The difference between HashMap and IdentityHashMap

1. Example comparison between HashMap and IdentityHashMap

public static void main(String[] args) {<!-- -->
    HashMap hashMap = new HashMap();
    hashMap.put("1", "1");
    hashMap.put(String.valueOf(1), "1");
    hashMap.put(String.valueOf('1'), "1");
    hashMap.put(new String("1"), "1");
    System.out.println(hashMap);

    IdentityHashMap identityHashMap = new IdentityHashMap();
    identityHashMap.put("1", "1");
    identityHashMap.put(String.valueOf(1), "1");
    identityHashMap.put(String.valueOf('1'), "1");
    identityHashMap.put(new String("1"), "1");
    System.out.println(identityHashMap);
}

Console prints:

{1=1}
{1=1, 1=1, 1=1, 1=1}

The 4 keys put in the above code: “1”, String.value(1), String.value('1') and new String ("1"), the different address spaces in the memory they point to are 4 different objects, use == to judge, and the two are not equal to each other;

The String class rewrites the hashCode and equals methods, and the hashCode of these four objects all return the same value. When the equals method is executed in pairs, all return true;

When HashMap performs put operations on 4 keys, use hashCode as the hash value, use equals to judge equality, the last 3 put operations, and finally perform update operations, and finally there is only 1 item in HashMap;

When IdentityHashMap performs put operations on 4 keys, use System.identityHashCode as the hash value, use == to judge equality, and the last 3 put operations finally execute Insert operation, finally there are 4 items in the IdentityHashMap.

The above is the most essential difference in function between HashMap and IdentityHashMap.

2, HashMap and IdentityHashMap

3. IdentityHashMap source code analysis

Both IdentityHashMap and HashMap implement the data structure of the Hash table. The following mainly analyzes the differences between the two.

3.1 hash location index

private static int hash(Object x, int length) {<!-- -->
    int h = System. identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

What is called is System.identityHashCode to get the hash value, and then calculate the index position index in the table based on this.

3.2 get search

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);
    }
}

The get method of IdentityHashMap is much simpler than the get method of HashMap, one only uses 3 situations:

1. item == k, find the corresponding key, and return the corresponding value, the value exists in the right adjacent position of the key, return tab[i + 1];

2. item == null, according to the hash to locate the item is empty, indicating that the current key does not exist in the table, directly return null;

3. item != null & amp; & amp; item != key, indicating that a hash conflict occurs, call nextKeyIndex to obtain the index position after the conflict is processed, and then repeat the above process;

It should be noted that the == used in the judgment of equality operation here is not the equals method;

3.3 nextKeyIndex handles hash conflict

private static int nextKeyIndex(int i, int len) {<!-- -->
    return (i + 2 < len? i + 2 : 0);
}

The way IdentityHashMap handles conflicts is to develop the line type re-detection in the address method. After the current position is not occupied, it is found in the right adjacent position, and a key-value key-value pair in IdentityHashMap occupies two positions in the table , so the operation here is to add 2, if it exceeds the table size, start from 0.

3.4. put method

public V put(K key, V value) {<!-- -->
    final Object k = maskNull(key);

    retryAfterResize: for (;;) {<!-- -->
        final Object[] tab = table;
        final int len = tab. length;
        int i = hash(k, len);

        for (Object item; (item = tab[i]) != null;
             i = nextKeyIndex(i, len)) {<!-- -->
            if (item == k) {<!-- -->
                @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
        }

        final int s = size + 1;
        // Use optimized form of 3 * s.
        // Next capacity is len, 2 * current capacity.
        if (s + (s << 1) > len & amp; & amp; resize(len))
            continue retryAfterResize;

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}

The put method of IdentityHashMap is also very simple. Call the hash method to obtain the index of the key in the table, and then perform the assignment operation, which is also divided into three situations:

1. item == k, the corresponding key is found, and the value exists in the position adjacent to the right of the key, update tab[i + 1], and return the original value;

2. item == null, means there is no corresponding key value in the table, jump out of the for loop, execute tab[i] = k and tab[i + 1] = value Insert a new key. Personally, I think the timing of the expansion here is not very good. I finally found the update location. Because the expansion is gone, I have to recalculate again. Like HashMap, I can expand the capacity after updating;

3. item != null & amp; & amp; item != key, indicating that a hash conflict occurs, call nextKeyIndex to obtain the index position after the conflict is processed, and then repeat the above process.

4. IdentityHashMap usage scenarios

When the type of the Hash storage structure Key does not override the hashCode and equals methods, and the data stored in the Hash structure is small, and the Hash conflict is not serious, you can use IdentityHashMap to replace HashMap;

In the implementation of JDK dynamic proxy, IdentityHashMap is used to repeatedly verify the incoming proxy interface. The code is in Proxy.ProxyClassFactory.apply< In the /code> method, part of the code is as follows:

@Override
public Class<?> apply(ClassLoader loader, Class<?>[] interfaces) {<!-- -->

    Map<Class<?>, Boolean> interfaceSet = new IdentityHashMap<>(interfaces. length);
    for (Class<?> intf : interfaces) {<!-- -->
        /*
         * Verify that the class loader resolves the name of this
         * interface to the same Class object.
         */
        Class<?> interfaceClass = null;
        try {<!-- -->
            interfaceClass = Class.forName(intf.getName(), false, loader);
        } catch (ClassNotFoundException e) {<!-- -->
        }
        if (interfaceClass != intf) {<!-- -->
            throw new IllegalArgumentException(
                    intf + " is not visible from class loader");
        }
        /*
         * Verify that the Class object actually represents an
         * interface.
         */
        if (!interfaceClass.isInterface()) {<!-- -->
            throw new IllegalArgumentException(
                    interfaceClass.getName() + " is not an interface");
        }
        /*
         * Verify that this interface is not a duplicate.
         */
        if (interfaceSet. put(interfaceClass, Boolean. TRUE) != null) {<!-- -->
            throw new IllegalArgumentException(
                    "repeated interface: " + interfaceClass. getName());
        }
    }

    //...
}