剑指Offer | java经典面试题—Map接口

剑指Offer | java经典面试题—Map接口 Map接口

说一下 HashMap 的实现原理？

HashMap概述：HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射 *** 作， 并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构：在Java编程语言中， 基本的结构就是两种，一个是数组，另外一个是模拟指针 （引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。

HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

HashMap 基于 Hash 算法实现的

当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标

存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value 放入链表中

获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除 困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各 自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。

JDK1.8之前

JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一 格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将 链表转化为红黑树，以减少搜索时间

HashMap的put方法的具体流程

当我们put的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让key.hashCode() 与key.hashCode()>>>16进行异或 *** 作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用 就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。

按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。

putVal方法执行流程图

1 public V put(K key, V value) { 

2 return putVal(hash(key), key, value, false, true); 

3 } 

4

5 static final int hash(Object key) { 

6 int h; 

7 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 

8 } 

9

10 //实现Map.put和相关方法 

11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 

12 boolean evict) { 

13 Node[] tab; Node p; int n, i; 

14 // 步骤①：tab为空则创建 

15 // table未初始化或者长度为0，进行扩容 

16 if ((tab = table) == null || (n = tab.length) == 0) 

17 n = (tab = resize()).length; 

18 // 步骤②：计算index，并对null做处理 

19 // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这 个结点是放在数组中) 

20 if ((p = tab[i = (n - 1) & hash]) == null) 

21 tab[i] = newNode(hash, key, value, null); 

22 // 桶中已经存在元素 

23 else { 

24 Node e; K k; 

25 // 步骤③：节点key存在，直接覆盖value 

26 // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等 

27 if (p.hash == hash && 

28 ((k = p.key) == key || (key != null && key.equals(k)))) 

29 // 将第一个元素赋值给e，用e来记录 

30 e = p; 

31 // 步骤④：判断该链为红黑树 

32 // hash值不相等，即key不相等；为红黑树结点 

33 // 如果当前元素类型为TreeNode，表示为红黑树，putTreeval返回待存放的node, e可能为null

34 else if (p instanceof TreeNode) 

35 // 放入树中 

36 e = ((TreeNode)p).putTreeval(this, tab, hash, key, value); 

37 // 步骤⑤：该链为链表 

38 // 为链表结点 

39 else { 

40 // 在链表最末插入结点 

41 for (int binCount = 0; ; ++binCount) { 

42 // 到达链表的尾部 

43

44 //判断该链表尾部指针是不是空的 

45 if ((e = p.next) == null) { 

46 // 在尾部插入新结点 

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

48 //判断链表的长度是否达到转化红黑树的临界值，临界值为8 

49 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 

50 //链表结构转树形结构 

51 treeifyBin(tab, hash); 

52 // 跳出循环 

53 break; 

54 } 

55 // 判断链表中结点的key值与插入的元素的key值是否相等 

56 if (e.hash == hash && 

57 ((k = e.key) == key || (key != null && key.equals(k)))) 

58 // 相等，跳出循环 

59 break; 

60 // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 

61 p = e; 

62 } 

63 } 

64 //判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的val ue这个值 

65 if (e != null) { 

66 // 记录e的value 

67 V oldValue = e.value; 

68 // onlyIfAbsent为false或者旧值为null 

69 if (!onlyIfAbsent || oldValue == null) 

70 //用新值替换旧值 

71 e.value = value; 

72 // 访问后回调 

73 afterNodeAccess(e); 

74 // 返回旧值 

75 return oldValue; 

76 } 

77 } 

78 // 结构性修改 

79 ++modCount; 

80 // 步骤⑥：超过最大容量就扩容 

81 // 实际大小大于阈值则扩容 

82 if (++size > threshold) 

83 resize(); 

84 // 插入后回调 

85 afterNodeInsertion(evict); 

86 return null; 

87 }

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如 果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向 ④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值 对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入 *** 作，否则进行链表的插入 *** 作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了 大容量threshold，如果超过，进行扩容。

HashMap的扩容 *** 作是怎么实现的？

①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行 扩容；

②.每次扩展的时候，都是扩展2倍；

