对于Java的集合认知一直以来都不够清晰,现在特地对Map
做一次总结,以加深印象。
Map
接口位于java.util包下,该包下一共提供了如下具体的实现类(基于JDK1.8),java.util包中开放的实现类如下图所示:
涉及的接口和抽象类有如下几个:
名称 | 说明 |
---|---|
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相同的数据以链表的形式存储起来,以便正常查找。
这种处理方式的数据结构,形似一个拉链,因此称为拉链法。
2. HashMap
HashMap基于哈希表(hash table)的Map接口的实现,它并允许空值和空键。(HashMap 类与Hashtable大致等效,不同之处在于它是不同步的,并且允许为null。)该类不保证映射的顺序,它不能保证顺序会随着时间的推移保持恒定。jdk1.8中的数据结构如下:
数据table即哈希桶数组,数组中每个元素都是一个哈希桶,每个哈希桶中以链表或红黑树的方式存储多个数据。下面从介绍HashMap的哈希函数和扩容机制。
新增数据
HashMap外层结构是一个组数,数组的长度是固定的,需要考虑扩容问题。默认情况下,初始容量为16。
调用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()方法