温故知新--深入理解Map

对于Java的集合认知一直以来都不够清晰,现在特地对Map做一次总结,以加深印象。

Map接口位于java.util包下,该包下一共提供了如下具体的实现类(基于JDK1.8),java.util包中开放的实现类如下图所示:

Map

涉及的接口和抽象类有如下几个:

名称 说明
Map 提供存放键值对的对象,要求key不能重复,包含get、put等方法
SortedMap 提供有序的Map
NavigableMap 在 SortedMap 基础上,支持快速搜索符合条件的最近的元素
ConcurrentMap 提供线程安全和原子性的Map
ConcurrentNavigableMap 继承自NavigableMap和ConcurrentMap,提供线程安全的同时,支持快速搜索
AbstractMap 提供Map接口的框架实现

AbstractMap
如果想要开发自定义的Map,建议扩展AbstractMap,其中提供了一些默认实现。除了 Hashtable 和 Properties,其它实现类都继承自AbstractMap。

实现类供有10个,整理如下:

名称 数据结构 初始化容量 扩容方式 适用场景
HashMap 数组 + 链表 + 红黑树 16 个数超过负载因子(默认0.75)指定值时,扩容2倍 不保证读取顺序与写入数据一致
LinkedHashMap 双向链表 +(数组 + 链表 + 红黑树) 同HashMap 同HashMap 继承自HashMap,保证读取顺序与写入数据一致
IdentityHashMap 数组 16 超出容量时,扩容2倍 不使用equals比较key,直接使用==比较key,因此不存在哈希冲突的问题,key和value相邻存储,存储16个元素时数组长度为32
TreeMap 红黑树 0 自动以key做自然排序,要求key必须实现Comparable接口
WeakHashMap 数组 + 单向链表 16 个数超过负载因子(默认0.75)指定值时,扩容2倍 当某个”弱键”不再正常使用时,会从WeakHashMap中被自动移除
ConcurrentHashMap 同HashMap 同HashMap 同HashMap 并发场景下的Map
ConcurrentSkipListMap 跳表 0 并发场景下的有序Map
EnumMap 数组 与Enum个数相同 当key是枚举类型时,可以使用EnumMap,操作效率更高
Hashtable 数组 + 链表 11 个数超过负载因子(默认0.75)指定值时,扩容2倍+1 线程安全的Map,目前已废弃
Properties 同Hashtable 同Hashtable 同Hashtable 继承自Hashtable,用于加载属性配置文件

尝试按照日常的使用频率,做如下分类:

名称 使用频率
HashMap、ConcurrentHashMap
LinkedHashMap、TreeMap
IdentityHashMap、WeakHashMap、ConcurrentSkipListMap、EnumMap
Hashtable、Properties 极低

HashMap无疑是最热门的类,本文将继续详细介绍这个类。

1. hash相关的概念

为了更好的理解HashMap和ConcurrentHashMap,这里先介绍下hash相关的概念。

哈希(hash)

Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入通过散列算法变换成固定长度的输出,转换过程称为散列函数哈希函数,转换结果就是散列值,也叫hash code或index。

哈希表(hash table)

哈希表(hash table,也叫散列表),是根据键(key)直接访问访问在内存储存位置的数据结构。 哈希表本质是一个数组,数组中的每一个元素成为一个箱子,箱子中存放的是键值对。

哈希桶(hash bucket),其中存储了hash code对应的所有数据;每个桶中包含了多个槽(slot),即每个hash code可以对应多条数据。

优点:哈希表可以提供快速的操作。

缺点:哈希表通常是基于数组的,数组创建后难于扩展。 也没有一种简便的方法可以以任何一种顺序〔例如从小到大)遍历表中的数据项。

哈希冲突(hash collision)

由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。

在Java语言中,体现为两个对象进行equals比较时不相等,但它们的hashCode相等。

哈希拉链法

由于存在哈希冲突,导致同一个hash code可能对应多条数据;为了解决该问题,将这些hash code相同的数据以链表的形式存储起来,以便正常查找。

这种处理方式的数据结构,形似一个拉链,因此称为拉链法。

hash-zipper

2. HashMap