③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。在putVal()中，我们看到在 这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或 者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进 行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根 据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是 否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大 小这个位置上

1 final Node[] resize() { 

2 Node[] oldTab = table;//oldTab指向hash桶数组 

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

4 int oldThr = threshold; 

5 int newCap, newThr = 0; 

6 if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空 

7 if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀 值

8 threshold = Integer.MAX_VALUE; 

9 return oldTab;//返回 

10 }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16 

11 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 

12 oldCap >= DEFAULT_INITIAL_CAPACITY) 

13 newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold 

14 } 

15 // 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初 始化成最小2的n次幂 

16 // 直接将该值赋给新的容量 

17 else if (oldThr > 0) // initial capacity was placed in threshold 

18 newCap = oldThr; 

19 // 无参构造创建的map，给出默认容量和threshold 16, 16*0.75 

20 else { // zero initial threshold signifies using defaults 

21 newCap = DEFAULT_INITIAL_CAPACITY; 

22 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 

23 } 

24 // 新的threshold = 新的cap * 0.75 

25 if (newThr == 0) {

26 float ft = (float)newCap * loadFactor; 

27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 

28 (int)ft : Integer.MAX_VALUE); 

29 } 

30 threshold = newThr; 

31 // 计算出新的数组长度后赋给当前成员变量table 

32 @SuppressWarnings({"rawtypes","unchecked"}) 

33 Node[] newTab = (Node[])new Node[newCap];//新建hash桶数组 

34 table = newTab;//将新数组的值复制给旧的hash桶数组 

35 // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素 重排逻辑，使其均匀的分散 

36 if (oldTab != null) { 

37 // 遍历新数组的所有桶下标 

38 for (int j = 0; j < oldCap; ++j) { 

39 Node e; 

40 if ((e = oldTab[j]) != null) { 

41 // 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无法被GC回收

42 oldTab[j] = null; 

43 // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树 

44 if (e.next == null) 

45 // 用同样的hash映射算法把该元素加入新的数组 

46 newTab[e.hash & (newCap - 1)] = e;

47 // 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排 

48 else if (e instanceof TreeNode) 

49 ((TreeNode)e).split(this, newTab, j, oldCap); 

50 // e是链表的头并且e.next!=null，那么处理链表中元素重排 

51 else { // preserve order 

52 // loHead,loTail 代表扩容后不用变换下标，见注1 

53 Node loHead = null, loTail = null; 

54 // hiHead,hiTail 代表扩容后变换下标，见注1 

55 Node hiHead = null, hiTail = null; 

56 Node next; 

57 // 遍历链表 

58 do { 

59 next = e.next; 

60 if ((e.hash & oldCap) == 0) { 

61 if (loTail == null) 

62 // 初始化head指向链表当前元素e，e不一定是链表的第一个元素，初始化后loHead 

63 // 代表下标保持不变的链表的头元素 

64 loHead = e; 

65 else 

66 // loTail.next指向当前e 

67 loTail.next = e; 

68 // loTail指向当前的元素e 

69 // 初始化后，loTail和loHead指向相同的内存，所以当loTail.next指向下一个元素 时，

70 // 底层数组中的元素的next引用也相应发生变化，造成lowHead.next.next..... 

71 // 跟随loTail同步，使得lowHead可以链接到所有属于该链表的元素。 

72 loTail = e; 

73 } 

74 else { 

75 if (hiTail == null) 

76 // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素 

77 hiHead = e; 

78 else 

79 hiTail.next = e; 

80 hiTail = e; 

81 }

82 } while ((e = next) != null); 

83 // 遍历结束, 将tail指向null，并把链表头放入新数组的相应下标，形成新的映射。 

84 if (loTail != null) { 

85 loTail.next = null; 

86 newTab[j] = loHead; 

87 } 

88 if (hiTail != null) { 

89 hiTail.next = null; 

90 newTab[j + oldCap] = hiHead; 

91 } 

92 } 

93 } 

94 } 

95 } 

96 return newTab; 

97 }

今天就先到这里了，关注我们，后期更新更多面试题，祝你早日拿到心仪的offer！