深耕JavaSe - HashMap底层源码分析

深耕JavaSe - HashMap底层源码分析

文章目录

• • 1. 简介
  • 2. 属性
  • 3. 单链表节点类Node
  • 4. 红黑树节点类
  • 5. 构造函数
  • • 5.1 HashMap()
    • 5.2 HashMap(int initialCapacity)
    • 5.3 HashMap(int initialCapacity, float loadFactor)
  • 6. 计算key的hash值
  • 7. 添加元素 put(K key, V value)
  • 8. 扩容 resize()
  • 10. 链表转化为红黑树 treeifyBin()
  • 11. 获取元素 get(Object key)
  • 12. 相关面试问题

1. 简介

① JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，当一个元素放入集合时，会计算key的Hash值，即hash(key)，然后和数组的大小进行按位与运算计算一个桶下标（索引）。将key放入数组对应的桶下标索引处，将key尽可能的分散在不同的桶下标下面，可以让查找更加快速，时间复杂度为O(1)， 但是不同的key也有可能计算出相同的桶下标（索引），此时需要通过equals()方法来查找key，虽然查找性能会有损失，但是可以解决桶下标冲突。

死链的并发问题会发在扩容的时候，随着数组内元素越来越多，必然导致链表的长度也越来越长，查找性能就会受到影响，jdk7和jdk8都是在数组长度超过一个阈值时就会发生扩容，这个阈值就是数组的长度的四分之三（12）发生扩容，扩容的方式会重新计算桶下标，让容量翻倍。

② JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

哈希冲突：两个不同的key经过hash函数计算出相同的桶下标索引

补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些 *** 作来保持平衡 。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。具体可以参考 treeifyBin方法。

当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变的更高效。

③ 小结：

（1）存取无序的

（2）键和值位置都可以是null，但是键位置只能是一个null

（3）键位置是唯一的，底层的数据结构控制键的

（4）jdk1.8前数据结构是：链表 + 数组 ； jdk1.8之后是 ： 链表 + 数组 + 红黑树

（5）阈值(边界值) > 8 并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

（6）HashMap 的实现不是同步的，这意味着它不是线程安全的。

---

2. 属性

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


static final int MAXIMUM_CAPACITY = 1 << 30;


static final float DEFAULT_LOAD_FACTOR = 0.75f;


static final int TREEIFY_THRESHOLD = 8;


static final int UNTREEIFY_THRESHOLD = 6;


static final int MIN_TREEIFY_CAPACITY = 64;


transient HashMap.Node[] table;


transient Set> entrySet;


transient int size;


transient int modCount;


int threshold;


final float loadFactor;

• 容量 ： 为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以将链表转化为红黑树
• 装载因子：用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
• 树化： 当容量大于64且链表的长度大于8时进行树化，当链表的长度小于6时将红黑树转为为链表。

---

3. 单链表节点类Node

Node是一个典型的单链表节点，其中，hash用来存储key计算得来的hash值。

static class Node implements Entry {
    final int hash;
    final K key;
    V value;
    HashMap.Node next;

    Node(int hash, K key, V value, HashMap.Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

---

4. 红黑树节点类

TreeNode是一个典型的树型节点，其中，prev是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。

static final class TreeNode extends java.util.linkedHashMap.Entry {
    HashMap.TreeNode parent;
    HashMap.TreeNode left;
    HashMap.TreeNode right;
    HashMap.TreeNode prev;
    boolean red;

    TreeNode(int hash, K key, V val, HashMap.Node next) {
        super(hash, key, val, next);
    }
}

5. 构造函数 5.1 HashMap()

空参构造方法，全部使用默认值。

public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR;
}

5.2 HashMap(int initialCapacity)

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

5.3 HashMap(int initialCapacity, float loadFactor)

 
public HashMap(int initialCapacity, float loadFactor) {
    // 检查传入的初始容量是否合法
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 如果传入的初始容量大于最大容量，将初始容量设置为最大容量 MAXIMUM_CAPACITY --> 2的30次方
    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);
}


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;
}

6. 计算key的hash值

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

7. 添加元素 put(K key, V value)

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


