Re: Hash or Tree
Philipp wrote :
Wojtek wrote:
Thank-you for all for responding
Philipp wrote :
Wojtek wrote:
Also, if you want to optimize further, and you know you have a well
distributed hashCode (which is the case for the String class), you may
copy the code of HashMap and remove the call to the hash(int h) method
which serves only to prevent very bad hashes to alter the HashMap's
performance prohibitively.
If I do not use the call, how could its removal speed thihgs up? I only
fill the HashMap up once, when the app starts. It NEVER gets any more
values put in.
The internal code of HashMap for get(Object key) (which is the method you
call very often) looks like this:
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
Note in particular that the hashcode of the key is hashed once again by the
hash(int) method. If you have a well distributed hashCode, you can forget
about this step and implement a get which uses the hashCode of the String
directly.
Hmmm, store the key hashcode, then use it directly. This bears thinking
on.
We are already using an object (LangKey) to store the key, so storing
the hashcode for each key is trivial. But HashMap does not expose any
method which can get a value from a passed hash code.
BUT, I could place each key during the loading process into an
ArrayList, then when done create an array from it, then run through the
array and set the index value into the LangKey. Then use that index
value to directly access the array to get the value.
I don't know if this will speed things up significantly, although if you
happen to measure it, please post your results.
I will need to use a VERY fine-grained timer run over the same page
sequence. System.nanoTime() here we come...
--
Wojtek :-)