江苏龙网

  1. 首页 > 人文 > >

详解HashMap集合

视频教程地址：
1.HashMap集合简介HashMap基于哈希表的Map接口实现 ， 是以key-value存储形式存在 ， 即主要用来存放键值对 。 HashMap 的实现不是同步的 ， 这意味着它不是线程安全的 。 它的key、value都可以为null 。 此外 ， HashMap中的映射不是有序的 。
JDK1.8 之前 HashMap 由 数组+链表 组成的 ， 数组是 HashMap 的主体 ， 链表则是主要为了解决哈希冲突(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化 ， 当链表长度大于阈值（或者红黑树的边界值 ， 默认为 8）并且当前数组的长度大于64时 ， 此时此索引位置上的所有数据改为使用红黑树存储 。
补充：将链表转换成红黑树前会判断 ， 即使阈值大于8 ， 但是数组长度小于64 ， 此时并不会将链表变为红黑树 。 而是选择进行数组扩容 。
这样做的目的是因为数组比较小 ， 尽量避开红黑树结构 ， 这种情况下变为红黑树结构 ， 反而会降低效率 ， 因为红黑树需要进行左旋 ， 右旋 ， 变色这些操作来保持平衡。 同时数组长度小于64时 ， 搜索时间相对要快些 。 所以综上所述为了提高性能和减少搜索时间 ， 底层在阈值大于8并且数组长度大于64时 ， 链表才转换为红黑树 。 具体可以参考 treeifyBin方法 。
当然虽然增了红黑树作为底层数据结构 ， 结构变得复杂了 ， 但是阈值大于8并且数组长度大于64时 ， 链表转换为红黑树时 ， 效率也变的更高效 。
小结：
特点：
1.存取无序的
2.键和值位置都可以是null ， 但是键位置只能是一个null
3.键位置是唯一的 ， 底层的数据结构控制键的
4.jdk1.8前数据结构是：链表 + 数组 jdk1.8之后是 ： 链表 + 数组 + 红黑树
5.阈值(边界值) > 8 并且数组长度大于64 ， 才将链表转换为红黑树 ， 变为红黑树的目的是为了高效的查询 。
2.HashMap集合底层的数据结构2.1数据结构概念数据结构是计算机存储、组织数据的方式 。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合 。 通常情况下 ， 精心选择的数据结构可以带来更高的运行或者存储效率 。 数据结构往往同高效的检索算法和索引技术有关 。
数据结构：就是存储数据的一种方式 。 ArrayList LinkedList
在JDK1.8 之前 HashMap 由 数组+链表 数据结构组成的 。
在JDK1.8 之后 HashMap 由 数组+链表 +红黑树数据结构组成的 。
2.2HashMap底层的数据结构存储数据的过程存储过程如下所示：
使用的代码：
public class Demo01 {public static void main(String[] args) {HashMap map = new HashMap<>();map.put("刘德华", 53);map.put("柳岩", 35);map.put("张学友", 55);map.put("郭富城", 52);map.put("黎明", 51);map.put("林青霞", 55);map.put("刘德华", 50);}}说明：
1.面试题：HashMap中hash函数是怎么实现的？还有哪些hash函数的实现方式？
对于key的hashCode做hash操作 ， 无符号右移16位然后做异或运算 。 还有平方取中法 ， 伪随机数法和取余数法 。 这三种效率都比较低 。 而无符号右移16位异或运算效率是最高的 。 至于底层是如何计算的我们下面看源码时给大家讲解 。 2.面试题：当两个对象的hashCode相等时会怎么样？
会产生哈希碰撞 ， 若key值内容相同则替换旧的value.不然连接到链表后面 ， 链表长度超过阈值8就转换为红黑树存储 。 3.面试题：何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞？
只要两个元素的key计算的哈希码值相同就会发生哈希碰撞 。 jdk8前使用链表解决哈希碰撞 。 jdk8之后使用链表+红黑树解决哈希碰撞 。


推荐阅读


上一篇：正确使用#include语句的双引号形式和角括号形式

下一篇：带你揭开BFC的神秘面纱