Java容器框架分析(七)——LinkedHashSet与LinkedHashMap

2017/2/25 posted in  Java  

如果你已经看过前面关于HashSet和HashMap,以及TreeSet和TreeMap的讲解,一定能够想到本文要讲解的LinkedSet和LinkedHashMap在Java中也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点介绍LinkedHashMap。

LinkedHashMap实现了Map接口,即允许放入key为null的元素,也允许插入value为null的元素。从名字上可以看出该容器是LinkedList和HashMap的混合体,也就是说它同时满足HashMap和LinkedList的某些特性。可以将LinkedHashMap看作采用LinkedList增强的HashMap。

事实上LinkedHashMap是HashMap的直接子类,二者的唯一区别是LinkedHashMap在HashMap的基础上,采用双向链表的形式将所有entry连接起来,这样是为保证元素的迭代顺序和插入顺序相同。

上图给出了LinkedHashMap的结构图,主体部分跟HashMap完全一样,多了header指向双向链表的头部,该双向链表的迭代顺序就是entry的插入顺序。
除了可以保证迭代顺序,这种结构还有一个好处:迭代LinkedHashMap时不需要像HashMap那样遍历整个table,而是只需要直接遍历header指向的双向链表即可。也就说LinkedHashMap的迭代时间就只跟entry的个数有关,和table的大小无关。

有两个参数可以影响 LinkedHashMap 的性能:初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。
将对象放入到 LinkedHashMap 或 LinkedHashSet 中时,有两个方法需要特别关心:hashCode()equals()hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是 “同一个对象”。所以,如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中,需要覆盖hashCode()equals()方法。

通过如下方式可以得到一个跟源Map迭代顺序一样的LinkedHashMap:

void foo(Map m) {
    Map copy = new LinkedHashMap(m);
    ...
}

出于性能原因,LinkedHashMap是非线程安全的,如果需要在多线程环境使用,需要程序呀手动进行同步;或者通过如下方式将LinkedHashMap包装成同步的:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

常用方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value.该方法的流程和HashMap的实现方式基本一样,可参考前文。

put()

put(K key,V value)方法是将指定的key,value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于get()方法;如没有找到则会通过addEntry(int hash,K key,V value,int bucketIndex)方法插入新的entry。
PS.这里的插入有两重含义:

  1. 从table的角度来看,新的entry需要插入到对应的bucket里,当有哈希冲突时,采用头插法将新的entry插入到冲突链表的头部。
  2. 从header的角度,新的entry需要插入到双向链表的尾部。

addEntry()代码如下:

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容,并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表引用header的前面,这样e就成为了双向链表中的最后一个元素。addBefore()的代码如下:

// LinkedHashMap.Entry.addBefor(),将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

仅需要简单修改相关entry的引用而已。

remove()

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除entry(修改链表的引用)。查找过程和get()方法类似。
注意,这里的删除也有两层含义:

  1. 从table的角度看,需要将该entry从对应的bucket里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。
  2. 从header的角度来看,需要将该entry从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。

removeEntryForKey()对应的代码如下:

// LinkedHashMap.removeEntryForKey(),删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

LinkedHashSet

前面已经说过 LinkedHashSet 是对 LinkedHashMap 的简单包装,对 LinkedHashSet 的函数调用都会转换成合适的 LinkedHashMap 方法,因此 LinkedHashSet 的实现非常简单,这里不再赘述。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ......
    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

声明

本系列博文装载自:https://github.com/CarpenterLee/JCFInternals
作者:CarpenterLee