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?
-
3What programming language is this for? Suspecting Javasmac89– smac892013-08-23 19:54:07 +00:00Commented Aug 23, 2013 at 19:54
-
2That kind of assumption has led to a famous DoS attack (bugzilla.redhat.com/show_bug.cgi?id=750521). In retrospect, a linked list was a poor choice of bucket implementation, but Java is not going to change it.usethe4ce– usethe4ce2013-08-23 20:14:09 +00:00Commented Aug 23, 2013 at 20:14
Add a comment
|
3 Answers
Looking at the source code of HashMap tells us that it's implemented as an array of Entries:
transient Entry[] table;
Each Entry has a field next, so they create a single linked list structure:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
"Bucket" is a higher-level term, used in the literature and when explaining hash maps. Here "buckets" are implemented as a single linked lists.
answered Aug 23, 2013 at 19:57
Adam Stelmaszczyk
19.9k4 gold badges72 silver badges111 bronze badges
Comments
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.
Comments
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.
