Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #8032

Re: string case clauses

Show all headers | View raw

On Sun, 11 Sep 2011 20:05:20 -0700, Peter Duniho
<NpOeStPeAdM@NnOwSlPiAnMk.com> wrote, quoted or indirectly quoted
someone who said :

>Huh?  How so?  It's actually basically the same algorithm a full-on hash 
>table would use.  Specifically: hash value gets you to a very small 
>subset of the possible values (very often just one, as long as the hash 
>code algorithm is good), then linear search on collisions.

Before case strings, there were two JVM instructions for implementing
an int switch, tableswitch and lookupswitch. The efficient tableswitch
is a jump table used when the switch values are reasonably dense e.g.
numbered 0..N. The less efficient lookupswitch is a binary search or
linear search used when the switch values all over the map.

I understood the way string case labels worked posted earlier was to
use the hashCode as the switch variable, which would necessitate the
use of the inefficient lookupswitch plus a little kludge to deal with
hashCode collisions.  

In contrast a String case lookup done manually with HashMap does not
involve any binary search or linear scan.  It folds the hashCode to a
reasonable value and does a table lookup.

As usual, there is nothing in the JVM spec that says how lookupswitch
has to be implemented. For maximum speed (but extravagant RAM), the
JIT could analyse the values, and construct a perfect or near perfect
hash table. It has the advantage the values are known at load time and
cannot change.  I have seen reference to a number of C algorithms for
doing this. The JIT has to generate thread-safe code. HashMap does
not.

-- 
Roedy Green Canadian Mind Products
http://mindprod.com
The modern conservative is engaged in one of man's oldest exercises in moral philosophy; that is, 
the search for a superior moral justification for selfishness.
~ John Kenneth Galbraith (born: 1908-10-15 died: 2006-04-29 at age: 97) 

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

string case clauses Roedy Green <see_website@mindprod.com.invalid> - 2011-09-11 09:35 -0700
  Re: string case clauses Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-11 12:00 -0500
    Re: string case clauses Roedy Green <see_website@mindprod.com.invalid> - 2011-09-11 15:33 -0700
      Re: string case clauses Arne Vajhøj <arne@vajhoej.dk> - 2011-09-11 21:56 -0400
        Re: string case clauses Lew <lewbloch@gmail.com> - 2011-09-11 20:54 -0700
          Re: string case clauses Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 18:58 -0400
      Re: string case clauses Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-09-11 20:05 -0700
        Re: string case clauses Roedy Green <see_website@mindprod.com.invalid> - 2011-09-14 12:13 -0700
          Re: string case clauses Patricia Shanahan <pats@acm.org> - 2011-09-14 12:36 -0700
          Re: string case clauses Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-09-14 18:01 -0700
            Re: string case clauses Lew <lewbloch@gmail.com> - 2011-09-14 20:05 -0700

csiph-web