2016-08-19 16:00

为什么两个对象equals返回true,可以hashcode不相等?

两个对象通过equals比较返回true.但是hashcode!=是一种什么样的情况.是为了节省HashMap的底层数组空间.也没有必要就完全不冲突.有一丢丢冲突的话.不用没一个Entry都用一个buckt啊.能省一些.

总之如果两个对象通过equals比较相等并且hashcode也相等的时候. 新添加的kv对v会覆盖掉原来的老的v.并且添加完成以后put方法返回老的被替换的v.

HashMap底层存储结构就是一个类型为HashMapEntry的数组

HashMapEntry就是一个单链表.存储了自己的key,value,hashcode以及下个HashMapEntry.

static class HashMapEntry
    
      implements Entry
     
       {        final K key;        V value;        final int hash;        HashMapEntry
      
        next;        HashMapEntry(K key, V value, int hash, HashMapEntry
       
         next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }        @Override public final boolean equals(Object o) {            if (!(o instanceof Entry)) {                return false;            }            Entry
         e = (Entry
        ) o;            return Objects.equal(e.getKey(), key)                    && Objects.equal(e.getValue(), value);        }        @Override public final int hashCode() {            return (key == null ? 0 : key.hashCode()) ^                    (value == null ? 0 : value.hashCode());        }}
       
      
     
    

对于put(k,v)方法根据k的值是否为null被当成两种情况来对待.

当key为null的情况

private V putValueForNullKey(V value) {    HashMapEntry
    
      entry = entryForNullKey;    if (entry == null)     {        addNewEntryForNullKey(value);        size++;        modCount++;        return null;    }     else     {        preModify(entry);        V oldValue = entry.value;        entry.value = value;        return oldValue;    }}
    

@Override public V put(K key, V value) {        if (key == null) {            return putValueForNullKey(value);        }        int hash = Collections.secondaryHash(key);        HashMapEntry
    
     [] tab = table;        int index = hash & (tab.length - 1);        for (HashMapEntry
     
       e = tab[index]; e != null; e = e.next) {            if (e.hash == hash && key.equals(e.key)) {                preModify(e);                V oldValue = e.value;                e.value = value;                return oldValue;            }        }        // No entry for (non-null) key is present; create one        modCount++;        if (size++ > threshold) {            tab = doubleCapacity();            index = hash & (tab.length - 1);        }        addNewEntry(key, value, hash, index);        return null;    }
     
    

int hash = Collections.secondaryHash(key);int index = hash & (tab.length - 1);public static int secondaryHash(Object key) {        return secondaryHash(key.hashCode());}private static int secondaryHash(int h) {        // Spread bits to regularize both segment and index locations,        // using variant of single-word Wang/Jenkins hash.        h += (h <<  15) ^ 0xffffcd7d;        h ^= (h >>> 10);        h += (h <<   3);        h ^= (h >>>  6);        h += (h <<   2) + (h << 14);        return h ^ (h >>> 16);    }

对于任意一个非null的key,总是能通过计算,获得一个整型值.这个整型值就是存储的bucket应该在HashMapEntry[]数组中的index. 这个是为什么? 计算出来的index就不会大于table数组的长度吗?我艹,太他妈难看懂了

public HashMap() {        table = (HashMapEntry
    
     []) EMPTY_TABLE;        threshold = -1; // Forces first put invocation to replace EMPTY_TABLE}
    

/**     * Min capacity (other than zero) for a HashMap.     * Must be a power of two greater than 1 (and less than 1 << 30).     */    private static final int MINIMUM_CAPACITY = 4;         /**     * An empty table shared by all zero-capacity maps (typically from default     * constructor). It is never written to, and replaced on first put. Its size     * is set to half the minimum, so that the first resize will create a     * minimum-sized table.     */    private static final Entry[] EMPTY_TABLE            = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

/**     * The table is rehashed when its size exceeds this threshold.     * The value of this field is generally .75 * capacity, except when     * the capacity is zero, as described in the EMPTY_TABLE declaration     * above.     */         private transient int threshold;

也即HashMap默认构造方法创建的是一个长度为2的数组.日了名字还得叫EMPTY_TABLE. 但是他没有用.而是会在第一次put进元素的时候resize. 当第一次put进元素的时候直接进入代码.

@Override public V put(K key, V value) {        if (key == null) {            return putValueForNullKey(value);        }            //A        int hash = Collections.secondaryHash(key);        HashMapEntry
    
     [] tab = table;        int index = hash & (tab.length - 1);        for (HashMapEntry
     
       e = tab[index]; e != null; e = e.next) {            if (e.hash == hash && key.equals(e.key)) {                preModify(e);                V oldValue = e.value;                e.value = value;                return oldValue;            }        }        //A        // No entry for (non-null) key is present; create one        modCount++;        //B        if (size++ > threshold) {            tab = doubleCapacity();            //CC            index = hash & (tab.length - 1);        }        //B        addNewEntry(key, value, hash, index);        return null;    }
     
    

因为是第一次put元素.所以必然不会经过A段代码. 并且threshold的值默认为0.那么就会进入B段代码. 并且CC处index的值又变了.变成 index = hash & (tab.length -1);

tab = doubleCapacity();

这一行代码并不是简单的扩容两倍.还会对原先的老数据搞什么鸡巴rehash.看不懂了这就

void addNewEntry(K key, V value, int hash, int index) {        table[index] = new HashMapEntry
    
     (key, value, hash, table[index]);}