JavaJava集合框架源码剖析:LinkedHashSet 和 LinkedHashMap

Java
LinkedHashMapHashMap有怎么着界别和联络?为啥LinkedHashMap会具备更快的迭代速度?LinkedHashSetLinkedHashMap怀有啥样的内在联系?本文从数据结构和算法层面,结合生动图解为读者一一解答。

本文github地址

总体介绍

若果你已看过前边境海关于HashSetHashMap,以及TreeSetTreeMap的讲解,一定能够想到本文将要教师的LinkedHashSetLinkedHashMap实质上也是二次事。LinkedHashSetLinkedHashMap在Java里也负有一样的兑现,前者仅仅是对后者做了一层包装,约等于说LinkedHashSet个中有七个LinkedHashMap(适配器格局)。因而本文将根本分析LinkedHashMap

LinkedHashMap实现了Map接口,即允许放入keynull的因素,也允许插入valuenull的因素。从名字上得以观望该容器是linked
list
HashMap的混合体,也便是说它同时满足HashMaplinked
list
的少数特征。可将LinkedHashMap用作采取linked
list
增强的HashMap

Java 1

事实上LinkedHashMapHashMap的直白子类,互相唯一的分化是LinkedHashMapHashMap的底蕴上,选取双向链表(doubly-linked
list)的款式将兼具entry连接起来,那样是为保证成分的迭代顺序跟插入顺序相同
。上海体育地方给出了LinkedHashMap的构造图,主体部分跟HashMap统统等同,多了header本着双向链表的底部(是三个哑元),该双向链表的迭代顺序正是entry的插入顺序

而外能够保迭代历顺序,那种协会还有三个功利:迭代LinkedHashMap时不需求像HashMap那样遍历整个table,而只需求直接遍历header针对的双向链表即可,也正是说LinkedHashMap的迭代时间就只跟entry的个数相关,而跟table的大小毫不相关。

有四个参数能够影响LinkedHashMap的属性:开端体量(inital
capacity)和负载周全(load
factor)。初步容积内定了开始table的大小,负载全面用来钦赐自动扩大体量的临界值。当entry的多寡超过capacity*load_factor时,容器将活动扩大容积同仁一视复哈希。对于插入成分较多的光景,将开首体量设大能够收缩重复哈希的次数。

将对象放入到LinkedHashMapLinkedHashSet中时,有三个办法须要特地关怀:hashCode()equals()hashCode()形式决定了目的会被内置哪个bucket里,当三个对象的哈希值顶牛时,equals()形式决定了那些目的是或不是是“同二个对象”。所以,假若要将自定义的对象放入到LinkedHashMapLinkedHashSet中,需要*@Override*hashCode()equals()方法。

经过如下格局得以获得3个跟源Map 迭代逐条一样的LinkedHashMap

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

鉴于品质原因,LinkedHashMap黑白同步的(not
synchronized),假若急需在多线程环境使用,需要程序员手动同步;只怕通过如下情势将LinkedHashMap包装成(wrapped)同步的:

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

格局分析

get()

get(Object key)办法依照内定的key值再次回到对应的value。该格局跟HashMap.get()办法的流程差不离全盘相同,读者可活动参照前文,那里不再赘言。

put()

put(K key, V value)办法是将点名的key, value对丰盛到map里。该格局首先会对map做叁回搜索,看是或不是包蕴该元组,要是已经包括则直接重返,查找进度看似于get()措施;若是没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry

注意,这里的插入有两重意思

  1. table的角度看,新的entry亟待插入到相应的bucket里,当有哈希争辩时,选择头插法将新的entry安顿到冲突链表的底部。
  2. header的角度看,新的entry亟待插入到双向链表的尾巴。

Java 2

addEntry()代码如下:

// LinkedHashMap.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从双向链表中删去,同时修改链表中前边以及背后成分的应和引用。

Java 3

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;
    }
    ......
}

相关文章