二、Java集合相关面试题 - 3、Map集合 - 《Java后端面试高频题》

1、Map实现类之间的底层原理和区别？
2、哈希函数其实就是我们常说的哈希算法

1、Map实现类之间的底层原理和区别？

HashMap

Map接口的主要实现类，线程不安全，但效率高，能够存储null值
HashMap的底层原理（类似于HashSet），JDK1.7：底层采用数组（桶）+链表的形式
- step1：实例化一个Hashmap对象，Map map=new HashMap（），此时底层创建了一个长度为16的数组[ ]Entry，包括key和value的值
- step2：向HashMap中添加一个键值对 map.put(key1,values1),此时开始判断是否能添加成功
- step3：首先调用hashCode（）方法计算key1值的哈希值，然后进行二次哈希对数组长度取模，找到所在底层数组Entry中的索引位置，如果该位置中没有其他元素，那么该键值对(key1-values1)添加成功，如果该索引位置已经有其他元素了，那么需要计算key1的hash（）值进行进一步的判断：
  - step4：如果key1的hash（）值与该索引位置任何一个元素hash（）值都不相同，那么key1-value1添加成功
  - step5：如果key1的hash（）值与该索引位置上某个元素的hash（）值相同，那么需要将这两个键值对的key1和key2进行进一步判断
    - 调用key1的equals（）方法和key2的equals（）方法，如果不相同，那么key1-value1键值对添加成功，【以链表的形式进行存储】
    - 如果key1的euqals（）方法和key2的euqals（）方法不相同，那么key1-value1值将去替换key2-vlaues2的值。
- step6：如果利用HashMap进行键值对添加的时候，其底层数组[ ]Entry容量已满，那么将进行扩容，其扩容机制为将原数组的容量扩大为2倍，并且将元素组复制给新数组。
HashMap的底层原理（类似于HashSet），JDK1.8：底层采用数组（桶）+链表+红黑树的形式

主要改变是
1、底层链表长度超过阈值（8）时，将链表存储转换成红黑树存储，避免链表中元素添加过多，导致查找效率过低。
2、底层创建了一个Node[]数组，而非[]Entry数组。

HashMap线程不安全主要表现为：
- 1、在计算哈希值reHash（）得到元素存放的索引位置时，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
- 2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%）

LinkedHaspMap

  - LinkedHashMap是HashMap的子类，其主要是实现了**有序的HashMap**
  - LinkedHashMap修改了底层Entry数组，使其增加了一个before，指向上一个元素；一个after，指向下一个元素。
  - LinkedHashMap能够实现按照插入顺序访问进行遍历。

TreeMap

  - TreeMap底层是**基于红黑树**，是一个**有序的key-value键值对**，其顺序是按照键（key）值的升序自然排序进行的，或者根据自定义Comparator进行排序的，取决于具体的构造方法。

Hashtable

  - **其底层原理与HashMap类似：基于“拉链法”**
  - 不同的是Hashtable的扩容机制是基于阈值的，当底层数组的长度达到阈值时，需要进行扩容，扩容的容量为旧数组容量*2+1，并且将原数组的内容复制给新数组，还重新计算hashtable的阈值。
  - hashtable具有几个重要的成员变量，分别为：
     - **table**：是一个Entry[]数组，其实质为一个单向链表，以key-value键值对存在
     - **count**：是Hashtable的大小，它是Hashtable保存的键值对的数量。
     - **threshold**：是Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值=”容量*加载因子”。
     - **loadFactor**：就是加载因子。
     - **modCount**：是用来实现fail-fast机制的(用于防止在读取过程中，有更新操作，如果有更新操，该参数会修改，然后读取操作会报错)
  - “拉链法”的定义即为大小为M的数组中每一个元素都对应这一个链表，链表中的每一个节点都存储散列值为该索引的键值对。
  - Hashtable不允许存储key-value为null的值。
  - Hashtable底层是同步的，所以是**线程安全的**，hashtable默认容量为11，加载因在为0.75。

properties

2、哈希函数其实就是我们常说的哈希算法

主要应用在以下这几个方面：文件校验、数字签名、鉴权协议。常用的哈希算法有以下这些。
<1>MD5：MD5即Message-Digest Algorithm 5(信息-摘要算法5)，用于确保信息传输完整一致。MD5是输入不定长度信息，输出固定长度128bits的算法。

<2>SHA-1：常用于HTTPS传输和软件签名。

<3>SHA-2:SHA-224/SHA-256/SHA-384/SHA-512并成为SHA-2

<4>SHA-3:之前名为Keccak算法，是一个加密杂凑算法