How does a HashMap work internally in Java, from the moment you call put to the moment you call get?
A HashMap holds an array of buckets, and each bucket holds the entries whose keys gave the same result when they were spread out.
Here is what happens when you call put. The map works out a hash for the key, and it spreads that hash around so that the low bits are well mixed. It then uses some of those bits to work out which bucket the entry belongs in. If that bucket is empty, the entry is put there. If the bucket already has entries, the map walks through them and compares each one, first by hash code and then by the equals method. If it finds a match, it replaces the value that is already there. If it does not, it adds the entry to that bucket.
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("one", "the first value");
map.put("two", "the second value");
// A put with a key that is already there replaces the value.
map.put("one", "a different value");
System.out.println("size : " + map.size());
System.out.println("one : " + map.get("one"));
System.out.println("two : " + map.get("two"));
System.out.println("missing : " + map.get("three"));
// The map knows straight away that it is full of strings.
System.out.println("has two : " + map.containsKey("two"));
}
}
When you call get, the same first half happens. The map works out the hash, works out the bucket, and walks through that bucket comparing the entries until it finds the one that matches. If the bucket is empty, the key is not in the map.
That is the whole idea. The array spreads the work out, so most buckets hold very few entries and the search is quick. The only slow case is when several keys land in the same bucket, and that is the subject of the next question.
The next question in this topic looks at what happens when the buckets get crowded.