HashMap底层原理（面试问到你哭）

Map方面的面试题，HashMap必问 ，重点掌握！！！个人能力有限，如有出入，恳请指教🙏

文章目录

• • 一、HashMap简介
  • • • HashMap集合底层的数据结构简介
  • 二、HashTable简介
  • 三、ConcurrentHashMap简介
  • 四、面试可能遇到的问题：
  • • 1. HashMap实现原理
    • 2. HashMap在JDK7 和JDK8有哪些不同？底层实现？
    • • ==JDK8之前==
      • ==JDK8==
      • ==JDK8之前于JDK8之后的区别==
    • 3. HashMap的put方法具体流程？
    • 4. HashMap的扩容机制如何实现？
    • 5. HashMap怎么解决hash冲突的
    • 6. 为什么像String,Ingeter这种包装类适合作为Map的key
    • 7. 能否使用任意类作为Map的key，应该怎么办？
    • 8. HashMap为什么不是直接使用hashCode()后的值直接作为table下标
    • 9. HashMap的长度为什么是2的幂次方
    • 10. HashMap和TreeMap如何选择
    • 11. HashMap和HashTable 有何区别
    • 12.CocurrentHashMap底层如何实现？实现原理是什么？
    • 13. HashMap和CocurrentHashMap有何区别
    • 14. HashTable和CocurrentHashMap有何区别
  • 五、面试可能遇到的其它问题：
  • • 1. 为什么不直接使用hashCode计算hash值，还要经过右移16位且异或的操作？
    • 2. Hash算法是如何实现的？
    • 3. 为什么是线程不安全？
    • 4. HashMap的数据结构是什么？
    • 5. HashMap是如何解决hash碰撞的？
    • 6. HashMap的get方法是怎么实现的？
    • 7. 拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？
    • 8. 默认加载因子为什么是0.75
    • 9. HashMap桶中链表转红黑树为什么选择数字8？
    • 10. HashMap的resize()扩容机制？

一、HashMap简介

HashMap基于哈希表的Map接口实现。是以key-value存储形式存在。线程不安全,也就是说多个线程同时对HashMap进行增删改操作时，不能保证数据时一致的。key和value都可以为null，无序存放。

JDK1.8之前由数组+链表组成，数组是HashMap主体，链表则主要是为了解决哈希冲突（两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同）而存在的（“拉链法”解决冲突），JDK1.8之后，当链表长度大于阈值（或者红黑树的边界值，默认为8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

注意：为了提高效率，将链表转换为红黑树前会判断，即使链表阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树，而是选择进行数组扩容。

Java为数据结构中映射定义了一个接口java.util.Map，接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

对其中的HashMap进行介绍：

它根据键的hashCode值进行数据存储，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但数据的存储却是无序的。HashMap最多只允许一条记录的键为null,运行允许多条记录值为null。HashMap非线程安全，如果需要满足线程安全，可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap.

其余学习到再做介绍。

参考：https://zhuanlan.zhihu.com/p/21673805

HashMap集合底层的数据结构简介

JDK1.8之前，数组+链表，创建HashMap对象，会创建一个长度为Entry[] table来存储键值对信息。

JDK1.8之后，数组+链表+红黑树，创建HashMap对象，不是在构造方法中创建了，而是在第一次调用put方法时创建，创建Node[] table用于存储键值对信息。

面试常问：哈希表底层采用何种算法计算哈希值？还有哪些方法可以计算哈希值？

