Why the calculation of hash in HashMap(JDK1.8) don't need to consider the negative hashCode as ConcurrentHashMap does?

▲
2
▼

In HashMap: (h = key.hashCode()) ^ (h >>> 16);

In ConcurrentHashMap: (h ^ (h >>> 16)) & HASH_BITS;

where HASH_BITS is 0x7fffffff, by & HASH_BITS it can always be a positive number.

java
hashmap
concurrenthashmap
asked on Stack Overflow Aug 17, 2018 by neal • edited Aug 17, 2018 by Stephen C

2 Answers

▲
1
▼

Why the calculation of hash in HashMap(JDK1.8) don't need to consider the negative hashCode as ConcurrentHashMap does?

Ultimately, the case where the hash is negative (after spreading) does need to be considered in the HashMap case as well. It is just that this happens later in the code.

For example, in getNode (Java 8) you find this:

    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

Since tab.length is a power of 2, tab.length - 1 is a suitable bitmask for reducing hash to a subscript for the array.

You can rest assured that in every implementation of HashMap or ConcurrentHashMap there is some code that reduces the hash code to a number that is suitable for use as a subscript. It will be there ... somewhere.

But also ... don't expect the code of these classes to be easy to read. All of the collection classes have been reworked / tuned multiple times get the best possible (average) performance over a wide range of test cases.

answered on Stack Overflow Aug 17, 2018 by Stephen C
▲
0
▼

Actually it handles negative index calculations. It's not evident at first looking but there are calculations in some places while accessing the elements(key or value).

int index = (n - 1) & hash, in which n is length of the table

It simply handles negative indexing.

AFAIK, HashMap always uses arrays sized to a power of 2 (e.g. 16, 32, 64, etc.).

Let's assume we have capacity of 256(0x100) which is 2^8. After subtraction 1, we get 256 - 1 = 255 which is 0x100 - 0x1 = 0xFF The subtraction gives rise to get the proper bucket index between 0 to length-1 with exact bit mask needed to bitwise-and with the hash.

256 - 1 = 255
0x100 - 0x1 = 0xFF

A hash of 260 (0x104) gets bitwise-anded with 0xFF to yield a bucket number of 4.

A hash of 257 (0x101) gets bitwise-anded with 0xFF to yield a bucket number of 1.

answered on Stack Overflow Aug 17, 2018 by snr • edited Aug 17, 2018 by snr

User contributions licensed under CC BY-SA 3.0