user5777530 user5777530 - 5 months ago 21
Java Question

A matter in the method "transfer " in HashMap ( jdk 1.6 )?

the source code is like this:

void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}


but I want to do like this,does this work well or any problem?
I think the hash value of all elements in the same list is same ,so we don't need calculate the buketIndex of the new table;the only thing we should do is
transfer the head element to the new table,and this will save time.
Thank you for your answer.

void transfer(Entry[] newTable){
Entry[] src = table;
int newCapacity = newTable.length;
for(int j = 0 ;j< src.length;j++){
Entry<K,V> e = src[j];
if(null != e){
src[j] = null;
int i = indexFor(e.hash,newCapacity);
newTable[i] = e;
}
}
}

Answer

I think you are asking about the HashMap class as implemented in Java 6, and (specifically) whether your idea for optimizing the internal transfer() method would work.

The answer is No it won't.

This transfer method is called when the main array has been resized, and its purpose is to transfer all existing hash entries to the correct hash chain in the resized table. Your code is simply moving entire chains. That won't work. The problem is that the hash chains typically hold entries with multiple different hashcodes. While a given group of entries all belonged on the same chain in the old version of the table, in the new version they probably won't.

In short, your proposed modification would "lose" some entries because they would be in the wrong place in the resized table.


There is a meta-answer to this too. The standard Java classes were written and tested by a group of really smart software engineers. Since then, the code has probably been read by tens or hundreds of thousands of other smart people outside of Sun / Oracle. The probability that everyone else has missed a simple / obvious optimization like this is ... vanishingly small.

So if you do find something that looks to you like an optimization (or a bug) in the Java source code for Java SE, you are probably mistaken!