点滴记忆*记忆点滴

HashMap 作为MAP数据结构的JDK API 实现类，是java程序猿们最常用的类之一。它与hashTable 的区别也不知道被多少公司拿来作为面试题，因此很多人为了应付考试，在网上下载答案背诵一通。至于为什么hashmap 好，如何用好hashmap 都是一知半解。

其中包括刚出来时的笔者。下面就根据hash数据结构的原理及hashMAp 源代码来分析一下。

原理：通过计算输入key的散列值，快速定位value 存储位置。其中最重要部分就是散列值的计算。关于散列值与散列算法，做个简要说明。

   把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

    若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

　 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

　　 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

HashMap 中散列方法如下：

    static int hash(int h) {
        //h 为你要存储key 的散列值，这就是我们自建类要覆盖hashCode重要原因。 
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

HashMap 中能存储key 为null 的值。这是因为

public V put(K key, V value) {
        if (key == null)//单独处理了key 为null情况，将其存储在内部表的第一个位置
            return putForNullKey(value); //
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);//通过hash 值计算value 存储位置。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

    /**
     * Offloaded version of put for null keys
     * 存储key 为null 的value .
     */
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

get 方法：

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());//通过key的hash 值计算，key 存储位置
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

hashmap 中数据结构：

    在hashmap中key - value被包装成Entry 对象并存储在一个Entry[] 数组当中。如下图

存储数据后：

从上图结合hashMap put 方法的源代码。我们可以得出，通过key 读取时，是通过hash 值计算entry 在table 中位置，然后通过遍历Entry 链表找到我们的值。可以整个过程遍历链表是最耗时的操作。如果每个table元素只存储一个Entry。那我们就可以快速找到我们要的value 了。也就是说我们在存储时要尽量将Entry 均匀存储在table中，这就是我们的类要覆盖hashCode 方法的原因。

再看看 HashMap 构造方法

// initialCapacity 存储容量，即table初始化大小
// loadFactor 因子，当存储的数据量大于 initialCapacity * loadFactor时，进行自动扩容，每次扩原来的一倍
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

其他两个构造方法都是使用默认的参数调用这个构造方法。默认的容量为16，因子为0.75。

说的好像断断续续，总结一下：

1、我们的对象要实现自己的hashCode 方法，可以用apache commons 包中的方法来辅助生成。如实现时要注意：当一个对象被存储在Hashset中后，如果修改参与计算hashcode有关的字段，那么修改后的hashcode的值就与一开始存储进来的hashcode的值不同了，这样contains无法通过hashcode找到该元素，也无法删除，从而导致造成的内存泄露。这也要求使用者在将对象存储到hashMap 后key值对象不允许在更改，特别是更改参与hashcode计算的字段。建议使用String 及基本类型包装类作为KEY

2、如果要存储的数据大小已知。初始化时将初始容量定为数据大小。

3、存储对象时，存储的都是引用。

4、该类是非线程安全的。多线程情况需注意。