final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 表示存储Map集合中元素的数组
    HashMap.Node[] tab;
    // 定义一个链表节点变量
    HashMap.Node p;
    int n;
    int i;
    // 如果tab==null，说明桶的数量为0，对tab数组进行初始化
    if ((tab = table) == null || (n = tab.length) == 0){
        n = (tab = resize()).length;
    }
    // i = (n - 1) & hash ：计算该元素应该添加到哪个桶中
    // 如果这个桶中还没有元素，则把这个元素放在桶中的第一个位置
    if ((p = tab[i = (n - 1) & hash]) == null) {
        // 将这个元素(key,value)构造成Node节点，添加到桶的第一个位置
        tab[i] = newNode(hash, key, value, null);
    } else {
        // 如果这个桶中已经有元素存在了
         HashMap.Node e;
         K k;
        
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
            e = p;
        } else if (p instanceof HashMap.TreeNode){
            // 如果第一个元素是树节点，则调用树节点的putTreeval插入元素
            e = (( HashMap.TreeNode)p).putTreeval(this, tab, hash, key, value);
        } else {
            // 否则第一个元素就是链表节点，遍历桶中的链表，然后将节点添加到链表中
            // binCount用于存储链表中元素的个数
            for (int binCount = 0; ; ++binCount) {
                // 如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最后插入一个新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果插入新节点后链表长度大于8，则判断是否需要转化为红黑树，因为第一个元素没有加到binCount中，所以这里为TREEIFY_THRESHOLD - 1
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果待插入的key在链表中找到了，则退出循环
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                    break;
                }
                p = e;
            }
        }
        // 如果找到了对应key的元素
        if (e != null) { // existing mapping for key
            // 记录下旧值
            V oldValue = e.value;
            // 判断是否需要替换旧值
            if (!onlyIfAbsent || oldValue == null){
                e.value = value;
            }
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 到这里了说明没有找到元素
    // 没有找到元素，改动次数加1
    ++modCount;
    // 元素数量加1，判断是否需要扩容
    if (++size > threshold){
        resize();
    }
    afterNodeInsertion(evict);
    // 没找到元素返回null
    return null;
}

1. 计算key的hash值；

2. 如果桶（数组）数量为0，则初始化桶；

3. 如果key所在的桶没有元素，则直接插入；

4. 如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（8）处理，判断是否需要替换旧值，并直接返回旧值；

5. 如果第一个元素是树节点，则调用树节点的putTreeval()寻找元素或插入树节点；

6. 如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中；

7. 如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化；

8. 如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值；

9. 如果插入了元素，则数量加1并判断是否需要扩容；

---

8. 扩容 resize()

当HashMap中的元素个数超过数组大小 *loadFactor时，就会进行数组扩容，loadFactor的默认值是0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16×0.75=12（这个值就是阈值或者边界值threshold值）的时候，就把数组的大小扩展为2×16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的 *** 作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。

当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。

进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。

怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：

元素在重新计算hash之后，因为n变为2倍，那么n-1的标记范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

说明：5是假设计算出来的原来的索引。这样就验证了上述所描述的：扩容之后所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。如果新的索引高位为0那么存储在原来索引位置，如果高位是1那么存在原来索引+旧的数组长度位置。

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。可以看看下图为16扩充为32的resize示意图：

正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。

