碰到一些需求需要放入可重复key的HashMap，比如Excel需要报错的行号。

那么如果对象实现过hashCode方法和equals 那么放入到hashMap中会出现可能互相覆盖的情形。

原来你是这样的HashMap 正如这篇文章中的测试所说，互相覆盖。

那么就是IdentityHashMap出场的时候啦~

首先了解一下Object的hashCode方法

/**  * Returns a hash code value for the object. This method is  * supported for the benefit of hash tables such as those provided by  * {@link java.util.HashMap}.  * <p>  * The general contract of {@code hashCode} is:  * <ul>  * <li>Whenever it is invoked on the same object more than once during  *     an execution of a Java application, the {@code hashCode} method  *     must consistently return the same integer, provided no information  *     used in {@code equals} comparisons on the object is modified.  *     This integer need not remain consistent from one execution of an  *     application to another execution of the same application.  * <li>If two objects are equal according to the {@code equals(Object)}  *     method, then calling the {@code hashCode} method on each of  *     the two objects must produce the same integer result.  * <li>It is <em>not</em> required that if two objects are unequal  *     according to the {@link java.lang.Object#equals(java.lang.Object)}  *     method, then calling the {@code hashCode} method on each of the  *     two objects must produce distinct integer results.  However, the  *     programmer should be aware that producing distinct integer results  *     for unequal objects may improve the performance of hash tables.  * </ul>  * <p>  * As much as is reasonably practical, the hashCode method defined by  * class {@code Object} does return distinct integers for distinct  * objects. (This is typically implemented by converting the internal  * address of the object into an integer, but this implementation  * technique is not required by the  * Java<font size="-2"><sup>TM</sup></font> programming language.)  *  * @return  a hash code value for this object.  * @see     java.lang.Object#equals(java.lang.Object)  * @see     java.lang.System#identityHashCode  */ public native int hashCode();

文章中提到了java.lang.System#identityHashCode 那么我们看一下这两个数据有没有差别

这里面包含了IntegerCache的相关知识可以各位详细看看Integer的源码

我们可以看出hashCode计算出来（未复写Object）的值和identityHashCode计算出来的相同（估计就是一个值？

/**  * Returns the same hash code for the given object as  * would be returned by the default method hashCode(),  * whether or not the given object's class overrides  * hashCode().  * The hash code for the null reference is zero.  *  * @param x object for which the hashCode is to be calculated  * @return  the hashCode  * @since   JDK1.1  */ public static native int identityHashCode(Object x);

bingo~就是和hashCode返回一样【而toString中并不是内存地址而是hashCode的hexString】

/**  * Returns a string representation of the object. In general, the  * {@code toString} method returns a string that  * "textually represents" this object. The result should  * be a concise but informative representation that is easy for a  * person to read.  * It is recommended that all subclasses override this method.  * <p>  * The {@code toString} method for class {@code Object}  * returns a string consisting of the name of the class of which the  * object is an instance, the at-sign character `{@code @}', and  * the unsigned hexadecimal representation of the hash code of the  * object. In other words, this method returns a string equal to the  * value of:  * <blockquote>  * <pre>  * getClass().getName() + '@' + Integer.toHexString(hashCode())  * </pre></blockquote>  *  * @return  a string representation of the object.  */ public String toString() {     return getClass().getName() + "@" + Integer.toHexString(hashCode()); }

那么来看一下IdentityHashMap对应的实现

/**  * Constructs a new, empty identity hash map with a default expected  * maximum size (21).  */ public IdentityHashMap() {     init(DEFAULT_CAPACITY); }   /**  * Constructs a new, empty map with the specified expected maximum size.  * Putting more than the expected number of key-value mappings into  * the map may cause the internal data structure to grow, which may be  * somewhat time-consuming.  *  * @param expectedMaxSize the expected maximum size of the map  * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative  */ public IdentityHashMap(int expectedMaxSize) {     if (expectedMaxSize < 0)         throw new IllegalArgumentException("expectedMaxSize is negative: "                                            + expectedMaxSize);     init(capacity(expectedMaxSize)); }   /**  * Returns the appropriate capacity for the specified expected maximum  * size.  Returns the smallest power of two between MINIMUM_CAPACITY  * and MAXIMUM_CAPACITY, inclusive, that is greater than  * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise  * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it  * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.  */ private int capacity(int expectedMaxSize) {     // Compute min capacity for expectedMaxSize given a load factor of 2/3     int minCapacity = (3 * expectedMaxSize)/2;       // Compute the appropriate capacity     int result;     if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {         result = MAXIMUM_CAPACITY;     } else {         result = MINIMUM_CAPACITY;         while (result < minCapacity)             result <<= 1;     }     return result; }   /**  * Initializes object to be an empty map with the specified initial  * capacity, which is assumed to be a power of two between  * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.  */ private void init(int initCapacity) {     // assert (initCapacity & -initCapacity) == initCapacity; // power of 2     // assert initCapacity >= MINIMUM_CAPACITY;     // assert initCapacity <= MAXIMUM_CAPACITY;       threshold = (initCapacity * 2)/3;     table = new Object[2 * initCapacity]; }

在传入容量的时候和HashMap不一样 其优先计算了1.5倍 恩 这样不需要开发者考虑expectedSize了

查看其get方法

private static int nextKeyIndex(int i, int len) {     return (i + 2 < len ? i + 2 : 0); }   /**  * Returns the value to which the specified key is mapped,  * or {@code null} if this map contains no mapping for the key.  *  * <p>More formally, if this map contains a mapping from a key  * {@code k} to a value {@code v} such that {@code (key == k)},  * then this method returns {@code v}; otherwise it returns  * {@code null}.  (There can be at most one such mapping.)  *  * <p>A return value of {@code null} does not <i>necessarily</i>  * indicate that the map contains no mapping for the key; it's also  * possible that the map explicitly maps the key to {@code null}.  * The {@link #containsKey containsKey} operation may be used to  * distinguish these two cases.  *  * @see #put(Object, Object)  */ 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);     } }

