HashMap简介

HashMap是一个由数组+链表/红黑树组成的数据结构，主要是以key->value的形式对数据进行存储。在JDK 1.7及以前的版本中，是由数组+链表的形式组成，在JDK 1.8及之后的版本中当链表长度达到8时就会将链表转换为红黑树

JDK 1.7

HashMap链表.png**

JDK 1.8

截屏2020-12-13 下午3.05.22.png

基本成员变量分析

节点元素

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.     final int hash;    
  3.     final K key;    
  4.     V value;    
  5.     Node<K,V> next;
  6.     Node(int hash, K key, V value, Node<K,V> next) {
  7.         this.hash = hash;        
  8.         this.key = key;        
  9.         this.value = value;        
  10.         this.next = next;    
  11.     }
  12. }

节点内部类，hashmap中存储的key->value对都会转化成Node。例如：map.put(“key1”, “value1”)，则会生成一个Node<”key1”, ‘value1”>对象存储到hashmap中

数组

transient Node<K,V>[] table;

初始化数组长度

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

数组的默认长度为16

负载因子

final float loadFactor;

默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子大小默认为0.75，即当hashmap中的元素达到这个值时需要进行扩容。例如：数组长度为16的hashmap，当其中的元素个数达到16 * 0.75 = 12时（当要添加第13个元素时）需要对hashmap进行扩容

hashmap元素个数

transient int size;

表示hashmap中的元素个数，当我们往hashmap里添加一个元素的时候就会对size进行+1

扩容阈值

int threshold;

threshold = table.length loadFactor。当hashmap中的元素个数超过这个值时就需要对hashmap进行扩容。例如：当前table大小为16，负载因子为0.75，即当前threshold为16 0.75 = 12，其中元素个数为12，当我们需要再往hashmap中添加元素时就需要对其进行扩容

hash运算

static final int hash(Object key) {
    int h;    
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

当我们往hashmap中添加元素时需要对元素的key进行hash算法生成一个32位的hashcode，即(hashcode)异或(hashcode右移16位)
hashcode右移16位就是将低16位的值舍弃，然后将高16位的值移到低16位，高16位用0补齐。例如：一个key对应生成的hashcode值是
原hashcode 1111 1111 1111 1111 0000 1111 0000 0101
右移16位后 0000 0000 0000 0000 1111 1111 1111 1111
原hashcode^右移16位后 1111 1111 1111 1111 1111 0000 1111 1010
对原hashcode右移后再进行异或操作主要是让高位也可以参与运算

put/get方法原理

当我们向hashmap中put元素时（无hash冲突时）

  1. 将key值进行hash运算得到hash值
  2. 将得到的hash值跟数组长度进行与运算。相当于取模（取模运算速度比与运算慢）。即可以获取到一个0~table.length - 1的值index。例如：table长度为16，则可以获取到一个0~15之间的一个数
  3. 将步骤3中获取到的index值作为数组下标，将新加入的节点放到table[index]中

    无hash冲突时

    put方法

截屏2020-12-13 下午4.42.23.png

get方法

截屏2020-12-13 下午5.08.35.png

hash冲突

  1. 2个不同的key但是经过hash运算后得到相同的值（发生概率较低）
  2. 2个不同的key经过hash运算后得到不同的值，但是该值与table.length - 1进行与运算后得到的下标值相同

    put方法

    下图中先在map中put了name1 -> 张三，其在下标1的位置上，此时需要put name2 -> 李四，此时name2通过hash运算再跟（table.length - 1）进行与运算后得到的下标也是1，那么，name2 -> 李四这个节点就会作为链表拼接在name1 -> 张三后面

截屏2020-12-13 下午4.55.05.png

get方法

截屏2020-12-13 下午5.19.03.png

红黑树解决hash冲突问题

链表是为了解决hash冲突的问题。但是在hash冲突很严重的情况下， 特别在极端情况下可能会退化成链表，而链表的查询时间复杂度是O(N)的，所以为了提升性能能当链表的长度达到8时就会转换成红黑树（时间复杂度O(logN)）
既然红黑树的查询性能优于链表为什么在hash冲突时直接使用红黑树呢？
其实主要是因为红黑树需要额外的内存存储左子节点、右子节点及父节点的引用，所以占用的内存较多
为什么在链表长度为8（插入第9个元素时）的时候对其专为红黑树呢？源码中的解释为，当链表长度达到8时的概率非常低，所以选择了8

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are: 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

扩容机制

hashmap在元素个数达到扩容阈值（threshold）时，会将数组的长度变为原来的2倍。例如：一个初始化长度为16的hashmap，当节点的元素个数达到12的时候就会申请一个新的数组，然后将原来的hashmap中的元素重新映射到新的数组对应的位置上，并且链表中的元素会逆序插入新的hashmap中。示意图如下

截屏2020-12-13 下午9.16.11.png

扩容机制示意图

循环链表问题

在JDK 1.7中hashmap在并发情况下会产生循环链表，导致cpu 100%。并发情况下可以使用ConcurrentHashMap。其扩容方法如下

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

hashmap扩容源码
还是以扩容机制是以图中扩容前的数据为例，此时map中有元素:(1, A) -> (3, C)，（2, B）
现在我们假设有2个线程并发执行，而且此时需要对map进行库容

序号 线程1 线程2
1 线程1执行到上述源码第12行，Entry next = e.next;此时线程1让出cpu资源
2 此时线程2对该map进行扩容，并且完成后让出cpu资源。此时map中的数据为（假设扩容后数据还在原来的位置）
(3, C) -> (1, A), (2, B)
3 此时由于头结点是（3, C），所以将（1，A）的next元素指向（3，C）。由于（3， C）的next原本指向了（1， A），而此时又把（1, A）的next指向了（3, C）由此就产生了循环链表（3, C）-> (1, A) -> (3, C)

为什么数组长度一定是2的次方

为了减少hash冲突的概率。因为这样table.length - 1的二进制数一定是高位是0，而地位全是1。例如：十进制数15对应的二进制数是 0000 0000 0000 0000 0000 0000 0000 1111。如果不满足上述条件，例如：十进制数14对应的二进制数是0000 0000 0000 0000 0000 0000 0000 1110，难么当一个hash值与这个数进行与操作时，hash值的最后一位得到的结果一定是0，这样就会破坏hash算法随机分布的特性，从而增加hash冲突的风险。
同时数组长度是2的次方，那么当扩容后元素要么在原来的位置没动，要么在原来的位置 + 原来的数组长度的下标位置下。例如：数组长度为16的map，在扩容为长度为32时，原来在下标1位置下的元素，要么还在下标1的位置，要么在1 + 16 = 17的位置下