bitwise operator >>> in hashCode

Question

I have two related questions:

1. the bitwise operator >>> means that we are shifting the binary number by those many places while filling 0 in the Most Significant Bit. But, then why does the following operation yields the same number: 5>>>32 yields 5 and -5>>>32 yields -5. Because if the above description is correct then both these operations would have yielded 0 as the final result.

2. In continuation to above, As per Effective Java book, we should use (int) (f ^ (f >>> 32)) (in case the field is long) while calculating the hash code (if the field is long). Why do we do that and what's the explanation

Idealist

Answer 1

Answer to your first question is here why is 1>>32 == 1?

The second question answer, in short, is that in such way the whole long value is used(not a part of it) and note that it is probably the fastest way to do this.

Cattegat

Can you please elaborate on the second point more, because as per the explanations, in case of long we can consider 0 to 63 values. So, why are we shifting by 32 and doing xor with the number itself (while calculating hashCode) – Idealist

We are making xor with the first 32-bit part of long, and the second one. That is all magic here=) – Cattegat

Answer 2

5 can be represented as 0101 if you shift it by 1 bit i.e 5>>>1 this will result as 0010=2

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f. The shift distance actually used is therefore always in the range 0 to 31, inclusive.

When you shift an integer with the << or >> operator and the shift distance is greater than or equal to 32, you take the shift distance mod 32 (in other words, you mask off all but the low order 5 bits of the shift distance). This can be very counterintuitive. For example (i> >> 32) == i, for every integer i. You might expect it to shift the entire number off to the right, returning 0 for positive inputs and -1 for negative inputs, but it doesn't; it simply returns i, because (i << (32 & 0x1f)) == (i << 0) == i.

Eastwardly

Thanks for the explanation, but what about the second question, why should we use (int) (f ^ (f >>> 32)) for calculation of hashCode (as per the Effective Java book) – Idealist

The long data type is a 64-bit two's complement integer. The signed long has a minimum value of -2^63 and a maximum value of 2^63-1. In Java SE 8 and later, you can use the long data type to represent an unsigned 64-bit long, which has a minimum value of 0 and a maximum value of 2^64-1. The unsigned long has a minimum value of 0 and maximum value of 2^64-1. Each right shift divides number by 2^K. And You actually cannot represent the number 2^63 = 9223372036854775808 in a Java primitive type, because that number is bigger than the maximum long, and long is the largest primitive type. – Eastwardly

Thanks, as per the reply of avrilfanomar, I feel that this operation of (int) (f ^ (f >>> 32)) is basically a way to achieve a possible unique number (by XORing the first half and second half of the number) and then converting it to int – Idealist

Answer 3

I know this question has been answered long back, but I tried an example to get more clarification and I guess it'll others too.

    long x = 3231147483648l;
    System.out.println(Long.toBinaryString(x));
    System.out.println(Long.toBinaryString(x >>> 32));
    System.out.println(Long.toBinaryString(x ^ (x >>> 32)));
    System.out.println(Long.toBinaryString((int) x ^ (x >>> 32)));

This prints -

101111000001001111011001011110001000000000

1011110000

101111000001001111011001011110000011110000

1001111011001011110000011110000

As @avrilfanomar mentions, this XORs first 32 bits of long with the other 32 bits and unsigned right shift operator helps us in doing this. Since we want to use this long field while calculating the hashcode, directly casting the long to int would mean that long fields differing only in the upper 32 bits will contribute the same value to the hashcode. This potentially means that two objects differing only in this field will have same hashcode and it'll be stored in the same bucket (with say a list to resolve collision) and this impacts the performance of hash-based collections. Hence, this operation.

Thaumatology