HashMap Bucket Index
Problem
A Java HashMap with a table of size n (n is a power of 2) stores a key in the bucket (h ^ (h >>> 16)) & (n - 1), where h is the hash code of the key (computed as for Java strings, 32-bit wrapping). The xor with the upper 16 bits mixes the high bits into the low bits. Input: a word and the table size n. Print the bucket index.
Constraints
- 1 <= length <= 100
- n is a power of 2, 2 <= n <= 2^20
Examples
Input
hello 16
Output
11
Solutions
Because the table size is a power of 2, a bit mask replaces the remainder. The xor with the upper 16 bits makes the high bits of the hash matter even for a small table.
/*
* Problem : Find the bucket.
* Input : A word and the table size.
* Output : The bucket index.
* Approach: Bit mask
* Time : O(length)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int solve(String a, String b) {
// Step 1: The hash code of the word. Java computes it as a 32-bit int.
int h = a.hashCode();
int size = Integer.parseInt(b);
// Step 2: Mix the upper 16 bits into the lower 16 bits. ">>>" moves bits right and fills with zeros.
int spread = h ^ (h >>> 16);
// Step 3: The size is a power of 2, so "& (size - 1)" keeps the low bits: the same as a remainder, but faster.
return spread & (size - 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a = scanner.next();
String b = scanner.next();
System.out.println(solve(a, b));
}
}
Hints (2)
- Why xor with h >>> 16?
- Why does the mask equal the remainder?