分类 标签 存档 社区 博客 友链 GitHub 订阅 搜索

HashMap

170 浏览

ZERO

    持续更新 请关注:https://zorkelvll.cn/blogs/zorkelvll/articles/2018/11/18/1542542370201

背景

     本文主要是针对 HashMap 进行学习和总结!

关键词:压缩映射、数组、链表、红黑树、异或 hashcode、与取模数组下标、扩容、线程不安全、碰撞

问题

1、HashTable toString 在迭代的时候为什么会出现异常?

一、哈希

    Hash,所谓散列也即哈希,是一种压缩映射函数,即将任意长度的输入压缩映射为固定长度的输出

    HashTable,也即散列表:根据键值 (key) 而直接访问在内存中存储位置的数据结构; 也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表

二、HashMap

    概念:基于哈希表的 Map 接口的非同步实现;也即,HashMap 基于 hashing 原理,通过 put 和 get 方法存储和获取对象;

    特点:提供所有可选的映射操作,但是不保证映射的顺序,也不保证顺序不随时间变化;允许使用 null 键和 null 值;

【问 1】??HashMap 的原理,内部数据结构?

    答:*->:*HashMap 底层是一个数组结构,该数组的每一项元素均为一个链表,当链表过长时会将链表转成红黑树;aka:Hashmap = 数组 + 链表 + 红黑树;

    ->:HashMap 在 put 一个 K,V 时,【存储的是键对象和值对象

    (1)hashCode(异或):先重新计算 hashCode 值【(key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16),高 16bit 不变,低 16bit 和高 16bit 做了一个异或,即加入了高位计算防止低位不变高位变化时造成的 hash 冲突,,这是因为在 table 长度较小时实际参与取模运算计算数组下标的很可能是就是低位参与运算的导致出现冲突的概率很大!!】,

    (2)取模(与):然后计算在数组中的存储下标 index【i = (2^n - 1) & hashCode】(说明:其中 2^n 为该数组的长度也即容量,若没有高 16bit 和低 16bit 异或一下,i = (2^n - 1) & hashCode 计算时真正有效的是低位,会导致因为高位没有参与下标的计算 (table 长度比较小时),大大增加了引起的碰撞的概率问题) => 这是因为 x % 2^n = X & (2^n -1),而与运算是直接在内存中进行计算的且 % 运算是需要转成十进制计算的,因此后者与运算效率性能更高!

    (3)如果没有碰撞,则直接放在数组 bucket 里;如果碰撞了,则以链表形式存储在 bucket 里,且后加入的放在链尾【jdk8 之前是插入头部的,jdk8 是插入尾部的】;如果碰撞导致链表过长(>=TREEIFY_THRESHOLD, 默认 8,也即超过阈值),则会把链表转换成红黑树;如果节点已经存在,则替换 old value(保证 key 唯一性);如果 HashMap 中元素的个数满了(超过了负载因子(默认 0.75)* 当前容量(初始默认 16),,也即键值对的实际大小 size 大于 table 可以允许的实际大小时进行扩容),则 resize(即调整数组的容量是当前的 2 倍); -> JDK8 相对于 JDK7 主要是增加了链表转树(树转链表)和红黑树平衡的逻辑,以进一步优化 HashMap 的性能

   (4)resize 扩大容量一倍,一个比较牺牲性能的操作,这是由于需要重新计算位置,因此应当尽可能精确地预设 HashMap 的容量,避免 resize 以有效提高性能;

【问 2】??说一下 HashMap 中 put 方法过程?

    答:也即:对 Key 对象高低 16 位异或运算重新计算出 hashcode 值,然后再通过与方式的取模运算计算出在数组中的下标;如果没有碰撞,则直接放入桶中;如果碰撞了,则以链表方式放在尾部(jdk8,jdk8 之前是放在链头的);如果链表长度超过阈值(TREEIFY_THRESHOLD == 8),则把链表转成红黑树;如果节点已经存在,则替换旧值;如果键值对的个数满了(容量 * 加载因子),则需要 resize

