hashmap详解

介绍

JDK1.8对HashMap底层的实现进行了优化，引入红黑树的数据结构和扩容的优化等。
它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度。
HashMap最多只允许一条记录的键为null，允许多条记录的值为null。非线程安全。
如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

avatar

内部原理

HashMap是采用数组+链表+红黑树实现的。
HashMap里面初始时是用Node[] table的方式存放数据的，Node实现了Map.Entry的接口，里面存放了map的key，hashcode值，还有map的值，以及链表的下一节点的指针，还有其他一些获取值的方法。

源码如下

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

hashCode()方法是通过hash算法计算得到一个hashcode，通过hashcode来设置在数组中的位置。

HashMap的字段：

int threshold; 
final float loadFactor;
int modCount; 
int size;

Node[] table的初始化长度length(默认值是16)，
Load factor为负载因子(默认值是0.75)，
threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。

在HashMap中，哈希桶数组table的长度length大小必须为2的倍数。HashMap采用这种设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。

Hash算法

Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

hashCode是通过把任意长度的输入通过散列算法变成固定长度的输出，散列算法就是一些数学函数，是一种消息摘要的的函数。
hashcode不一定是均匀的，有可能会在一边上面堆积数据，将高位的16位和低位的16位进行异或，利用异或的特性保证hashcode的值是均匀的。
处理过后的hashcode并不是都在数组长度里面，所以我们就需要取模运算来保证在数组范围里。

1
2
3

static int indexFor(int h, int length) { 
     return h & (length-1);
}

而HashMap中的取模运算是h & (length-1)这样的，因为和取模的结果是一样的，但是&的速度比%要快的多，但是条件是要length是2的倍数才行。

扩容机制

 void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;         
     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
         return;
     }
  
     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
     transfer(newTable);                         //！！将数据转移到新的Entry数组里
     table = newTable;                           //HashMap的table属性引用新的Entry数组
     threshold = (int)(newCapacity * loadFactor);//修改阈值
}

transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                e.next = newTable[i]; //标记[1]
                newTable[i] = e;      //将元素放在数组上
                e = next;             //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了

补充点

扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

负载因子是代表着，如果数组中的数据与数组大小的比例，如果超过了负载因子就进行扩容。

链表默认是8是因为通过泊松分布的计算，来计算hashcode在同一个位置的概率，8的概率是非常小的，接近于不可能发生的，但是还是要有处理的措施。

节点出现的频率在hash桶中遵循泊松分布，也就是说用0.75作为负载因子，每个碰撞位置的链表长度超过8个是几乎不可能的，但是总容量是16，而负载因子为0.5（数组数据为8时）时又对空间有一半的浪费，hash容器指定初始容量尽量为2的幂次方，所以采用0.75（数组数据为12时）是空间和时间成本的一种折中。

泊松分布的概率表：
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006