很明显其使用了item==k 其实就是地址的比较

nextKeyIndex这个方法很有意思 看来是用来解决Hash冲突的。hashMap通过链表完成了冲突的解决。{

查看hash方法

/**  * Returns index for Object x.  */ 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); } 

直接调用了System.identityHashCode 并且和tab的length进行了hash【和hashMap类似】

那么IdentityHashMap通过挪后2个位置【下一个位置用来放value】来占位置【某些情境下性能确实很差，但是通过threshold为2/3稍微稀疏了一些】

继续查看put方法

/**  * Associates the specified value with the specified key in this identity  * hash map.  If the map previously contained a mapping for the key, the  * old value is replaced.  *  * @param key the key with which the specified value is to be associated  * @param value the value to be associated with the specified key  * @return the previous value associated with <tt>key</tt>, or  *         <tt>null</tt> if there was no mapping for <tt>key</tt>.  *         (A <tt>null</tt> return can also indicate that the map  *         previously associated <tt>null</tt> with <tt>key</tt>.)  * @see     Object#equals(Object)  * @see     #get(Object)  * @see     #containsKey(Object)  */ public V put(K key, V value) {     Object k = maskNull(key);     Object[] tab = table;     int len = tab.length;     int i = hash(k, len);       Object item;     while ( (item = tab[i]) != null) {         if (item == k) {             V oldValue = (V) tab[i + 1];             tab[i + 1] = value;             return oldValue;         }         i = nextKeyIndex(i, len);     }       modCount++;     tab[i] = k;     tab[i + 1] = value;     if (++size >= threshold)         resize(len); // len == 2 * current capacity.     return null; }

确实可以看到当hash之后发生碰撞直接找到null可以放入为止。

可以看到查找和插入都比较简单。那么如果移除呢

 此时需要注意了。因为当前移除的hash可能是后面如果和当前hash一样的需要前移

/**  * Removes the mapping for this key from this map if present.  *  * @param key key whose mapping is to be removed from the map  * @return the previous value associated with <tt>key</tt>, or  *         <tt>null</tt> if there was no mapping for <tt>key</tt>.  *         (A <tt>null</tt> return can also indicate that the map  *         previously associated <tt>null</tt> with <tt>key</tt>.)  */ public V remove(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) {             modCount++;             size--;             V oldValue = (V) tab[i + 1];             tab[i + 1] = null;             tab[i] = null;             closeDeletion(i);             return oldValue;         }         if (item == null)             return null;         i = nextKeyIndex(i, len);     }   }

换言之需要当前的数据之后【循环table到头了需要从0从开始】全部数据需要朝前提两个格子知道查找到为null为止

/**  * Rehash all possibly-colliding entries following a  * deletion. This preserves the linear-probe  * collision properties required by get, put, etc.  *  * @param d the index of a newly empty deleted slot  */ private void closeDeletion(int d) {     // Adapted from Knuth Section 6.4 Algorithm R     Object[] tab = table;     int len = tab.length;       // Look for items to swap into newly vacated slot     // starting at index immediately following deletion,     // and continuing until a null slot is seen, indicating     // the end of a run of possibly-colliding keys.     Object item;     for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;          i = nextKeyIndex(i, len) ) {         // The following test triggers if the item at slot i (which         // hashes to be at slot r) should take the spot vacated by d.         // If so, we swap it in, and then continue with d now at the         // newly vacated i.  This process will terminate when we hit         // the null slot at the end of this run.         // The test is messy because we are using a circular table.         int r = hash(item, len);         if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {             tab[d] = item;             tab[d + 1] = tab[i + 1];             tab[i] = null;             tab[i + 1] = null;             d = i;         }     } }

其实key也不重复只是判断“equals”的逻辑发生了变化~