【问 3】??HashMap 中 hash 函数是怎么实现的?还有那些 hash 的实现方式?

    答:核心思想是取模运算实现 hash 压缩映射的,jdk8 中采用一些小技巧:如(1)通过 16bit 和高 16bit 异或运算重新计算出一个新的 hashcode 值,以减少因数组长度较小时带来的碰撞冲突;(2)通过与运算符号 & 代替直接的取模符号 %,即用新的 hashcode 值与该数组长度 - 1(2^n - 1)进行与运算,计算出数组下标,与运算是直接在内存中进行的且无须转换成 10 进制,以进一步提高性能;

    ???哪些实现方式?::直接定址法、数字分析法、除留余数法、分段叠加法、平方取中法、伪随机数法

  ->:HashMap 在 get(Object key) 时,

    (1)先高低位异或重新计算获得 hashcode 值,然后与运算取模计算得到在数组中的存储下标 index

    (2)如果是 bucket 里的第一个节点,则直接命中;否则有冲突,通过 key.equals(k) 查找对应的 Node,若为树则 O(logn),若为链表则 O(n);

   ->:碰撞探测,也即上述 set 和 get 方法中提到的 hashCode 相同时,则数组 index 位置处的 bucket 中以链表形式进行存储和查找

    描述:HashMap 初始化时,系统会创建一个长度为 capcity(16) 的的 Node 数组,该 Node 数组中可以存储 node 元素的位置被称为桶 bucket(每个桶均有其索引,且只存储一个 node 元素,且 node 对象含有一个引用变量,用以指向下一个 node 进而构成 node 链表结构)

   ->:非线程安全,这是由于:

    (1)不同线程在 put 操作时,如果是其中一个线程改变了某一键值对的 value,那么其他的线程就 get 不到预期的值,而且值是在不停改变的,因此这样也不是线程安全的;

    (2)在多线程中,当有两个线程同时在 put 操作的时候,如果存在扩容调用 resize,那么也就是 resize 被两个线程同时调用,可能会产生环形链表,然后再执行 get 操作就会触发死循环引起 CPU 的 100% 问题

    (3)fail-fast,如果在使用迭代器的过程中有其他线程修改了 map 的结构,则将抛出 ConcurrentModificationException 异常,也即所谓的 fail-fast 策略,此时开发人员应该注意线程安全问题

   (说明)(a) 避免多线程写时使用 HashMap,单写多读是没有问题的;(b) 或者为什么要在多线程中使用 HashMap,Sun 官方都不认为 HashMap 在多线程中的这个问题是个 bug,因为 HashMap 本来就是不支持多线程使用的,如果需要并发的话就用 ConcurrentHashMap;© 或者通过方法 Collections.synchroziedMap(Map),将 HashMap 转化为线程同步的 Map

    注意事项:

 (1)使用 String、Integer 等引用类型的封箱 wrapper 类作为键 Key 使用;String 最为常用,不可变且 final 的,已经重写的 equals 和 hashCode 方法 -> 当对象插入到 HashMap 之后,且 Key 就不会再改变了

(2)equals 相等,必然 hashCode 相等 <=> hashCode 不相等,必然 equals 不相等;

(3)hashCode 相等,equals 可能不相等;

(4)Hashtable 使用了线程同步锁保护,也即 Hashtable 是粗暴地添加了同步锁 (synchronized),导致性能会有损失 -> 更好的方式是使用 ConcurrentHashMap,该类采用的是一种分段锁的机制实现线程安全的,后续将在单独一个篇幅中进行介绍!

【问 4】??HashMap 怎样解决冲突,讲一下扩容过程,假如一个值在原数组中,现在移动了数组,位置肯定改变了,那是什么定位到在这个新数组中的位置?

    答:将新节点加到链表后,容量扩充为原来的两倍,然后对每个节点重新计算 hash 值,这个值只会出现在两个地方,一个是原下标的位置,另一种是在下标为 <原下标 + 原容量> 的位置

【问 5】??抛开 HashMap,hash 冲突有哪些解决办法?

    答:开放定址法,链地址法,再哈希法、建立公共溢出区

【问 6】??针对 HashMap 中某个 Node 链太长,查找的时间复杂度可能达到 O(n), 怎么优化?

    答:将链表转为红黑树,JDK1.8 已经实现,时间复杂度变为 O(logn)

三、Hashtable、HashMap、ConcurrentHashMap

    ConcurrentHashMap 使用分段锁技术,允许多个修改操作并发进行。ConcurrentHashMap 内部使用段来表示这些不同的部分,每个段其实就是一个小的 Hashtable,它们有自己的锁。只要多个修改操作发生在不同的段上,它们就可以并发进行。

    Hashtable 是一个线程安全的类,它使用 synchronized 来锁住整张 Hash 表来实现线程安全,即每次锁住整张表让线程独占

    有些方法需要跨段,比如 size()和 containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。这里 “按顺序” 是很重要的,否则极有可能出现死锁,在 ConcurrentHashMap 内部,段数组是 final 的,并且其成员变量实际上也是 final 的,但是,仅仅是将数组声明为 final 的并不保证数组成员也是 final 的,这需要实现上的保证。这可以确保不会出现死锁,因为获得锁的顺序是固定的。

    HashMap 类:

  • Node:链表节点,包含了 key、value、hash、next 指针四个元素
  • table:Node 类型的数组,里面的元素是链表,用于存放 HashMap 元素的实体
  • size:记录了放入 HashMap 的元素个数
  • loadFactor:负载因子
  • threshold:阈值,决定了 HashMap 何时扩容,以及扩容后的大小,一般等于 table 大小乘以 loadFactor

四、参考

1、http://www.hollischuang.com/archives/2091

2、http://www.importnew.com/20386.html

评论  
留下你的脚步
推荐阅读