Is HashMap internally implemented in Java using LinkedList or Array?
It basically looks like this:
this is the main array ↓[Entry] → Entry → Entry ← here is the linked-list[Entry][Entry] → Entry[Entry][null ][null ]
So you have the main array where each index corresponds to some hash value (mod
'ed* to the size of the array).
Then each of them will point to the next entry with the same hash value (again mod
'ed*). This is where the linked-list comes in.
*: As a technical note, it's first hashed with a different function before being mod
'ed, but, as a basic implementation, just modding will work.
Each HashMap
has an Array and in that Array it places each Entry
in a position according to its key's hash code (e.g. int position = entry.getKey().hashCode() % array.length
). The position where an Entry
is stored is called a bucket.
If more than one Entry
ends up in the same bucket, those Entries are combined in a LinkedList
(also see @Dukeling's answer). Thus the bucket metaphor: each Array index is a "bucket" where you dump in all matching keys.
You have to use an Array for the buckets in order to achieve the desired constant time performance for random access. Within a bucket you have to traverse all elements to find the desired key anyways, so you can use a LinkedList
as it is easier to append to (no resize needed).
This also shows the need for a good hash function, because if all keys hash to only a few values you will get long LinkedList
s to search and a lot of (fast to access) empty buckets.
HashMap has an array of HashMap.Entry objects :
/** * The table, resized as necessary. Length MUST Always be a power of two. */transient Entry<K,V>[] table;
We can say that Entry is a one-way linked list (such HashMap.Entry linkage is called "Bucket") but it is not actually a java.util.LinkedList.
See for yourself :
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } }