HashMap 知识小结

1.HashMap 数据结构

  • JDK1.7：数组+链表
  • 数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
  • JDK1.8：数组+链表+红黑树
    • 当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。
      • 当链表超过 8 且数据总量超过 64 才会转红黑树。
      • 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。

 

image.png

  • 数组：采用一段连续的存储单元来存储数据。
    • 特点：查询 O(1) ，删除插入 O(N)
    • 总结：查询快，删除插入慢
  • 链表：链表是一种物理存储单元上非连续，非顺序的存储结构。
    • 特点：插入、删除时间复杂度 O(1) ，查询遍历时间复杂度 O(N)
    • 总结：插入快、查找慢

2.Hash 算法

哈希算法（也叫散列），就是把任意长度值（Key）通过散列算法变换成固定长度的 Key (地址) 通过这个地址进行访问的数据结构。

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

 

  • Hashcode（取模/位运算）
    • 通过字符串算出它的 ascii 码，进行 mod（取模），算出哈希表中的下标。
    • 优点：能够节省数组的空间
    • 缺点：会产生哈希冲突问题
    • 链表出现原因：解决hash 碰撞。

3.JDK8 中的 HashMap 与 JDK7 的 HashMap 有什么不一样？

  1. JDK8 中新增了红黑树，JDK8 是通过 【数组+链表+红黑树】来实现的。
  2. JDK7 中链表的插入式用的头插法，而 JDK8 中则改为了尾插法。
  3. JDK8 中的因为使用了红黑树保证了插入和查询的效率，所以实际上 JDK8 中的 Hash 算法实现的复杂度降低了。
  4. JDK8 中数组扩容的条件也发生了变化，只会判断是否当前元素是否查过了阈值，而不再判断当前 put 进来的元素对应的数组下标位置是否有值。
  5. JDK7 中是先扩容再添加新元素，JDK8 中是先添加新元素然后再扩容。

 

4.HashMap 中 PUT 方法的流程

  1. 通过 Key 计算出一个 hashcode。
  2. 通过 hashcode 与“与操作”计算出一个数组下标
  3. 在把 put 进来的 key-value 封装为一个 entry 对象
  4. 判断数组下标对应的位置，是不是空，如果是空则把 entry 直接存在该数组位置
  5. 如果该下标对应的位置不为空，则需要把 entry 插入到链表中
  6. 并且还需要判断该链表中是否存在相同的 key ，如果存在，则更新 value
  7. 如果是 jdk7 ，则使用头插法
  8. 如果是 jdk8 ，则会遍历链表，并且在遍历链表的过程中，统计当前链表的元素个数，如果超过8个，则先把链表转变为红黑树，并且把元素插入到红黑树中

 

5.JDK8 中链表转变为红黑树的条件？

  1. 链表中的元素的个数为8个或超过8个
  2. 同时，还要满足当前数组的长度大于或等于64才会把链表转变为红黑树。
    1. 为什么？——>因为链表转变为红黑树的目的是为了解决链表过长，导致查询和插入效率慢的问题，而如果要解决这个问题，也可以通过数组扩容，把链表缩短也可以解决这个问题。所以在数组长度还不太长的情况，可以先通过数组扩容来解决链表过长的问题。

image

 

6.HashMap是线程不安全的，其主要体现

  1. 在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
  2. 在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

 

HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

 Map map = Collections.synchronizedMap(new HashMap());

https://mp.weixin.qq.com/s/UdonpQAYbTqFvxZR1Cm5lg

7.HashMap 解决hash冲突

HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。

【HashMap底层是通过链表来解决hash冲突的。】

 

8.HashMap 关键属性

  • loadFactor加载因子是表示Hsah表中元素的填满的程度=0.75
  • threshold临界值当实际大小超过临界值时，会进行扩容
    • threshold = 加载因子*容量

 

9.HashMap 数组长度永远为 2 的幂次方

HashMap 是通过一个名为 tableSizeFor 的方法来确保 HashMap 数组长度永远为2的幂次方的。

tableSizeFor 的功能（不考虑大于最大容量的情况）是返回大于等于输入参数且最近的 2 的整数次幂的数。比如 10，则返回 16。

 

10.HashMap 为什么会导致 CPU 运行 100% ？（为什么会导致死循环？）

image.png

JAVA HASHMAP的死循环：https://coolshell.cn/articles/9606.html

 

参考资料：

  • 如何决定使用 HashMap 还是 TreeMap？
  • 什么情况用ArrayList or LinkedList呢?
  • HashMap怎样解决hash冲突
  • HashMap的实现原理
  • Java集合框架 10 连问
  • Java容器面试题：谈谈你对 HashMap 的理解
  • Java集合面试问题
  • HashMap 中的容量与扩容实现
  • 看完这篇，再也不怕面试被问HashMap
  • ArrayList源码分析&手写ArrayList
  • LinkedList源码分析
  • HashMap源码分析
  • TreeMap 原理实现及常用方法
  • java集合中HashSet的原理及常用方
  • 常用的Arraylist和Linkedlist的区别
  • HashMap 面试二十一问
  • hashCode()和equals()方法及使用规范
  • Java线程安全与不安全的理解
版权声明：本文为cangsheng45原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。