Java中的HashMap原理及运用 - JAVA

HashMap在HashTable上的改进基本有3点，*安装了Map的接口，而不是JDK1.0的Dictionary，Map接口更丰富合理。*可以接受null键和null值。*去掉同步，速度大幅提高(同步使用的是ConcurrentHashMap，几个改进：段锁、不变性、Unsafe的CAS操作、弱一致迭代器)。

        if (key == null)
            return putForNullKey(value);

使用的hash映射的原理，既然是hash，就不免有冲突，HashMap使用链表的方式解决冲突。冲突时新元素指向头结点，新元素放进数组里。有点LRU是Least Recently Used 近期最少使用算法的意思。Entry第四个参数为指向的元素。

        Entry
  
    e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);

关于扩容，需要扩容时扩两倍，什么时候扩容呢？hash算法在接近桶上限时性能急剧下降。所以一定要在离桶上限有段距离时扩容。这就是loadfactor负载系数。默认HashMap桶上限是16，负载为0.75。也就是装12个。capacity桶上限、loadFactor负载、threshold门限值。

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];

和其它集合类一样，可以在初始化的时候初始化大小以免后面扩容。HashMap在设置大小时是设置比参数大的第一个2的指数次方的数。为什么要这样呢？肯定和性能有关，因为hashCode是一个int数，所以应该把它的范围限制到桶上限的大小。在范围限制时使用'与'操作效率将会更高，也就是hashCode & (length-1)。假如长度为16，16-1=15。所以就是与上1111。

//初始化的时候
// Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
.............................................
 return h & (length-1);//计算hash的函数

Object中和HashMap关切最大就是equals和hashCode两个方法。HashMap也是为什么会有equals和hashCode契约的关系。这是因为HashMap使用hashCode来存储元素。然后在get取元素时，先通过hashCode找到位置。再遍历位置上的链表，直到key.equals(k)返回true时。所以，重写了equals必须重写hashCode相对应。

            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;

HashMap获得hashCode(变量h)之后又进行了一堆右移和异或运算。为什么呢？ h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); 上述就是源代码。这就相当于int有几个分布区间。经过位移把h分别移位到几个分布区间里面后，再进行异或的合并。这是因为HashMap需要一个均匀分布的散列值。考虑一种情况，hashCode都主要集中在高位的，那当映射到桶上限时，会hashCode & (length-1)。也就是只取低位。那所有的元素都要冲突。这是一个可怕的现象。所以，此项操作的作用就是让低位的hashCode能代表整个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);

关于hashCode的计算。第一点，hashCode的最大的期望就是计算的值是在int范围随机分布的。就是把所有的可能映射到整个int范围上来。比如long计算(int)(f^(f>>>32))。第二点，必须要考虑到类中所有元素的改变，比如String的计算，s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]。也就是for (int i = 0; i < len; i++) h = 31*h + val[off++]。

            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

问题又来了，为什么String的hashCode的计算的基数是31呢？这个code大小虽然不奢求必须唯一（因为这样通常计算会非常慢），但是要尽可能的不要重复，因此基数要尽量的大。另外，31*N可以被编译器优化为左移5位后减1，有较高的性能。基数还有就是必须得是质数，质数的特性（只有1和自己是因子）能够使得它和其他数相乘后得到的结果比其他方式更容易产成唯一性，也就是hash code值的冲突概率最小。