final HashMap.Node[] resize() {
    // 得到当前数组
    HashMap.Node[] oldTab = table;
    // 旧容量：当前数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧扩容阈值（门槛）：默认是12 (16*0.75)
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // 如果旧容量达到了最大容量，则不再进行扩容，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        // 如果旧容量没超过最大容量，并且旧容量大于默认初始容量（16），则数组容量就扩充为原来的2倍，newCap = 16*2=32
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY){
            // 扩容门槛也扩大为原来的2倍
            newThr = oldThr << 1; // double threshold
        }
    } else if (oldThr > 0) {
        // 使用带参构造函数创建的map，第一次插入元素会走到这里，则把旧门槛赋值给新容量
        newCap = oldThr;
    } else {
        // 如果旧容量，旧扩容门槛都是0，说明还未初始化过
        // 使用空参构造函数创建的map，第一次插入元素会走到这里：直接使用默认值
        // 初始化容量为默认容量，扩容门槛为：（默认容量*默认装载因子）
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16*0.75=12
    }
    if (newThr == 0) {
        // 如果新扩容门槛为0，则计算为容量*装载因子，但不能超过最大容量
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    // 扩容阈值为newThr
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 新建一个新容量的数组，数组大小为newCap
    HashMap.Node[] newTab = (HashMap.Node[])new HashMap.Node[newCap];
    // 把桶赋值为新数组
    table = newTab;
    // 判断旧数组不等于空，遍历旧的哈希表，重新计算桶里元素的新位置,把每个bucket都移动到新的buckets中
    if (oldTab != null) {
        // 遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            HashMap.Node e;
            // 如果桶中第一个元素不为空，赋值给e
            if ((e = oldTab[j]) != null) {
                // 清空旧桶，便于GC回收
                oldTab[j] = null;
                if (e.next == null){
                    // 如果这个桶中只有一个元素，则计算它在新桶中的位置并把它搬移到新桶中
                    // 因为每次都扩容两倍，所以这里的第一个元素搬移到新桶的时候新桶肯定还没有元素
                    newTab[e.hash & (newCap - 1)] = e;
                } else if (e instanceof HashMap.TreeNode){
                    // 如果第一个元素是树节点，则把这颗树打散成两颗树插入到新桶中去
                    ((HashMap.TreeNode)e).split(this, newTab, j, oldCap);
                } else { // preserve order
                    // 如果这个链表不止一个元素且不是一颗树
                    // 则分化成两个链表插入到新的桶中去
                    // 比如，假如原来容量为4， 3、7、11、15这四个元素都在三号桶中
                    // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
                    // 也就是分化成了两个链表
                    HashMap.Node loHead = null, loTail = null;
                    HashMap.Node hiHead = null, hiTail = null;
                    HashMap.Node next;
                    do {
                        next = e.next;
                        // (e.hash & oldCap) == 0的元素放在低位链表中
                        // 比如，3 & 4 == 0
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null){
                                loHead = e;
                            } else{
                                loTail.next = e;
                            }
                            loTail = e;
                        } else {
                            // (e.hash & oldCap) != 0的元素放在高位链表中
                            // 比如，7 & 4 != 0
                            if (hiTail == null){
                                hiHead = e;
                            } else{
                                hiTail.next = e;
                            }
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历完成分化成两个链表了
                    // 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1. 如果使用的是空参构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12；

2. 如果使用的是带参构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方；

3. 如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍；

4. 创建一个新容量的桶；

5. 搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置；

---

10. 链表转化为红黑树 treeifyBin()

final void treeifyBin(HashMap.Node[] tab, int hash) {
    int n, index;
    HashMap.Node e;
    // 如果桶数量小于64，直接扩容而不用转化为红黑树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY){
        resize();
    // 执行到这里说明哈希表中的数组长度大于阈值64，开始将链表转化为红黑树
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
        HashMap.TreeNode hd = null, tl = null;
        do {
            // 把所有节点换成树节点
            HashMap.TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 让桶中的第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树,而不是链表数据结构了
        if ((tab[index] = hd) != null){
            hd.treeify(tab);
        }
    }
}

11. 获取元素 get(Object key)

public V get(Object key) {
    HashMap.Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final HashMap.Node getNode(int hash, Object key) {
    HashMap.Node[] tab;
    HashMap.Node first, e;
    int n; K k;
    // 如果桶的数量大于0，并且待查找的key所在的桶的第一个元素不为空
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // always check first node
        // 检查第一个元素是不是要查的元素，如果是直接返回
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) {
            return first;
        }
        if ((e = first.next) != null) {
            // 如果第一个元素是树节点，则按树的方式查找
            if (first instanceof HashMap.TreeNode)
                return (( HashMap.TreeNode)first).getTreeNode(hash, key);
            // 否则就遍历整个链表查找该元素
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                    return e;
                }
            } while ((e = e.next) != null);
        }
    }
    return null;
}

1. 计算key的hash值；

2. 找到key所在的桶及其第一个元素；

3. 如果第一个元素的key等于待查找的key，直接返回；

4. 如果第一个元素是树节点就按树的方式来查找，否则按链表方式查找；

---

12. 相关面试问题

1、为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

因为红黑树需要进行左旋，右旋，变色这些 *** 作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询 *** 作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

2、为什么链表改为红黑树的阈值是 8?

是因为泊松分布，我们来看作者在源码中的注释：

 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
  more: less than 1 in ten million

理想情况下使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了 8，是根据概率统计而选择的。

3. 默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？

int threshold;             // 容纳键值对的最大值
final float loadFactor;    // 负载因子
int modCount;  
int size;  

Node[] table的初始化长度length（默认值是16），Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳键值对的最大值。threshold = length * Load factor=12。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空间比较特殊的情况下 ：

• 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值 。
• 相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的 *** 作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash *** 作的次数。如果初始容量大于最大条目数除以负载因子，rehash *** 作将不会发生。

4. HashMap 中 key 的存储索引是怎么计算的？

首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。

5. HashMap中hash函数是怎么实现的？还有哪些hash函数的实现方式？

key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从**-2147483648到2147483648**。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。

但问题是一个40亿长度的数组，内存是放不下的。你想，HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的，用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标，这个数组下标的范围为[0,table.length]：

public int hash(Object key){
    return key.hashCode() % table.length;
}

为了提高效率，我们将求余运算%改成了&与运算，但是前提就是数组的长度为2的幂次方：

public int hash(Object key){
    return key.hashCode() & (table.length-1);
}

让数组的长度为2的幂次方，是因为让key的hash值与全1（数组长度-1正好相当于一个“低位掩码”）进行&运算，其结果一定小于数组长度：

1          2^1-1
11		   2^2-1	
111        2^3-1
1111       2^4-1

& *** 作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做& *** 作如下，结果就是截取了最低的四位值。则可以看出我们在通过hash值计算索引时，仅仅利用了hash值的低位信息 ：

    10100101 11000100 00100101
&   00000000 00000000 00001111
----------------------------------
    00000000 00000000 00000101    //高位全部归零，只保留末四位

为了充分利用hash值的所有信息，即既利用低位信息，也利用高位信息，使用了>>>与^：

    h         1011 0110 0011 1001 0110 1111 1100 1010    key的hash值
    h >>>16   0000 0000 0000 0000 1011 0110 0011 1001	 key的hash值无符号右移16位
-----------------------------------------------------------------------------------
^			  1011 0110 0011 1001 1101 1001 1111 0011	 将两者进行异或^运算	 	              

右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

因此，良好的哈希函数可以让hash值更加均匀分布，减少哈希冲突的次数，从而提升哈希表的性能。不然，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突。

6. HashMap 的put方法流程

1. 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
2. 如果数组是空的，则调用 resize 进行初始化；
3. 如果没有哈希冲突直接放在对应的数组下标里；
4. 如果冲突了，且 key 已经存在，就覆盖掉 value；
5. 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
6. 如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。

7. JDK1.7 和1.8 的put方法区别是什么？

链表插入元素时，JDK1.7 使用头插法插入元素，在多线程的环境下有可能导致环形链表的出现，扩容的时候会导致死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，但JDK1.8 的 HashMap 仍然是线程不安全的，具体原因会在另一篇文章分析。

8. HashMap 的扩容方式？

Hashmap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无法自动扩容的，方法是将 Hashmap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。

9. 扩容在JDK1.8中有什么不一样？

1. resize 之后，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）。不需要像 JDK1.7 的实现那样重新计算hash ，只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”。这个设计非常的巧妙，省去了重新计算 hash 值的时间。

2. JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，使用尾插法。

10. 还知道哪些hash算法？

Hash函数是指把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存。 比较出名的有MurmurHash、MD4、MD5等等。

11. 传统hashMap的缺点，1.8为什么引入红黑树？

JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。 当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

12. HashMap中hash函数是怎么实现的？

对于key的hashCode做hash *** 作，无符号右移16位然后做异或运算。还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。

13. 当两个对象的hashCode相等时会怎么样？

会产生哈希碰撞，若key值内容相同则替换旧的value.不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储。

14. 何时发生哈希碰撞和什么是哈希碰撞，如何解决哈希碰撞？

只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。

15. 如果两个键的hashcode相同，如何存储键值对？

hashcode相同，通过equals比较内容是否相同。如果hashcode相同，则新的value覆盖之前的value。如果hashcode不相同，则将新的键值对添加到哈希表中。