Why does Hashmap Internally use LinkedList instead of Arraylist

Question

Why does Hashmap internally use a LinkedList instead of an Arraylist when two objects are placed in the same bucket in the hash table?

Solution

Why does HashMap internally use s LinkedList instead of an Arraylist, when two objects are placed into the same bucket in the hash table?

Actually, it doesn't use either (!).

It actually uses a singly linked list implemented by chaining the hash table entries. (By contrast, a LinkedList is doubly linked, and it requires a separate Node object for each element in the list.)

So why am I nitpicking here? Because it is actually important ... because it means that the normal trade-off between LinkedList and ArrayList does not apply.

The normal trade-off is:

• ArrayList uses less space, but insertion and removal of a selected element is O(N) in the worst case.

• LinkedList uses more space, but insertion and removal of a selected element¹ is O(1).

However, in the case of the private singly linked list formed by chaining together HashMap entry nodes, the space overhead is one reference (same as ArrayList), the cost of inserting a node is O(1) (same as LinkedList), and the cost of removing a selected node is also O(1) (same as LinkedList).

Relying solely on "big O" for this analysis is dubious, but when you look at the actual code, it is clear that what HashMap does beat ArrayList on performance for deletion and insertion, and is comparable for lookup. (This ignores memory locality effects.) And it also uses less memory for the chaining than either ArrayList or LinkedList was used ... considering that there are already internal entry objects to hold the key / value pairs.

But it gets even more complicated. In Java 8, they overhauled the HashMap internal data structures. In the current implementation, once a hash chain exceeds a certain length threshold, the implementation switches to using a binary tree representation if the key type implements Comparable.

---

^{1 - That is the insertion / deletion is O(1) if you have found the insertion / removal point. For example, if you are using the insert and remove methods on a LinkedList object's ListIterator.}

Comments

[Lii]

"Removal in arraylist could be O(n^2) , traverse to element and shift elements": This actually only makes it O(n), because O(n + n) = O(2*n) = O(n).

[dhke]

Also think of the memory overhead. ArrayList overallocates, for large hashtables with a low load factor this becomes really significant.

[Lii]

"Insertion in ArrayList (when order is not important) is O(N) ,traverse to end and there is also resizing overhead.": This seems to be a misunderstanding. In an array based list you usually know where the end is, so insertions (including amortised resizing) are O(1) there too.

[yug]

Java Hashmap uses singly linklist, it does not use Arraylist. Please refer to the above mentioned explanation.