面试必问之HashMap

ゝ一世哀愁。 2023-02-19 14:22 9阅读 0赞

# 问题1 hashmap原理？ #

## 问题1.1 hashmap底层数据结构是什么 ##

哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。当链表长度超过 8 时，链表转换为红黑树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwMTk4NjExMjY_size_16_color_FFFFFF_t_70]

## 问题1.2 jdk1.8为啥要将链表转为红黑树呢？ ##

链表的用的是线性检索，时间复杂度是O(n)，而红黑树的检索方式是二分查找，平均时间复杂度是O(logn)，当达到一定阈值后，二分查找是由于先行检索的

## 问题1.3 什么情况下会将链表转为红黑树 ##

当来链表长度达到8时会转为红黑树，当桶中链表元素个数小于等于6时，树结构还原成链表。因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

## 问题1.4 能说一下什么是红黑树吗？ ##

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树.  
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。  
红黑树有5个原则：

*  每个节点是红色或者黑色的
 *  根节点必须是黑色的
 *  每个叶子节点都是黑色的空节点（NIL节点），即叶子节点不存储数据
 *  红色节点的两个子节点必须都是黑色的（即路径中不能存在两个连续的红色节点）
 *  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

定义了两个属性：节点的 黑深 以及 树的 黑高。  
根据维基百科的定义，  
节点的黑深指 从根节点到该节点的任意路径中黑色节点的数量。  
树的黑高指 从根节点到叶子节点的任意路径上的黑色节点数量。  
红黑树通过3种操作来维持自身的平衡（插入或删除节点后） —变色，左旋，右旋

## 问题1.5 还有其他集合的数据结构是红黑树吗？ ##

treemap、hashset

## 问题1.6 红黑树能替换为二叉查找树吗？ ##

不能，因为在特定条件下二叉树可能会退化为线性结构

# 问题2 hashmap在什么条件下扩容 #

*  HashMap在什么条件下扩容?
 *  为什么扩容是2的n次幂?
 *  为什么要先高16位异或低16位再取模运算?

## 问题2.1 HashMap在什么条件下扩容? ##

如果bucket满了(超过load factor\*current capacity)，就要resize。  
load factor为0.75，为了最大程度避免哈希冲突  
current capacity为当前数组大小。

## 问题2.2 为什么扩容是2的n次幂? ##

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法  
这个算法实际就是取模，hash%length。 但是，大家都知道这种运算不如位移运算快。  
因此，源码中做了优化hash&(length-1)。 也就是说hash%length==hash&(length-1)

## 问题2.3 为什么要先高16位异或低16位再取模运算? ##

来看一下jdk1.8里的hash方法源码。1.7的比较复杂，就不看了。

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

hashmap这么做，是为了降低hash冲突的几率。

# 问题3 讲一讲hashmap的get/put的过程 #

hashmap put过程：  
对key的hashCode()做hash运算，计算index; 如果没碰撞直接放到bucket里； 如果碰撞了，以链表的形式存在buckets后； 如果碰撞导致链表过长(大于等于TREEIFY\_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)； 如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor\*current capacity)，就要resize。

hashmap get过程：  
对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回； 如果有冲突，则通过key.equals(k)去查找对应的Entry;  
• 若为树，则在树中通过key.equals(k)查找，O(logn)；  
• 若为链表，则在链表中通过key.equals(k)查找，O(n)。

# 问题4 HashMap并发问题 #

## 问题4.1 HashMap 和 HashTable 有什么区别？ ##

①、HashMap 是线程不安全的，HashTable 是线程安全的；  
②、由于线程安全，所以 HashTable 的效率比不上 HashMap；  
③、HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable 不允许；  
④、HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；  
⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

## 问题4.2 HashMap在并发过程中可能遇到什么问题 ##

*  多线程put的时候可能导致元素丢失
 *  put非null元素后get出来的却是null
 *  多线程put后可能导致get死循环

## 问题4.3 怎么得到线程安全的HashMap ##

一般情况下可以使用下面三种集合来替换hashMap，性能最好是ConcurrentHashMap

*  HashTable (直接new)
 *  SynchronizedMap （Collections.synchronizedMap(new HashMap)）
 *  ConcurrentHashMap （直接new）

以上的三个都能在并发情况下正常工作，性能不同主要是体现在锁粒度方面  
这三个都使用了synchrnized 关键字。  
其中HashTable、SynchronizedMap 是直接锁住当前对象，不管是get、put都需要排队。  
而ConcurrentHashMap  
JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。  
JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwMTk4NjExMjY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200620234514201.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwMTk4NjExMjY=,size_16,color_FFFFFF,t_70