底层采用key的hashCode()的值结合数组长度进行无符号右移（>>>）,按位异或（^）计算hash值，按位与（&）计算索引。

    static final int hash(Object key) {
    //jdk1.8 & jdk1.7
        int h;
        // h = key.hashCode() 为第一步 取hashCode值
    	// h ^ (h >>> 16) 为第二步 高位参与运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
	//返回索引值 
	static int indexFor(int hash, int length) {
     //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

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

关键点介绍：

hashCode（）：Object类的一个本地方法，用于对象的存储和查找的快捷性，在HashMap中发挥重要作用。

返回的是对象存储物理地址的一个映射地址(并不一定等于这个地址)，这个地址有什么用呢？

通过这个地址可以定位到它应该存放的物理位置上，如果这个这个位置上没有元素，则直接插入到此位置；如果位置上有元素，Object中equals()进行判断是不是用一个对象，如果是则不插入，如果不是，则替换这个位置的值。

hashCode()与String 的equals()之间的关系：

如果x.equals(y)返回“true”，那么x和y的hashCode()必须相等。
如果x.equals(y)返回“false”，那么x和y的hashCode()有可能相等，也有可能不等，例如：

System.out.println("重地".hashCode());//1179395不唯一
System.out.println("通话".hashCode());//1179395
计算公式：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]   //不展开

采用以上的hashCode()的优越性？

例如有四个桶来装对象，每个桶装的对象不能重复，A,B,C,D，Person类new出的对象可分别放任何一个桶中，如何判断放进去对象重复？想通过hashCode定位放的桶，然后equals判断是否是同一个对象，考虑要不要放进去，这样比较的就是一个桶中的数据。

倘若没有这个hashCode则需要一个一个桶去比较，对象进行比较是不是同一个对象，效率极低。所以一般要在重新equals方法的同时也重写hashCode.

补充：本地方法是什么？

是由其他语言（如C、C++ 或其他汇编语言）编写，编译成和处理器相关的代码。本地方法保存在动态连接库中，格式是各个平台专用的，运行中的java程序调用本地方法时，虚拟机装载包含这个本地方法的动态库，并调用这个方法。

源码解析：

HashMap：

// key --- value
public V put(K key, V value) {
   
    /* 1.hash(key)：计算key的hash值 2.key 3.value 4.onlyIfAbsent:当键相同时不修改已存在的值 5.true：如果为false,那么数组就处于创建模式中，所以一般为true */
    return putVal(hash(key), key, value, false, true);
}

其中 putVal(hash(key), key, value, false, true);

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
   
    //tab数组：存储键值对 p：当前插入的键值对
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果数组为空 ,则新建一个数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //计算出索引值，并赋值给当前p，并判断是否冲突，如果不冲突则开辟出一个Node空间存储键值对 
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果冲突
    else {
   
        Node<K,V> e; K k;
        //当前的节点p和要插入的节点key相等，就将p值赋给e,用于后面对节点e进行afterNodeAccess(e);
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果当前节点p是红黑树的头节点，则将节点插入到红黑树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //不是红黑树，则遍历链表。如果没找到和要插入节点相同的节点，则插入到链表的最后面，此时如果链表的阈值 >8 且数组的长度 > 64则转换成红黑树，break退出循环
        else {
   
            for (int binCount = 0; ; ++binCount) {
   
                if ((e = p.next) == null) {
   
                    p.next = newNode(hash, key, value, null);
                    //链表长度大于8转换为红黑树进行处理
                    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相等的节点，将value赋值给它，并将e节点进行 afterNodeAccess(e);
        if (e != null) {
    // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //插入成功后判断实际存在的键值对数量size是否大于阈值threshold，如果大于则进行扩容
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容 resize();

final Node<K,V>[] resize() {
   
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //threshold = 初始容量 * 加载因子。也就是扩容的 门槛。相当于实际使用的容量
    int oldThr = threshold;
    int newCap, newThr = 0;
    //
    if (oldCap > 0) {
   
        //如果超过了数组的最大值，则将阈值设置为最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
   
            threshold = Integer.MAX_VALUE;扩容
            return oldTab;
        }
        //如果没有超过则设置为原来的两倍 <<1
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //旧的数组的阈值已经在使用
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //没有初始化阈值，则设置一个默认的阈值
    else {
                  // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    if (newThr == 0) {
   
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({
   "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
   
        // 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
   
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
   
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
    // 链表优化重hash的代码块
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
   
                        next = e.next;
                         // 原索引
                        if ((e.hash & oldCap) == 0) {
   
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
   
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
   
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
   
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap核心get方法：

//注意：返回的是value
public V get(Object key) {
   
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//返回一个键值对
final Node<K,V> getNode(int hash, Object key) {
   
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果表不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
   
        //table[i]首元素则返回first满足key与待查相等，则返回first
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //遍历链表
        if ((e = first.next) != null) {
   
            //如果结构是红黑树，则开始遍历
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
   
                //满足key相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null); //遍历next结束
        }
    }
    return null;
}

二、HashTable简介

哈希表（HashTable）又叫做散列表，是根据关键码值（即键值对）而直接访问的数据结构，HashTable通用也是基于哈希表实现的，同样也是key - value对，其内部也是通过单链表解决冲突问题，容量不足的时候同样会自动增长。
HashTable是JDK 1.0引入的类，是线程安全的，可用于多线程环境中，HashTable同样实现Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。

三、ConcurrentHashMap简介

ConcurrentHashMap结合了HashMap和HashTable的优势，HashMap没有考虑同步机制，HashTable虽然考虑了同步机制，但是每次同步的时候都会锁住整个map，效率低下。而ConcurrentHashMap锁定的稍微细粒度。

四、面试可能遇到的问题：

1. HashMap实现原理

HashMap的底层数据结构是数组+链表，所谓数组+链表指的是每一个数组都维护着一个链表，实现原理是通过哈希函数计算出key散列值，再进行求hash，最后计算索引值。
存储时，如果遇到hash值相同key，即索引值相同，此时将调用equals比较key值是否相等，如果返回true，则覆盖原始值，如果返回false,
将key-value形式数据存入链表中。
获取时，直接找到hash值相等的数组下标，再进一步调用equals判断key值是否相等。

HashMap解决hash的核心就是使用了数组的存储方式，一旦出现冲突的key，就在链表中做进一步的对比再存储。
需要注意的时JDK8对HashMap的实现做了优化，当链表长长度>8，并且数组的长度>64时，会将链表转换成红黑树来提高查询效率，时间辅助度从原来的O(n)---->O(logn)

2. HashMap在JDK7 和JDK8有哪些不同？底层实现？

数组：寻址容易，插入删除数据困难。
链表：寻找困难，插入删除数据容易。
所有将数组和链表结合起来，发挥各自优势，使用一种叫拉链法解决哈希冲突

<mark>JDK8之前</mark>

JDK8之前采用的时拉链法，拉链法将数组和链表结合起来，也就是创建一个数组链表，数组中每一格就是一个链表，若遇到哈希冲突，则将冲突的值存入链表中。

<mark>JDK8</mark>

相比之前的版本，jdk8在解决冲突有了较大的变化，当链表的长度>8并且数组长度>64，将链表转成红黑树，以减少搜索时间。

<mark>JDK8之前于JDK8之后的区别</mark>

JDK8主要解决或优化了一些问题：

1. 引入了红黑树，目的是为了避免因单链表过程而影响查询效率
2. 解决了多线程的死循环问题，但并没有解决线程不安全的问题，还是存在线程安全问题
3. resize扩容优化

hash的计算区别参考：https://blog.csdn.net/hefenglian/article/details/79763634

3. HashMap的put方法具体流程？

请看执行流程图：

方法执行流程：

（1）put方法传入键值

（2）Node<K,V>[] table 是否为空 (JDK1.8),如果为空，则进行resize()扩容

（3）table 不为空，根据hash值+高位右移+异或+取模计算索引值。确定存放的位置。

（4）如果存放的位置为空，则直接插入，++size

（5）如果存放的位置不为空，通过重写Object的equals的方法进行遍历链表中是否存在相等的key

（6）若存在相等的，则直接覆盖value值

（7）否则判断链表的阈值是否>8 ,数组长度是否>64(满不满足生成红黑二叉树)，若满足，则将键值对插入红黑二叉树中

（8）如果不满足，则开始遍历链表插入，如果插入后链表长度 > 8且table长度 > 64,则转换称红黑树后插入

（9）倘若仍不满足红黑树，则遍历链表插入，遇到相同的key,覆盖value插入

4. HashMap的扩容机制如何实现？

1. 在jdk8中，resize方法是在hashmap的键值大于阈值或初始化时开始调用resize进行扩容
2. 每次扩展时，都是扩展2倍（左移一位）
3. 扩展后的位置，要么在原位置，要么移动到偏移量两倍的位置，根据e.hash & oldCap 是否为0和重新进行hash分配有关

5. HashMap怎么解决hash冲突的

HashMap解决hash冲突的方法是用hash()函数，又称扰动函数

static final int hash(Object key) {
   
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}
....还有一个取余操作得到索引值

为什么不直接用hashCode取余呢?
原因是直接取余的话只有地位的hashCode参与运算，大大增大了冲突的概率，于是采用右移16位再异或，使得高位和地位同时参与取余运算，这样可以大大降低冲突的机会。
相比JDK7(9次扰动 = 4次位运算，5次异或运算)，JDK8只有一次位运算和一次异或运算，代码更加简洁。

小结

1. 使用链地址法来处理拥有相同hash值的数据。
2. 使用2次扰动（hash函数）来降低hash冲突的概率，使得数据分布更加均匀。
3. 引入红黑树来降低遍历的时间复杂度，使得遍历更快。

6. 为什么像String,Ingeter这种包装类适合作为Map的key

String,Ingeter这种包装类能够保证Hash值得不可改性和计算得准确性，能够有效得减少Hash得碰撞机率。

• 都是final类，即不可变性，保证可key得不可变，不会存在获取hash值不同得情况
• 内部都已经重写了hashcode和equals方法，遵守了HashMap的内部规范，不容易出现hash的计算错误。

7. 能否使用任意类作为Map的key，应该怎么办？

可以，但是要重写hashcode和equals方法

• 重写hashcode是因为需要计算存储数据的位置，并且可以保证取数据的时候可以直接锁定索引值，提高效率。
• 遵从Java的api规范，重写equals目的是为了保证key值在哈希表中的唯一性

8. HashMap为什么不是直接使用hashCode()后的值直接作为table下标

hashCode()返回值是一个整形，取值范围在-(2 ^ 31)~(2 ^ 31 - 1）,约有40亿个，映射空间，而hashMap得默认数组容量是16，因此有可能出现计算出来得哈希值不在数组得范围内，进而无法匹配存储位置。
解决方案：
可以自己实现hash()函数，通过二次扰动，使得自己得哈希值自行高低位异或运算，降低哈希碰撞概率也使数据分布更加均匀。

9. HashMap的长度为什么是2的幂次方

为了使HashMap存储得取出更加得高效，尽量减少碰撞，也就是把数据分布均匀。
取余%操作中如果除数是2得次幂则等价于与其除数减一得与&操作，也就是hash % length == (length-1) & hash并且采用二进制得 &运算相比 % 更为高效，这就是为什么是2次幂得原因所在了。
那为什么是二次扰动？
这样就可以加大哈希值低位的随机性，使得分布均匀，从而提高数组存储下标的随机性和均匀性，最终减少hash冲突，两次已经足够，已经达到了高低位同时参与运算的目的。

10. HashMap和TreeMap如何选择

对于你如果需要经常的插入和删除，定位数据的HashMap是比较好的选择。
如果需要对一个有序的key进行遍历的话TreeMap是更好的选择。

11. HashMap和HashTable 有何区别

线程安全:HashMap线程不安全，多个线程同时操作集合数据是，可能会引数据的不一致;而HashTable是线程安全的，内部的方法都有synchronized修饰了，但并不推荐使用，如果想要保证线程安全的话就使用ConcurrentHashMap。
效率：因为线程安全问题，HashMap的效率会比HashTable快。
对null key 和 null value的支持：HashMap支持null key和null value，由于key值唯一，所有允许有一个null key的数据，而HashTable是不允许null key的出现，一出现直接报空指针异常。
底层结构：jdk1.8后HashMap的底层进行了优化，采用数组+链表+红黑树的结构，而HashTable并没有此变化。

12.CocurrentHashMap底层如何实现？实现原理是什么？

<mark>在JDK1.8之前：ConcurrentHashMap采用的是Segment + HashEntry的方式实现，上图</mark>

• 该类包含了两个静态内部类HashEntry，和Segment，前者用来存储键值对，后者用来充当🔒角色。
• Segment是一种可重入的锁ReetrantLock，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry里的数组元素进行修改时，首先必须先获取对应的锁。
  <mark>在JDK1.8之后：放弃了Segment的臃肿设计，取而代之的是采用Node+CAS算法+Synchronized来保证并发安全的实现</mark>
  
  CAS(Compare And Swap)算法：比较替换，用一个期望值和当前值比较，如果期望值与当前值相同则用新值替换当前值。这个是并发场景中乐观锁常用的算法。

13. HashMap和CocurrentHashMap有何区别

• HashMap相比ConcurrentHashMap不是线程安全，ConcurrentHashMap对整个桶数组进行分割分段（Segment）,然后在每一段上加上了lock锁进行保护，相对于HashTable的Synchronized锁的粒度更加精细，并发性能更好。而JDK8后，ConcurrentHashMap采用了全新的实现方式，引入CSA算法。
• HashMap的键值对运行为null，而CocurrentHashMap，HashTable都不允许。

14. HashTable和CocurrentHashMap有何区别

ConcurrentHashMap和HashTable都适用与多线程的环境，但是当HashTable的大小增加到一定时，性能会急剧下降，因为迭代时需要被🔒很长。ConcurrentHashMap引入了分割（Segmentation），无论变得多大，仅仅需要🔒住map的某个部分，而其它线程不需要等迭代完才能访问map。简而言之，在迭代过程中，ConcurrentHashMap仅仅只是🔒住map的某个部分，而HashTable则会🔒住整个map.

五、面试可能遇到的其它问题：

1. 为什么不直接使用hashCode计算hash值，还要经过右移16位且异或的操作？

答：如果一个key经过hashCode()得到

h = 1110 1010 1110 0011 1010 0101 0001 1110

table[]的默认长度是16，进行了h & (n-1) = h&15

1110 1010 1110 0011 1010 0101 0001 1110

&

0000 0000 0000 0000 0000 0000 0000 1111

=

0000 0000 0000 0000 0000 0000 0000 1110

无论高位是什么值，只有1110会被分配在一起(只有低位参与的运算)，哈希碰撞的概率将会变得很高。

而如果进行右移16位的异或操作

1110 1010 1110 0011 1010 0101 0001 1110 >>>16 (高位向低位移动10位，高位补0)

=

0000 0000 0000 0000 1110 1010 1110 0011

再进行异或操作（相异为1）

0000 0000 0000 0000 1110 1010 1110 0011

^

1110 1010 1110 0011 1010 0101 0001 1110

=

1110 1010 1110 0011 0100 1111 1111 1101

得到的数据再进行取模运算得到的索引值将大大减少了哈希碰撞的概率。

2. Hash算法是如何实现的？

答：通过计算key的hashCode值，再将值进行高位右移16位后异或刚刚得到的hashCode值，即hash值。

3. 为什么是线程不安全？

答：因为多个线程同时操作HashMap，并进行put操作如果hash值相同，可能会遇到解决冲突，由于put方法里面没有加入同步锁synchronized机制，因此容易造成数据的不一致，类似addEntry()、resize()方法都不是同步的，因此HashMap是线程不安全。

4. HashMap的数据结构是什么？

在JDK1.8之前HashMap是数组+链表的形式，

在JDK1.8包括之后是数组+链表+红黑树，当链表超过8且数组总量超过64才会转红黑树。

5. HashMap是如何解决hash碰撞的？

答：HashMap采用采用 “拉链法” ，将hash值相同的元素放到同一个链表下面，还可以采用的方法：平方取中法，伪随机数法，取余法

6. HashMap的get方法是怎么实现的？

• 将查询的key传入进行hash计算得到hash值
• 再通过tab[i = (n - 1) & hash]计算索引值定位到table[i]
• 判断首元素的key是否和待查的key == ，若是则直接返回节点
• 如果不是则开始遍历链表判断是否结构是红黑树，若是，则进行红黑树树的遍历
• 若不是，则开始遍历单链表，找到key == 就返回节点

7. 拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

答：选择红黑树是为了解决二叉查找树的缺陷，因为二叉查找树在特殊的情况下会变成一条线性结构，类似与单链表，造成二叉树出现不平衡现象，遍历查找的时候会很慢。引入红黑二叉树就是因为他是一个自平衡的二叉树，会自己调整到二叉树平衡这样就可以提高遍历和查找的效率

8. 默认加载因子为什么是0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;  

答：加载因子需要在时间和空间成本上寻求一种折衷。

加载因子: 是表示Hash表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。

冲突的机会越大,则查找的成本越高。反之,查找的成本越小。

9. HashMap桶中链表转红黑树为什么选择数字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(-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

more: less than 1 in ten million

简单的说就是按照泊松分布的计算公式计算出了放入桶中元素个数和概率的对照表，可以看到链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的，这样就相当于在链表转红黑树之间取一个适中，也是为了提高效率而设定的。

10. HashMap的resize()扩容机制？

答：当put进去元素后，table中的元素个数> table*loadFactor(默认加载因子0.75) ，那么数组就开始扩容，例如：table数组的默认大小是16，当put后的数组长度超过16 * 0.75 = 12时，数组开始扩容，扩容大小 = 原来的一倍，然后重新计算每个元素在数组中的位置。