CODEWITHSUNDEEP
javadata-structures
Arham
Arham

Reputation: 2102

Does IdentityHashMap entertain collisions?

As per the Javadocs of IdentityHashMap, it says

This class implements the Map interface with a hash table, using reference-equality in place of object-equality when comparing keys (and values). In other words, in an IdentityHashMap, two keys k1 and k2 are considered equal if and only if (k1==k2). (In normal Map implementations (like HashMap) two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2)).)

As I understand, two different objects pointing to different memory locations can still have same hashcode hence object1.equals(object2) can return true. But two different objects pointing to different memory locations can never return true for object1 == object2.

Question 1 - when IdentityHashMap relies strictly on reference equality, does that mean collisions will never occur?

Question 2 - debugging the following code shows me 6 buckets in all with key and value both stored in separate buckets. But this is not the case with HashMap, where the key and value are stored in the same bucket.

As it's name has a 'hash' word in it, so it must be hashing the keys, then why does it store the keys and values separately and how does it retrieve the value of a given key?

String A = "abc";
String B = "def";
String C = new String("abc");
Map<String, String> map1 = new IdentityHashMap<String, String>();
map1.put(A, "123");
map1.put(B, "345");
map1.put(C, "567");

Upvotes: 3

Views: 515

Answers (3)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726987

Collisions happen when two different items have the same hash code, so obviously IdentityHashMap must deal with collisions. The only difference is that the "regular" hash map uses equals which can be true for different objects, while IdentityHashMap uses == that can't be true for different object.

The reason the "regular" hash map has separate variables for keys and values is an implementation detail of the IdentityHashMap: its implementation uses linear probing to address collisions, and it also stores keys and values in the same table: the key is placed at table[hash], while the value is placed at table[hash+1]. The regular HashMap defines an Entry class which combines the key with its value in the same object, and stores entries in buckets.

Upvotes: 1

JB Nizet
JB Nizet

Reputation: 692121

IdentityHashMap doesn't use the hashCode of the keys, but their System.identityHashCode. Although collisions of such identity hash codes are possible if you have a huge memory, they will be very seldom. That of course doesn't prevent two keys to end up in the same bucket, since the number of buckets is typically much smaller than 2^32 - 1.

Upvotes: 5

Peter Lawrey
Peter Lawrey

Reputation: 533820

when IdentityHashMap relies strictly on reference equality, does that mean collisions will never occur?

Collisions are almost as likely as if it didn't. System hashCodes are not unique and even if they were the collections are not 2^^32 in size so only the hashCode has to be cut down to a small number of bits.

how does it retrieve the value of a given key?

I would read the code to find out.

public V get(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k)
            return (V) tab[i + 1];
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
}

Upvotes: 3

Related Questions