Why hashmap internally uses LinkedList instead of Arraylist

Question

Why Hashmap internally use LinkedList instead of Arraylist when two objects are placed in the same basket in the hash table?

Answer 1

Why HashMap internally use s LinkedList instead of Arraylist when two objects are placed in the same basket in a hash table?

In fact, he does not use either (!).

In fact, it uses a singly linked list implemented by a chain of hash table entries. (In contrast, a LinkedList is linked twice, and it requires a separate Node object for each item in the list.)

So why am I picking on here? Because it is really important ... because it means that the usual compromise between LinkedList and ArrayList not applicable.

The usual compromise:

• ArrayList uses less space, but inserting and deleting the selected item in the worst case is O(N) .

• LinkedList uses more space, but inserting and deleting the selected item is O(1) .

However, in the case of a private, single-linked list, formed by combining together the HashMap input nodes, the service memory of the space is one link (the same as ArrayList ), the cost of inserting the node is O(1) (the same as [TG414). ]), and the cost of deleting the selected node is also O(1) (similar to LinkedList ).

Relying only on “big O” for this analysis is doubtful, but if you look at the real code, it becomes clear that the HashMap outperforms the ArrayList in performance for deletion and insertion, and is comparable in search. (This ignores the effects of locality of memory.) In addition, it uses less memory for chaining than ArrayList or LinkedList ... given that there are already internal input objects for storing key / value pairs.

But it gets even harder. In Java 8, they redesigned the internal HashMap data structures. In the current implementation, when the hash chain exceeds a certain length threshold, the implementation switches to using a binary tree view if the key type implements Comparable .

Answer 2

Short answer : Java uses LinkedList or ArrayList (depending on what it considers suitable for the data).

Long answer

Although a sorted ArrayList looks the obvious way, there are several practical advantages to using LinkedList. Keep in mind that the LinkedList chain is only used for key collisions. But how to define a hash function: collisions should be rare

In rare collisions, we must choose between a Sorted ArrayList or LinkedList. If we compare the sorted ArrayList and LinkedList, we get some obvious tradeoffs.

1. Insert and delete: A sorted ArrayList accepts O (n), but LinkedList accepts an O (1) constant
2. Extract: A sorted ArrayList accepts O (logn), and LinkedList accepts 0 (n).

Now it’s clear that LinkedList is better than a sorted ArrayList during insert and delete, but they are poor at searching.

Since the number of collisions is less, a sorted ArrayList brings less value (but more overhead). But when collisions occur more often, and the list of collision elements becomes large (over a certain threshold), Java changes the structure of the collision data from LinkedList to ArrayList.

Answer 3

It basically comes down to the complexities of ArrayList and LinkedList. The insert in LinkedList (when order is not important) is O (1), just add it to the beginning. The insertion into the ArrayList (when the order is not important) is O (N), moving to the end and also resizing the overhead.

Removing O (n) in LinkedList, moving and setting pointers. The deletion in the arraylist can be O (n ^ 2), move to shift and shift elements, or resize the Arraylist.

Contains O (n) in both cases.

When using HashMap, we will expect O (1) operations to add, remove, and contains. Using ArrayList, we will incur a higher cost for adding, removing operations in buckets