HashMap存储原理以及与hashcode、equals方法的关系

一、HashMap 存储/读取数据原理：
先放源码：

public class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable {
    private static final int MINIMUM_CAPACITY = 4;
...
    transient HashMapEntry<K, V>[] table;
...
    private static final Entry[] EMPTY_TABLE
            = new HashMapEntry[MINIMUM_CAPACITY >>> 1];
  ...       
   @Override public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);
        for (HashMapEntry<K, V> 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;
    }
    ...
        public V get(Object key) {
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            return e == null ? null : e.value;
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
        }
    ...
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54

    HashMap中存储数据是用一个数组来保存的，也就是上面的table变量，其类型是HashMapEntry的数组，
    而HashMapEntry则是保存键值对的数据结构，并且有本身类型的next变量，可以构成链表。

    HashMap存储数据时，首先根据key的hashcode值找到应该保存在table数组的下标位置，如果该位置之前没有
    保存过值，也就是没有发生碰撞，则保存这个键值对对象到该位置中；如果发生了碰撞，也就是说有两个对象的key
    的hashcode值相等，那么则需要通过key的equals方法判断这两个对象是否是同一个对象，如果是，那么原本存
    储的旧值会被新值所替换；如果不是同一个对象，则把新的键值对对象保存到旧的键值对对象next变量中，构成链表。


    我们分析下put方法的实现：
    1、if (key == null) {
        return putValueForNullKey(value);
    }
        首先判断是否为null,如果为null则特殊处理；

    2、int hash = Collections.secondaryHash(key);
    获取Key的二级hash值，其中Collections.secondaryHash方法的实现就是把Key的hashcode值
    做一定改变；

    3、int index = hash & (tab.length - 1);
    通过刚才计算的hash值来获取该key应该存放在数组的下标位置，也就是获取该数据应该存储在table数
    组的哪个位置；

    4、for (HashMapEntry<K, V> 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;
        }
    }
    如果已经有该key存在了，则覆盖这个key的值value。
    注意这里的判断：因为只有两个对象的hashcode值相等并且两个对象用equals判断返回true时，才
    去覆盖原有的值；

    5、
    if (size++ > threshold) {
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);
        如果该key不存在，或者发生碰撞的对象不是一个对象时，则需要把它存储下来。首先如果存储数量已经
        大于数组大小，则把数组双倍扩大。然后再把键值对保存到数组中。
    注意这里保存的时候，如果数组存储位置原本就存在键值对，那么则把新的键值对对象保存到旧的键值对
    对象next变量中，构成链表。

二、HashMap与hashcode、equals方法的关系
它们的关系从上面的源码都能略知一二，再说个实际情况。
假设你用自定义类型MyClass作为HashMap的Key，同时为了需求重写了hashcode、equals方法（这个
很常见），那么很有可能会影响HashMap的执行效率，例如：

1、重写hashcode方法后，任何对象返回都是同一个hash值，那么，每次存储都会发生碰撞，所有对象都只会保存
在HaspMap的一格中，HashMap就等于废了；

2、重写hashcode方法后，其返回值会随属性的变化而变化，这样的话，因为HashMap是根据Key的hashcode
值存储读取的，如果同一个对象每次返回的hashcode都不一样，则根本无法读取你上次保存的位置，也就是
HashMap会失效；

3、重写equals方法后，只根据对象的某些属性值相等与否来决定equals方法是否返回true。这样的话，就有可
能两个其实不是一个对象的，但是保存到HashMap时，则被认为是一个对象，导致其值被覆盖了；

还有很多很多要注意的情况，为了避免这些情况，我们需要注意一些地方：当你使用任何对象作为Key，那么它必
须遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变。

推荐看这些文章：
http://www.importnew.com/7099.html
http://blog.csdn.net/michaellufhl/article/details/5833188