java.util.HashMap implements Hash table data structure. It maintains an array of buckets.
The hashCode() of a particular key object is mapped to a bucket array index.
Multiple keys are allowed to have same hashcode. That's why each bucket can contain multiple key/value pair (HashMap entry).
Entries, within a bucket, are arranged via Linked data structure.
During HashMap#get(key) call, first a bucket is selected by mapping the key's hashCode to the bucket index, then the target entry is searched by calling equals() method on the key.
If two keys have same hash per hashCode() method then they should not be same per equal() method
Example
package com.logicbig.example;
public class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
Person person = (Person) o;
if (age != person.age)
return false;
return name.equals(person.name);
}
@Override
public int hashCode() {
int result = name.hashCode();
result = 31 * result + (age/4);
return result;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
As seen above, inside hashCode(), age is divided by 4. That means for same person's name, 4 consecutive ages will make one hashcode group. Let's see that in code:
package com.logicbig.example;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ExampleMain {
public static void main(String[] args){
Map<Integer, List<Person>> bucketMap = new HashMap<>();
for (int i = 20; i <= 30; i++) {
Person person = new Person("Tina", i);
int hashCode = person.hashCode();
List<Person> persons = bucketMap.get(hashCode);
if (persons == null) {
persons = new ArrayList<>();
bucketMap.put(hashCode, persons);
}
persons.add(person);
}
bucketMap.forEach((k, v) -> {
System.out.println("hashcode: " + k);
v.forEach(x -> System.out.println(" " + x));
});
}
}
hashcode: 80812541
Person{name='Tina', age=20}
Person{name='Tina', age=21}
Person{name='Tina', age=22}
Person{name='Tina', age=23}
hashcode: 80812543
Person{name='Tina', age=28}
Person{name='Tina', age=29}
Person{name='Tina', age=30}
hashcode: 80812542
Person{name='Tina', age=24}
Person{name='Tina', age=25}
Person{name='Tina', age=26}
Person{name='Tina', age=27}
HashMap internally maps each hashCode group to a bucket index as shown by following code:
package com.logicbig.example;
import java.util.ArrayList;
import java.util.List;
public class ExampleMain2 {
public static void main(String[] args) {
List<Person> firstList = new ArrayList<>();
int hashCode = 0;
for (int i = 20; i <= 30; i++) {
Person person = new Person("Tina", i);
int hash = hash(person.hashCode());
if (hashCode != hash) {
firstList.add(person);
hashCode = hash;
}
}
for (Person person : firstList) {
int hash = hash(person.hashCode());
//HashMap's initial bucket array size i.e. 16
int n = 1 << 4;
//HashMap's hash to bucket index formula
int index = (n - 1) & hash;
System.out.printf("index: %s, hash: %s%n", index, hash);
}
}
//internally used by HashMap
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
}
index: 12, hash: 80813356
index: 15, hash: 80813359
index: 14, hash: 80813358
Let's use some reflection to see how HashMap's bucket is populated.
package com.logicbig.example;
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;
public class ExampleMain3 {
public static void main(String[] args) throws Exception {
Map<Person, Integer> personSalaryMap = new HashMap<>();
for (int i = 20; i <= 30; i++) {
Person person = new Person("Tina", i);
personSalaryMap.put(person, ThreadLocalRandom.current().nextInt(100, 1000));
}
printHashMapBuckets(personSalaryMap);
}
private static void printHashMapBuckets(Map<Person, Integer> personSalaryMap) throws Exception {
//HashMap#table field = array of bucket
Field bucketArrayField = HashMap.class.getDeclaredField("table");
bucketArrayField.setAccessible(true);
Object[] buckets = (Object[]) bucketArrayField.get(personSalaryMap);
System.out.println("Number of buckets: " + buckets.length);
for (int i = 0; i < buckets.length; i++) {
Object node = buckets[i];
if (node == null) {
continue;
}
System.out.printf("\n-- bucket index: %s --%n", i);
print(1, "Node: " + node);
printNode(node, 1);
}
}
private static void printNode(Object node, int level) throws IllegalAccessException {
for (Field declaredField : node.getClass().getDeclaredFields()) {
declaredField.setAccessible(true);
String fieldName = declaredField.getName();
Object value = declaredField.get(node);
if (fieldName.equals("next")) {
if (value == null) {
continue;
}
print(level, "Next Node:" + value);
printNode(value, level + 1);
continue;
}
print(level, fieldName + " = " + value);
}
}
private static void print(int level, String string) {
System.out.printf("%" + (level * 4 - 3) + "s|- %s%n", "", string);
}
}
Number of buckets: 16
-- bucket index: 12 --
|- Node: Person{name='Tina', age=20}=722
|- hash = 80813356
|- key = Person{name='Tina', age=20}
|- value = 722
|- Next Node:Person{name='Tina', age=21}=507
|- hash = 80813356
|- key = Person{name='Tina', age=21}
|- value = 507
|- Next Node:Person{name='Tina', age=22}=530
|- hash = 80813356
|- key = Person{name='Tina', age=22}
|- value = 530
|- Next Node:Person{name='Tina', age=23}=228
|- hash = 80813356
|- key = Person{name='Tina', age=23}
|- value = 228
-- bucket index: 14 --
|- Node: Person{name='Tina', age=28}=425
|- hash = 80813358
|- key = Person{name='Tina', age=28}
|- value = 425
|- Next Node:Person{name='Tina', age=29}=447
|- hash = 80813358
|- key = Person{name='Tina', age=29}
|- value = 447
|- Next Node:Person{name='Tina', age=30}=758
|- hash = 80813358
|- key = Person{name='Tina', age=30}
|- value = 758
-- bucket index: 15 --
|- Node: Person{name='Tina', age=24}=652
|- hash = 80813359
|- key = Person{name='Tina', age=24}
|- value = 652
|- Next Node:Person{name='Tina', age=25}=516
|- hash = 80813359
|- key = Person{name='Tina', age=25}
|- value = 516
|- Next Node:Person{name='Tina', age=26}=709
|- hash = 80813359
|- key = Person{name='Tina', age=26}
|- value = 709
|- Next Node:Person{name='Tina', age=27}=439
|- hash = 80813359
|- key = Person{name='Tina', age=27}
|- value = 439
Example ProjectDependencies and Technologies Used:
|
|
