HashMap

HashMap和HashTable区别：

• HashTable和HashMap在代码实现上，基本上是一样的，和Vector与Arraylist的区别大体上差不多，一个是线程安全的，一个非线程安全，因而也带来了效率问题。HashMap的键和值都允许有null值存在，而HashTable则不行。
• HashTable基于Dictionary类，HashMap基于map
• 扩容策略：HashMap默认初始化数组的大小为16，HashTable为11。前者扩容时乘2，使用位运算取得哈希，效率高于取模。而后者为乘2加1，都是素数和奇数，这样取模哈希结果更均匀。

与ConncurrentHashMap区别

• 线程安全与否
• HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

构造函数：

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

只是初始化了一个负载因子，默认为0.75f。一个意外的东西，如果使用指定了capacity的构造函数，则hashMap拿这个capacity只是设置了threshold，作为扩容的时候时候用

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);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

当中的threshold并不是直接为initialCapacity，而是大于等于initialCapacity且最近的2的整数次幂的数，使用到了其一个工具

寻找大于等于输入参数且最近的2的整数次幂的数

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这就是个算法题，然而变成了hashmap的工具类，是比较秀的

思路大概是这样，从左往右的第一个1开始，赋值后面所有的位均为1，举个例子（n=01000000）：

1. n = 01000000，则n >>> 1为00100000，再与原本的n或运算得到01100000
2. n = 01100000，则n >>> 2为00011000，再与原本的n进行或运算得到01111000
3. 依此类推...

加载因子：

size：表示HashMap中存放KV的数量（为链表和树中的KV的总和）。

loadFactor（加载因子）：hashMap在其容量自动增加之前可以达到多满的一种尺度。计算HashMap的实时装载因子的方法为：size/capacity。

threshold：threshold=capacity*loadFactor。当HashMap的size大于threshold时会执行扩容resize操作，默认值为16，之后按照2倍进行扩容。

hashMap的加载因子（initCapacity和loadFactor）是影响其迭代性能（get和put）的重要指标，大的值可以减少空间消耗但是会导致效率变低，太小则反之

transient Node<K,V>[] table：

先看看Node类

H1.jpg

当中的equals方法如下

public final boolean equals(Object o) {
    if (o == this)
        return true;
    if (o instanceof Map.Entry) {
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        if (Objects.equals(key, e.getKey()) &&
            Objects.equals(value, e.getValue()))
            return true;
    }
    return false;
}

其比较是直接调用Objects的equals方法，注意不是Object，不过也差不多，点进去看发现就是Object中equals方法的一个包装，最终都会使用到原生的equals方法，除非覆盖

public static boolean equals(Object a, Object b) {
    return (a == b) || (a != null && a.equals(b));
}

可以看到，每一个节点都有key,value,hash，next，这个hash是根据什么字段生成的呢？那就来看看添加元素的put方法

put(key ,value)添加元素

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

调用了hash和putVal，先看看hash

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

可以看到，hash的生成跟key相关，而且是调用了key的hashCode，所以，再次强调，重写equals方法的时候，一定要重写hashCode方法，因为key是基于hashCode来处理的

然而，HashMap又自己写了一个hash方法来计算hash值，不用key本身的hashCode方法，也就是只使用产生出来的hashCode的高16位，这样做是为了对元素的hashCode进行再散列，减少散列冲突

再看看putVal方法，代码有点长。

H2.jpg

一步步来，当放入第一个元素的时候，会触发resize（hashmap的table能够是长度为0的数组），resize函数比较长，讲讲代码的实现过程。

resize()：

int oldCap = (oldTab == null) ? 0 : oldTab.length;

判断原有的table是否为null，不是则默认扩大为原容量的2倍，并且重排底层数组元素，但需要先检查原容量以及扩大后的容量是否在MAXIMUM_CAPACITY范围内；是的话则变为DEFAULT_INITIAL_CAPACITY=16；再下去，如果oldTab不为空，复制，否则，返回新对象

好了，返回putVal，继续执行，看到代码

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

通过(n - 1) & hash计算得到对象的位置，也就是只取hash的后n-1位，如果为null，插入元素；如果得到的对象位置不为null，也就是产生冲突，接下来就解决这种情况，

H3.jpg

红框中，原代码在解决冲突的时候，有这么关键一句

p.next = newNode(hash, key, value, null);

也就是在冲突节点的位置，变成了单向链表
在红框中，还有两行重要的代码

if (binCount >= TREEIFY_THRESHOLD - 1) //当binCount>=TREEIFY_THRESHOLD-1
      treeifyBin(tab, hash);//把链表转化为红黑树

[图片上传失败...(image-dc128-1525784747687)]

在JDK1.7及以前的版本中，HashMap里是没有红黑树的实现的，在JDK1.8中加入了红黑树是为了防止哈希表碰撞攻击，当链表链长度为8（这里只是举例）时，及时转成红黑树，提高map的效率。

如果这个桶中bin的数量小于TREEIFY_THRESHOLD当然不会转化成树形结构存储；如果这个桶中bin的数量大于了 TREEIFY_THRESHOLD ，但是capacity小于MIN_TREEIFY_CAPACITY 则依然使用链表结构进行存储，此时会对HashMap进行扩容；如果capacity大于了MIN_TREEIFY_CAPACITY ，则会进行树化。

HashMap的最底层是数组来实现的，数组里的元素可能为null，也有可能是单个对象，还有可能是单向链表或是红黑树。（数据+红黑树）

H4.jpg

如果碰到了key相同的，也就是红框2执行，此时会跳到5执行，并且覆盖相应节点的value值

再来看看putTreeVal的函数

H5.jpg

思想上跟链表一样，遍历节点，如果找到节点，则返回节点，否则，添加新节点

总结一下

在hashMap里面put元素，有以下重要步骤：

1. 计算key的hash值，((n-1) & hash)算出元素在底层数组中的下标位置。
2. 通过下标位置定位到底层数组里的元素（可能是链表也可能是树）。
3. 取到元素，判断放入元素的key是否==或equals当前位置的key，成立则替换value值，返回旧值。
4. 如果是树，循环树中的节点，判断放入元素的key是否==或equals节点的key，成立则替换树里的value，并返回旧值，不成立就添加到树里。
5. 否则就顺着元素的链表结构循环节点，判断放入元素的key是否==或equals节点的key，成立则替换链表里value，并返回旧值，找不到就添加到链表的最后。

以上中，hashMap的判相等

会经过3个步骤

1. hashCode比较
2. key比较

参考
https://zhuanlan.zhihu.com/p/28501879
https://zhuanlan.zhihu.com/p/28587782