前言
这次我和大家一起学习HashMap ,HashMap 我们在工作中经常会使用,而且面试中也很频繁会问到,因为它里面蕴含着很多知识点,可以很好的考察个人基础。但一个这么重要的东西,我为什么没有在一开始就去学习它呢,因为它是由多种基础的数据结构和一些代码设计思想组成的。我们要学习了这些基础,再学习HashMap ,这样我们才能更好的去理解它。古人云:无欲速,无见小利。欲速则不达,见小利则大事不成。 HashMap 其实就是ArrayList 和LinkedList 的数据结构加上hashCode 和equals 方法的思想设计出来的。没有理解上述说的知识点的同学可以翻开我过往的文章记录。
下面我就以面试问答的形式学习我们的——HashMap (源码分析基于JDK8,辅以JDK7),问答内容只是对HashMap 的一个总结归纳,因为现时已经有大牛把HashMap 通俗易懂的剖析了一遍,我学习HashMap 也是主要通过这篇文章学习的,强烈推荐:美团点评技术团队的Java 8系列之重新认识HashMap 问答内容1.问:HashMap 有用过吗?您能给我说说他的主要用途吗? 答: 示例代码:
int size; 用于记录HashMap 实际存储元素的个数;
float loadFactor; 负载因子(默认是0.75,此属性后面详细解释)。
int threshold; 下一次扩容时的阈值,达到阈值便会触发扩容机制resize (阈值 threshold = 容器容量 capacity * 负载因子 load factor)。也就是说,在容器定义好容量之后,负载因子越大,所能容纳的键值对元素个数就越多。
Node<K,V>[] table; 底层数组,充当哈希表的作用,用于存储对应hash位置的元素Node<K,V> ,此数组长度总是2的N次幂。(具体原因后面详细解释)
示例代码:
其中Node<K,V>[] table; 哈希表存储的核心元素是Node<K,V> ,Node<K,V> 包含:
final int hash; 元素的哈希值,决定元素存储在Node<K,V>[] table; 哈希表中的位置。由final 修饰可知,当hash 的值确定后,就不能再修改。
final K key; 键,由final 修饰可知,当key 的值确定后,就不能再修改。
V value; 值
Node<K,V> next; 记录下一个元素结点(单链表结构,用于解决hash冲突)
示例代码:
hashMap内存结构图 - 图片来自于《美团点评技术团队文章》 2.问:您能说说HashMap 常用操作的底层实现原理吗?如存储put(K key, V value) ,查找get(Object key) ,删除remove(Object key) ,修改replace(K key, V value) 等操作。 答: 判断哈希表Node<K,V>[] table 是否为空或者null ,是则执行resize() 方法进行扩容。 根据插入的键值key 的hash 值,通过(n - 1) & hash 当前元素的hash 值 & hash 表长度 - 1(实际就是 hash 值 % hash 表长度) 计算出存储位置table[i] 。如果存储位置没有元素存放,则将新增结点存储在此位置table[i] 。 如果存储位置已经有键值对元素存在,则判断该位置元素的hash 值和key 值是否和当前操作元素一致,一致则证明是修改value 操作,覆盖value 即可。 当前存储位置即有元素,又不和当前操作元素一致,则证明此位置table[i] 已经发生了hash冲突,则通过判断头结点是否是treeNode ,如果是treeNode 则证明此位置的结构是红黑树,已红黑树的方式新增结点。 如果不是红黑树,则证明是单链表,将新增结点插入至链表的最后位置,随后判断当前链表长度是否 大于等于 8,是则将当前存储位置的链表转化为红黑树。遍历过程中如果发现key 已经存在,则直接覆盖value 。 插入成功后,判断当前存储键值对的数量 大于 阈值threshold 是则扩容。
hashMap put方法执行流程图- 图片来自于《美团点评技术团队文章》 示例代码:
先调用 hash(key) 方法计算出 key 的 hash 值 根据查找的键值key 的hash 值,通过(n - 1) & hash 当前元素的hash 值 & hash 表长度 - 1(实际就是 hash 值 % hash 表长度) 计算出存储位置table[i] ,判断存储位置是否有元素存在 。
如果存储位置有元素存放,但是头结点元素不是要查找的元素,则需要遍历该位置进行查找。 先判断头结点是否是treeNode ,如果是treeNode 则证明此位置的结构是红黑树,以红色树的方式遍历查找该结点,没有则返回null 。 如果不是红黑树,则证明是单链表。遍历单链表,逐一比较链表结点,链表结点的key 的hash 值 和 要获取的key 的hash 值相等,并且 链表结点的key 本身 和要获取的 key 相等,则返回该结点,遍历结束仍未找到对应key 的结点,则返回null 。
示例代码: 先调用 hash(key) 方法计算出 key 的 hash 值 根据查找的键值key 的hash 值,通过(n - 1) & hash 当前元素的hash 值 & hash 表长度 - 1(实际就是 hash 值 % hash 表长度) 计算出存储位置table[i] ,判断存储位置是否有元素存在 。
如果存储位置有元素存放,但是头结点元素不是要删除的元素,则需要遍历该位置进行查找。 先判断头结点是否是treeNode ,如果是treeNode 则证明此位置的结构是红黑树,以红色树的方式遍历查找并删除该结点,没有则返回null 。 如果不是红黑树,则证明是单链表。遍历单链表,逐一比较链表结点,链表结点的key 的hash 值 和 要获取的key 的hash 值相等,并且 链表结点的key 本身 和要获取的 key 相等,则此为要删除的结点,记录此结点至变量node 中,遍历结束仍未找到对应key 的结点,则返回null 。 如果找到要删除的结点node ,则判断是否需要比较value 也是否一致,如果value 值一致或者不需要比较value 值,则执行删除结点操作,删除操作根据不同的情况与结构进行不同的处理。
如果当前结点是树结点,则证明当前位置的链表已变成红黑树结构,通过红黑树结点的方式删除对应结点。 如果不是红黑树,则证明是单链表。如果要删除的是头结点,则当前存储位置table[i] 的头结点指向删除结点的下一个结点。 如果要删除的结点不是头结点,则将要删除的结点的后继结点node.next 赋值给要删除结点的前驱结点的next 域,即p.next = node.next; 。
HashMap 当前存储键值对的数量 - 1,并返回删除结点。
示例代码:
先调用 hash(key) 方法计算出 key 的 hash 值 随后调用getNode 方法获取对应key 所映射的value 值 。 记录元素旧值,将新值赋值给元素,返回元素旧值,如果没有找到元素,则返回null 。
示例代码: 3.问 1:您上面说,存放一个元素时,先计算它的hash值确定它的存储位置,然后再把这个元素放到对应的位置上,那万一这个位置上面已经有元素存在呢,新增的这个元素怎么办? 问 2:hash 冲突(或者叫hash 碰撞)是什么?为什么会出现这种现象,如何解决hash 冲突? 答: hash 冲突: 当我们调用put(K key, V value) 操作添加key-value 键值对,这个key-value 键值对存放在的位置是通过扰动函数(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) 计算键key 的hash 值。随后将 这个hash 值 % 模上 哈希表Node<K,V>[] table 的长度 得到具体的存放位置。所以put(K key, V value) 多个元素,是有可能计算出相同的存放位置。此现象就是hash 冲突或者叫hash 碰撞。
例子如下: 元素 A 的hash 值 为 9,元素 B 的hash 值 为 17。哈希表Node<K,V>[] table 的长度为8。则元素 A 的存放位置为9 % 8 = 1 ,元素 B 的存放位置为17 % 8 = 1 。两个元素的存放位置均为table[1] ,发生了hash 冲突。 hash 冲突的避免:既然会发生hash 冲突,我们就应该想办法避免此现象的发生,解决这个问题最关键就是如果生成元素的hash 值。Java是使用“扰动函数”生成元素的hash 值。
示例代码: Java7做了4次16位右位移异或混合,Java 8中这步已经简化了,只做一次16位右位移异或混合,而不是四次,但原理是不变的。例子如下:
扰动函数执行例子 - 图片来自于《知乎》
右位移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。 上述扰动函数的解释参考自:JDK 源码中 HashMap 的 hash 方法原理是什么? 4.问:HashMap 的容量为什么一定要是2的n次方? 答: 因为调用put(K key, V value) 操作添加key-value 键值对时,具体确定此元素的位置是通过 hash 值 % 模上 哈希表Node<K,V>[] table 的长度 hash % length 计算的。但是'模'运算的消耗相对较大,通过位运算h & (length-1) 也可以得到取模后的存放位置,而位运算的运行效率高,但只有length 的长度是2的n次方时,h & (length-1) 才等价于 h % length 。 而且当数组长度为2的n次幂的时候,不同的key算出的index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
例子: hash & (length-1)运算过程.jpg
上图中,左边两组的数组长度是16(2的4次方),右边两组的数组长度是15。两组的hash 值均为8和9。 当数组长度是15时,当它们和1110 进行& 与运算(相同为1,不同为0)时,计算的结果都是1000 ,所以他们都会存放在相同的位置table[8] 中,这样就发生了hash 冲突,那么查询时就要遍历链表,逐一比较hash 值,降低了查询的效率。 同时,我们可以发现,当数组长度为15的时候,hash 值均会与14(1110) 进行& 与运算,那么最后一位永远是0,而0001 ,0011 ,0101 ,1001 ,1011 ,0111 ,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率。
上述回答参考自:深入理解HashMap 示例代码: 5.问:HashMap 的负载因子是什么,有什么作用? 答:负载因子表示哈希表空间的使用程度(或者说是哈希表空间的利用率)。 例子如下: 底层哈希表Node<K,V>[] table 的容量大小capacity 为 16,负载因子load factor 为 0.75,则当存储的元素个数size = capacity 16 * load factor 0.75 等于 12 时,则会触发HashMap 的扩容机制,调用resize() 方法进行扩容。 当负载因子越大,则HashMap 的装载程度就越高。也就是能容纳更多的元素,元素多了,发生hash 碰撞的几率就会加大,从而链表就会拉长,此时的查询效率就会降低。 当负载因子越小,则链表中的数据量就越稀疏,此时会对空间造成浪费,但是此时查询效率高。 我们可以在创建HashMap 时根据实际需要适当地调整load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,默认负载因子 (0.75) 在时间和空间成本上寻求一种折衷,程序员无需改变负载因子的值。 因此,如果我们在初始化HashMap 时,就预估知道需要装载key-value 键值对的容量size ,我们可以通过size / load factor 计算出我们需要初始化的容量大小initialCapacity ,这样就可以避免HashMap 因为存放的元素达到阈值threshold 而频繁调用resize() 方法进行扩容。从而保证了较好的性能。
6.问:您能说说HashMap 和HashTable 的区别吗? 答:HashMap 和HashTable 有如下区别: 1)容器整体结构: 2) 容量设定与扩容机制: 3) 散列分布方式(计算存储位置): HashMap 是先将key 键的hashCode 经过扰动函数扰动后得到hash 值,然后再利用 hash & (length - 1) 的方式代替取模,得到元素的存储位置。
Hashtable 则是除留余数法进行计算存储位置的(因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算),int index = (hash & 0x7FFFFFFF) % tab.length; 。
由于HashMap 的容器容量一定是2的n次方,所以能使用hash & (length - 1) 的方式代替取模的方式计算元素的位置提高运算效率,但Hashtable 的容器容量不一定是2的n次方,所以不能使用此运算方式代替。
4)线程安全(最重要): HashMap 不是线程安全,如果想线程安全,可以通过调用synchronizedMap(Map<K,V> m) 使其线程安全。但是使用时的运行效率会下降,所以建议使用ConcurrentHashMap 容器以此达到线程安全。
Hashtable 则是线程安全的,每个操作方法前都有synchronized 修饰使其同步,但运行效率也不高,所以还是建议使用ConcurrentHashMap 容器以此达到线程安全。
因此,Hashtable 是一个遗留容器,如果我们不需要线程同步,则建议使用HashMap ,如果需要线程同步,则建议使用ConcurrentHashMap 。 此处不再对Hashtable的源码进行逐一分析了,如果想深入了解的同学,可以参考此文章 Hashtable源码剖析 7.问:您说HashMap 不是线程安全的,那如果多线程下,它是如何处理的?并且什么情况下会发生线程不安全的情况? 答: HashMap 不是线程安全的,如果多个线程同时对同一个HashMap 更改数据的话,会导致数据不一致或者数据污染。如果出现线程不安全的操作时,HashMap 会尽可能的抛出ConcurrentModificationException 防止数据异常,当我们在对一个HashMap 进行遍历时,在遍历期间,我们是不能对HashMap 进行添加,删除等更改数据的操作的,否则也会抛出ConcurrentModificationException 异常,此为fail-fast(快速失败)机制。从源码上分析,我们在put,remove 等更改HashMap 数据时,都会导致modCount的改变,当expectedModCount != modCount 时,则抛出ConcurrentModificationException 。如果想要线程安全,可以考虑使用ConcurrentHashMap 。
而且,在多线程下操作HashMap ,由于存在扩容机制,当HashMap 调用resize() 进行自动扩容时,可能会导致死循环的发生。
由于时间关系,我暂不带着大家一起去分析resize() 方法导致死循环发生的现象造成原因了,迟点有空我会再补充上去,请见谅,大家可以参考如下文章: Java 8系列之重新认识HashMap 谈谈HashMap线程不安全的体现 8.问:我们在使用HashMap 时,选取什么对象作为key 键比较好,为什么? 答: 可变对象:指创建后自身状态能改变的对象。换句话说,可变对象是该对象在创建后它的哈希值可能被改变。 我们在使用HashMap 时,最好选择不可变对象作为key 。例如String ,Integer 等不可变类型作为key 是非常明智的。 如果key 对象是可变的,那么key 的哈希值就可能改变。在HashMap 中可变对象作为Key会造成数据丢失。因为我们再进行hash & (length - 1) 取模运算计算位置查找对应元素时,位置可能已经发生改变,导致数据丢失。
详细例子说明请参考:危险!在HashMap中将可变对象用作Key 总结HashMap 是基于Map 接口实现的一种键-值对<key,value> 的存储结构,允许null 值,同时非有序,非同步(即线程不安全)。HashMap 的底层实现是数组 链表 红黑树(JDK1.8增加了红黑树部分)。
HashMap 定位元素位置是通过键key 经过扰动函数扰动后得到hash 值,然后再通过hash & (length - 1) 代替取模的方式进行元素定位的。
HashMap 是使用链地址法解决hash 冲突的,当有冲突元素放进来时,会将此元素插入至此位置链表的最后一位,形成单链表。当存在位置的链表长度 大于等于 8 时,HashMap 会将链表 转变为 红黑树,以此提高查找效率。
HashMap 的容量是2的n次方,有利于提高计算元素存放位置时的效率,也降低了hash 冲突的几率。因此,我们使用HashMap 存储大量数据的时候,最好先预先指定容器的大小为2的n次方,即使我们不指定为2的n次方,HashMap 也会把容器的大小设置成最接近设置数的2的n次方,如,设置HashMap 的大小为 7 ,则HashMap 会将容器大小设置成最接近7的一个2的n次方数,此值为 8 。
HashMap 的负载因子表示哈希表空间的使用程度(或者说是哈希表空间的利用率)。当负载因子越大,则HashMap 的装载程度就越高。也就是能容纳更多的元素,元素多了,发生hash 碰撞的几率就会加大,从而链表就会拉长,此时的查询效率就会降低。当负载因子越小,则链表中的数据量就越稀疏,此时会对空间造成浪费,但是此时查询效率高。
HashMap 不是线程安全的,Hashtable 则是线程安全的。但Hashtable 是一个遗留容器,如果我们不需要线程同步,则建议使用HashMap ,如果需要线程同步,则建议使用ConcurrentHashMap 。
在多线程下操作HashMap ,由于存在扩容机制,当HashMap 调用resize() 进行自动扩容时,可能会导致死循环的发生。 我们在使用HashMap 时,最好选择不可变对象作为key 。例如String ,Integer 等不可变类型作为key 是非常明智的。
|