黑马程序员技术交流社区

标题: 面试题9 [打印本页]

---

作者: 小白进阶之路    时间: 2018-1-6 23:09
标题: 面试题9
问：简单说说 HashMap 的底层原理？

答：当我们往 HashMap 中 put 元素时，先根据 key 的 hash 值得到这个 Entry 元素在数组中的位置（即下标），然后把这个 Entry 元素放到对应的位置中，如果这个 Entry 元素所在的位子上已经存放有其他元素就在同一个位子上的 Entry 元素以链表的形式存放，新加入的放在链头，从 HashMap 中 get  Entry 元素时先计算 key 的 hashcode，找到数组中对应位置的某一 Entry 元素，然后通过 key 的 equals 方法在对应位置的链表中找到需要的 Entry 元素，所以 HashMap 的数据结构是数组和链表的结合，此外 HashMap 中 key 和 value 都允许为 null，key 为 null 的键值对永远都放在以 table[0] 为头结点的链表中。

之所以 HashMap 这么设计的实质是由于数组存储区间是连续的，占用内存严重，故空间复杂度大，但二分查找时间复杂度小（O(1)），所以寻址容易而插入和删除困难；而链表存储区间离散，占用内存比较宽松，故空间复杂度小，但时间复杂度大（O(N)），所以寻址困难而插入和删除容易；所以就产生了一种新的数据结构叫做哈希表，哈希表既满足数据的查找方便，同时不占用太多的内容空间，使用也十分方便，哈希表有多种不同的实现方法，HashMap 采用的是链表的数组实现方式。

特别说明，对于 JDK 1.8 开始 HashMap 实现原理变成了数组+链表+红黑树的结构，数组链表部分基本不变，红黑树是为了解决哈希碰撞后链表索引效率的问题，所以在 JDK 1.8 中当链表的节点大于 8 个时就会将链表变为红黑树。区别是 JDK 1.8 以前碰撞节点会在链表头部插入，而 JDK 1.8 开始碰撞节点会在链表尾部插入，对于扩容操作后的节点转移 JDK 1.8 以前转移前后链表顺序会倒置，而 JDK 1.8 中依然保持原序。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2