Java 常用集合类 Map

Map 继承自 Iterator 接口,表示一种映射关系,其中的元素是以键值对(key-value)的形式存储的,能够根据 key 快速查找 value;key 不可重复,value 值可以重复。

Map 常用主要有 HashMap、Hashtable、TreeMap、WeakHashMap、LinkedHashMap 等几种实现方式。Java Map 的架构图如下:

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

继承以下接口:

  • AbstractMap,Map,规定了 Map 的操作规范
  • Cloneable 支持克隆
  • Serializable 表示序列化

HashMap 是最常用的 Map 之一,存储 key-value 的散列表,是基于“拉链法”实现。HashMap 的实现不是同步的,即不是线程安全的,一般多用于单线程中。key 和 value 都可以为 null。注意,HashMap 中的映射不是有序的。

拉链法,链地址法,就是把具有相同散列地址的关键字的值放在一个单链表中。有m个散列地址就有m个链表,同时用指针数组 T[0..m-1] 存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以 T[i] 为头指针的单链表中。

++在 jdk1.8 中当链表长度大于一定长度时,使用平衡树代替链表++

HashMap 由一个链表数组实现,链表节点由 Entry(key, value, next) 表示。同时在内部维护了一个容量(Capacity),表示 HashMap 可以存储的键值对的数量(默认初始容量为16)和扩容因子,当 HashMap 中元素的数量达到 capacity * loadfactor 时,

主要方法实现

Put 操作

根据 key 值得到 hashCode,然后用这个 hashCode 与数组的长度进行模运算,得到一个 int 值,就是 Entry(key, value, next) 对象要存储在链表数组的位置。然后遍历链表(Entry),如果 key 存在则更新对应的 value,否则插入链表表头

当元素数量超过扩容阈值时,进行扩容,并重新计算每个元素的位置。当数组的数量达到 Integer.MAX_VALUE,不进行扩容,修改阈值为 Integer.MAX_VALUE

Get 操作

根据 key 值得到 hashCode,然后用这个 hashCode 获取数组下标对应的 Entry(key, value, next),然后遍历链表(Entry),如果 key 存在则返回对应的 value,否认则返回 null。

对于 null 键值,使用 putForNullKey()getForNullKey() 来处理

初始化

为了防止大量插入 HashMap 导致频繁扩容,造成性能损失,建议在能够预估数据量大小的时候设置出事容量。容量默认为16,如果设置数量,会变为最接近的2的次幂的数量。

Hashtable

public class Hashtable<K, V> extends Dictionary<K, V> 
    implements Map<K, V>, Cloneable, Serializable {

继承以下接口:

  • Dictionary 接口,而没有继承 AbstractMap
  • Map,规定了 Map 的操作规范
  • Cloneable 支持克隆
  • Serializable 表示序列化

Hashtable 与 HashMap 一样是基于“拉链法”实现的散列表,存储 key-value。Hashtable 的实现都是同步的,是线程安全的,一般多用于多线程中。key 和 value 都不可以为 null。注意,Hashtable 中的映射也不是有序的。

设计思想与 HashMap 相同,使用链表数组存储元素。

HashMap 与 Hashtable 的区别

继承接口不同

HashMap 继承于 AbstractMap,而 Hashtable 继承于 Dictionary,Dictionary 是JDK1.0引入的。API 相比Map 较少,而且遍历方式不同:Dictionary 一般是通过 Enumeration 遍历,Map 是通过 Iterator 遍历。 不过 Hashtable 即实现了 Dictionary 同时也实现了 Map。两种迭代都是 fail-fast 的

两种遍历的区别:Iterator 对与数组从0开始,Enumeration 则从 index-1(数组末尾)开始

对null值处理

HashMap 支持 key 或 value 为 null。Hashtable 既不支持 key 也不支持 value 为 null。

线程安全不同

HashMap 的实现是非同步的,不是线程安全的,而 Hashtable 的实现是同步的(synchronized),线程安全。在多线程中使用 HashMap 需要进行同步处理。

Collections 类提供的 synchronizedMap 静态方法,可以获得同步的 HashMap,或者使用 java.util.concurrent 包里的 ConcurrentHashMap。

扩容逻辑不同

HashMap 默认的容量大小是16,扩容因子0.75,每次扩容将容量增加一倍:newCapacity = 2 * table.length

Hashtable 默认的容量大小是11,扩容因子0.75,每次扩容将容量增加一倍再加1:newCapacity = oldCapacity * 2 + 1

key 的哈希值计算不同

HashMap 自定义了哈希算法,添加了动扰函数,通过对默认 hashCode 的高低位运算,使分布更均匀,具体可参考 HashMap 的 hash 方法原理

Hashtable 则使用了默认的 hashCode。

HashSet

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

继承以下接口:

  • AbstractSet,Set,规定了 Set 的操作规范
  • Cloneable 支持克隆
  • Serializable 表示序列化

HashSet 是 Set 集合的实现,内部逻辑是通过 HashMap 实现,存入 HashSet 的值,当作 HashMap 的 key 存入 HashMap,value 为 null。因为 HashMap 的 key 允许为null,因此 HashSet 允许存入 null 值。

LinkedHashMap

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

继承自 HashMap,有 HashMap 的一切特性。通过重写 addEntry()createEntry()put() 时调用的方法)实现了新的双向链表实现,记录了元素的插入顺序,在用 Iterator 遍历时,保证先得到的记录是先插入的。也可以指定以访问顺序排序(构造时指定)。

