CODEWITHSUNDEEP
javadata-structureshashmaphashtable
LordDoskias
LordDoskias

Reputation: 3191

Hashmap with separate chaining

Is there an implementation of the java Map interface which utilizes separate chaining as collision resolution. By reading the javadocs for HashMap and HashTable I came to the conclusion that what the implementation does is basically replace the value and essentially doesn't employ any collision resolution?

Upvotes: 2

Views: 6010

Answers (2)

JB Nizet
JB Nizet

Reputation: 691715

You got it wrong: it uses a linked list of entries for each bucket.

When putting a value in the map, the map starts by calling hashCode on the key, then transforms this hash code so that it's between 0 and the number of buckets. If the bucket is empty, the key is stored in this bucket. If it's not, then every key in this bucket is compared to the new key with equals. If one is equal, then its value is replaced by the new value. Else, a new entry with the new key is added to the bucket's list of entries.

If you want to store multiple values for a given key, then use a Map<Key, List<Value>>, or use Guava's MultiMap.

Upvotes: 5

Vlad
Vlad

Reputation: 18633

It does have collision resolution, but that's because two different keys could plausibly end up in the same bucket after hashing.

If you want to store more than one value for a single key, you can always use HashMap<KeyType, ArrayList<ValueType>> and do some housekeeping to initialize the array when necessary.

Upvotes: 3

Related Questions