HashMap基于哈希表(hash table)的Map接口的实现,它并允许空值和空键。(HashMap 类与Hashtable大致等效,不同之处在于它是不同步的,并且允许为null。)该类不保证映射的顺序,它不能保证顺序会随着时间的推移保持恒定。jdk1.8中的数据结构如下:

map-data-structure

数据table即哈希桶数组,数组中每个元素都是一个哈希桶,每个哈希桶中以链表或红黑树的方式存储多个数据。下面从介绍HashMap的哈希函数和扩容机制。

新增数据

HashMap外层结构是一个组数,数组的长度是固定的,需要考虑扩容问题。默认情况下,初始容量为16。

调用put方法添加元素时的流程如下:

put

其中有几个需要重点关注的步骤:哈希函数、扩容机制。

哈希函数

HashMap通过哈希函数计算key的哈希值,达到快速定位数组下标的目的。对于哈希函数,总是希望计算后的结果可以均匀分布在数组中,从而提高存取性能。

一个优质的哈希函数对于HashMap的性能提升,是至关重要的。

HashMap中哈希函数的伪代码如下:

int h = key.hashCode();//1. 获得key的哈希值

// int hash ^= (h >>> 20) ^ (h >>> 12);
// hash = h ^ (h >>> 7) ^ (h >>> 4); // 2. jdk1.7中的hash计算方式,对h进行多次右移、异或运算。

int hash = h ^ (h >>> 16);//2. jdk1.8中的hash计算方式,对h做右移、异或运算

int index = (table.length - 1) & hash;//3. 取模运算,获得数组下标

计算过程

注意:int类型是一个32位的二进制数。

第一步计算hashCode,不再赘述。

第二步,jdk1.7的计算方式,保证了对象的hashCode的32位值只要有一位发生改变,整个hash返回值就会改变,高位的变化会反应到低位里。

第二步,jdk1.8的计算方式,保证了对象的hashCode的高16位的变化能反应到低16位中,相比较而言减少了过多的位运算,是一种折中的设计。

第三步,HashMap的容量长度固定为2的n次方,当length总是2的n次方时,该计算方式与hash%length相同,即对hash取模,但是&比%效率更高。

HashMap的容量长度固定为2的n次方,是为了用位运算替换%运算,提高效率。
另外,当数组长度为2的n次幂时,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀。

扩容机制

HashMap的扩容需要满足两个条件:当前数据存储的数量(即size())大小必须大于等于阈值;当前加入的数据是否发生了hash冲突。

1)创建一个新的Entry空数组,长度是原来的2倍。
2)遍历原Entry数组,把所有的Entry重新Hash到新数组里。为什么要重新Hash呢?因为长度扩大以后,Hash的规则也随之改变了。

3. 小结

本文整理了java.util包下的Map相关类,充分理解他们的适用场景,以便在使用时合理挑选。后面又介绍了HashMap的哈希函数和扩容机制,对HashMap的深入理解,就是对相关数据结构及算法的深入理解。

参考的文章

Java 8系列之重新认识HashMap
Java集合之LinkedHashMap
java中key值可以重复的map:IdentityHashMap
Hash(散列函数)百度百科
夯实Java基础系列19
搞iOS的,面试官问Hash干嘛?原因远比我下面要介绍的多
Java中hashCode()方法以及HashMap()中hash()方法


文章作者: 沉迷思考的鱼
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 沉迷思考的鱼 !
评论
 上一篇
jOOQ –通过java语言以最简单的形式写SQL jOOQ –通过java语言以最简单的形式写SQL
当下我们使用的ORM框架中,Hibernate/Mybatis占了半边天,它们都有各自的优势和使用场景。 最近发现了一个之前从来没用的ORM框架jOOQ,非常有意思,为数据处理提供了一种全新的方式。 1. jOOQ是什么JOOQ(Java
2020-02-14
下一篇 
Java模块化开发通用设计指南 Java模块化开发通用设计指南
模块化不仅仅是一个实现问题,也是一个设计和架构的问题。通过模块化,可以应对需求、环境、团队以及其他不可预见事件所带来的变化。 本章将讨论模块化开发通用设计指南,以提高使用模块所构建系统的可维护性、灵活性和可重用性,这些模式和设计实践中的大部
2019-10-28
  目录