'Is hashMap implemented as an array of linked lists
While reading about HashMap I see that it is implemented as an array of buckets? Now are these buckets always linked lists? If so, why are they called buckets and not linked lists?
Solution 1:[1]
In Java's Hashmap, the buckets are implemented as a linked list (each Entry has a reference to another entry called next).
The term "bucket" is referring to a concept. Linked list an implementation detail.
Solution 2:[2]
Java, uses the concept of "Seperate Chaining" where it's implemented as an array of linked lists, in order to avoid collisions. This though, is not always the case. A hashmap can be implemented as an array entirely (linear probing); this though has a higher chance of creating a colission.
Regarding your question of "buckets". You could imagine a linked list as a bucket. However, if your HashMap implementation uses a proper HashFunction (algorithm to distribute your values in the hashmap array), your "buckets" only has, preferably, one item in it.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | pamphlet |
| Solution 2 | Daniel Mac |