Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is hashMap implemented as an array of linked lists

Tags:

java

hashmap

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?

like image 433
Victor Avatar asked Feb 15 '23 11:02

Victor


2 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.

like image 65
Adam Stelmaszczyk Avatar answered Feb 20 '23 09:02

Adam Stelmaszczyk


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.

like image 38
pamphlet Avatar answered Feb 20 '23 09:02

pamphlet