Is HashMap internally implemented in Java using LinkedList or Array?
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) {
}
}
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.