Android LinkedHashMap 解析

发表于 | 分类于 | 阅读次数

LinkedHashMap 概述

LinkedHashMap 是哈希表和链表的Map实现，具有可预测的迭代次序。LinkedHashMap 允许 key和value 为null。LinkedHashMap 和HashMap的不同之处在于 LinkedHashMap 维护了一个双向链表，运行于所有的条目。该链表定义了迭代排序，通常是定义了插入顺序。

注意: 如果将key 重新插入map中 则插入顺序不受影响（如果m.containsKey（k)在调用之前立即返回true，则调用m.put（k，v）时，将键k重新插入到映射m中）

LinkedHashMap 的实现

对于LinkedHashMap 继承了HashMap 底层使用哈希表与双向链表来保存所有元素。 操作基本和HashMap 一样。

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

构造方法

LinkedHashMap 有五个构造方法

  • LinkedHashMap() 默认构造方法 初始化一个空的插入顺序的LinkedHashMap capacity (16)和 load factor (0.75)
1
2
3
4
5
6
7
8

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}
  • LinkedHashMap(int initialCapacity) 根据初始容量initialCapacity 和默认0.75 load factor(0.75)的负载系数初始化一个空的插入顺序的LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the specified initial capacity and a default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity
 * @throws IllegalArgumentException if the initial capacity is negative
 */
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
  • LinkedHashMap(int initialCapacity, float loadFactor) 根据初始容量initialCapacity和负载系数loadFactor初始化一个空的插入顺序的LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the specified initial capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
  • LinkedHashMap(Map<? extends K, ? extends V> m) 根据传入的map 初始化一个和map 一样插入顺序的LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
 * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
 * instance is created with a default load factor (0.75) and an initial
 * capacity sufficient to hold the mappings in the specified map.
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
  • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 根据初始容量initialCapacity、负载系数loadFactor 和 排序方式accessOrder(true 为 访问顺序 false为插入顺序) 初始化一个空的LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

存取

  • LinkedHashMap 重写了HashMap 的 public V get(Object key) 方法 当排序方式为 访问顺序时（accessOrder 为 true）会把访问的节点放到队尾
1
2
3
4
5
6
7
8

public V get(Object key) {
  	Node<K,V> e;
  	if ((e = getNode(hash(key), key)) == null)
  	    return null;
  	if (accessOrder)//如果是访问顺序是 则进行排序
  	    afterNodeAccess(e);
  	return e.value;
}

afterNodeAccess(e) 将访问的节点放到队尾 方法具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
  • HashMap 的put 方法
1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

然后我们看看putVal方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
            boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
                }
            }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);//这个方法在LinkedHashMap中实现
    return null;
}

afterNodeInsertion 的实现

1
2
3
4
5
6
7

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

这个方法可能删除最少使用的元素

具体使用实例

  • 排序方法为 访问顺序即
1
2
3
4
5
6
7
8
9
10
11

public static void main(String[] args) {
    LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>(0, 0.75f, true);
    linkedHashMap.put(0, "张三");
    linkedHashMap.put(1, "李四");
    linkedHashMap.put(2, "王二");
    linkedHashMap.put(3, "麻子");
    linkedHashMap.get(1);//访问之前顺序是插入顺序
    for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
        System.out.println(" key: " + entry.getKey() + " value:" + entry.getValue());
    }
}

输出结果

 key: 0 value:张三
 key: 2 value:王二
 key: 3 value:麻子
 key: 1 value:李四

可以看到 输出的顺序 key=1 的在队尾

1
2
3
4
5
6
7
8
9

 LinkedHashMap<Integer, String> insertLinkedMap = new LinkedHashMap<Integer, String>(0, 0.75f, false);
    insertLinkedMap.put(1, "李四");
    insertLinkedMap.put(0, "张三");
    insertLinkedMap.put(2, "王二");
    insertLinkedMap.put(3, "麻子");
    insertLinkedMap.get(1);
    for (Map.Entry<Integer, String> entry : insertLinkedMap.entrySet()) {
        System.out.println(" key: " + entry.getKey() + " value:" + entry.getValue());
    }

输出结果

 key: 1 value:李四
 key: 0 value:张三
 key: 2 value:王二
 key: 3 value:麻子

输出顺序不会变化。

暂时分析到这，以后继续补充。