Java 杂谈

Java - Map 集合简单介绍

2019-02-08  本文已影响0人  希尔大

本文简单介绍一下 Java 中 Map 集合,包括 HashMap,HashTable,LinkedHashMap。

HashMap

HashMap 内部用于存放键值对<key,value>,其中 key 可以为null。

HashMap 内部使用数组加链表(1.8+红黑树)的结构实现。数组元素的类型为 Entry,Entry 是链表的节点,也代表了一个键值对。

HashMap 初始化时可以指定两个参数:initialCapacity(默认为16) 与 loadFactor(默认为0.75)。

Entry > (int)(capacity * loadFactor) 时,则会进行扩容,每次扩容到 capacity * 2

put 数据时,会计算 key 的 hash 并求模,得到放入 Entry[] 的下标,其中 null key 坐标为 0。写入对应链表(1.8超过8就转为红黑树)。其中计算hash使用如下公式:

index = hash(key) & (capacity - 1)

使用 & 具有较好的性能,限制 capacity 为 2的n方, 就保证了取模结果的离散型。

在迭代map时,另外的线程修改Map,会抛出 ConcurrentModificationException, 在迭代开始时,Map 迭代器会得到当前 Map 的修改次数,若在迭代过程中修改次数发生了变化,则会抛出该异常。

另外 HashSet 内部是使用 HashMap 的 key 的特性实现的。

HashTable

算是已经被弃用。

与 HashMap 的区别:

LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用 LinkedHashMap。

LinkedHashMap 实现与 HashMap 的不同之处在于,LinkedHashMap 维护着一个运行于所有元素的双重链接列表。此链接列表标定了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。

插入顺序: 保留元素插入的顺序。
访问顺序: get() 方法访问元素的顺序,当元素访问后,元素放入链表的末尾,以此来达成访问顺序的维护,使用构造函数的 accessOrder=true 开启。

LinkedHashMap 允许插入 key 为 null,且不是线程安全的。

LinkedHashMap 的 Entry 关键代码如下, before, after 即为双向链表的前置与后置引用:

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    Entry<K,V> before, after;
    ……
}

当添加了新的元素并且 Map 已满时,可以选择删除掉末尾的元素,如果方法 removeEldestEntry(Entry<K,V> eldest) 返回 false,则不会进行删除(默认),反之则会进行删除。使用该特性,可以使用 LinkedHashMap 构建 LRU 缓存。


参考:
Java集合学习指南_Java开发中文手册[PDF]下载-极客学院Wiki

上一篇 下一篇

猜你喜欢

热点阅读