一般来说 LinkedHashMap 在遍历的时候会比 HashMap 慢,除非当 HashMap 容量很大,实际数据较少时。LinkedHashMap 的遍历速度只和实际数据有关,HashMap 的遍历速度和容量有关。

按访问顺序遍历的实现

getEntry() 方法查找到元素后,判断当排序模式 accessOrder 为true时(按访问顺序排序),将最新访问的元素添加到双向链表的表头,并删除原位置上的元素。这种排序很适合构建LRU缓存(Least Recently Used,最近最少使用)。

WeakHashMap

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V> 

继承以下接口:
– AbstractMap,Map,规定了 Map 的操作规范

WeakHashMap 一样是基于“拉链法”实现的散列表,存储 key-value。非线程安全的,一般用于单线程中。WeakHashMap 中的键是“弱键”,当“弱键”被GC回收时,对应的键值对也会被从 WeakHashMap 中删除。

WeakHashMap 没有继承 Cloneable 和 Serializable 接口,不能够克隆和序列化。其他方法与 HashMap 的实现大致相同。

什么是强引用?弱引用?

简单介绍,Java 中有四种引用包括强引用,软引用,弱引用,虚引用。

  • 强引用:只要引用存在,垃圾回收器永远不会回收。
  • 软引用(SoftReference):非必须引用,内存溢出之前进行回收。
  • 弱引用(WeakReference):第二次垃圾回收时回收。
  • 虚引用(PhantomReference):垃圾回收时回收,无法通过引用取到对象值。

“弱键”通过 WeakReference 和 ReferenceQueue 实现。使用“弱键”的目的:实现对 key-value 的动态回收。当键不再被使用到时,GC会回收它,WeakReference 也会将“弱键”对应的键值对删除。

TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

继承以下接口:

  • AbstractMap
  • NavigableMap,继承于 SortedMap,支持导航函数的接口,SortedMap 有序的 key-value 映射接口
  • Cloneable 支持克隆
  • Serializable 表示序列化

TreeMap 是有序的散列表,通过红黑树实现的(每一个 key-value 是树的一个节点)。方法是非同步的,一般用于单线程中存储有序的 key-value 集合。

TreeMap 存储时会根据 key 来对 key-value 进行排序,其中排序方式也是分为两种,一种是自然排序,一种是定制排序,具体取决于使用的构造方法。

CorrentHashMap

package java.util.concurrent;

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable 

继承以下接口:

  • AbstractMap
  • ConcurrentMap,线程安全的 Map 实现
  • Serializable 表示序列化

ConcurrentHashMap 是线程安全的散列表,不支持克隆。与 HashMap 类似使用数组和链表的存储结果,内部使用了一种可重入锁来实现线程安全。在多线程程序中可以使用 ConcurrentHashMap 代替 HashMap。


Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

1 + 2 =