Java源码集合类LinkedHashMap学习1

    xiaoxiao2021-03-25  64

    LinkedHashMap类简介(jdk 1.7.0_67)

    LinkedHashMap类继承了HashMap类,也就是LinkedHashMap类的功能几乎和HashMap一样。而LinkedHashMap类就是扩展了一个双向链表,使得可以按照“键-值”对插入的顺序遍历,这个是在HashMap类中遍历是没有顺序的。LinkedHashMap类可以插入null的key值和value值,以及这个类也是线程不安全的。重点是要了解它是如何实现按“键-值”对插入的顺序遍历的。

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

    LinkedHashMap类中的Entry<K,V>类继承自HashMap.Entry<K,V>类源码如下:

    //这里就只是多了两个属性 private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after;//这两个属性用于构成双链表遍历 Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } //后面源代码省略 }先看如下一段代码:

    public static void main(String[] args){ Map<String, String> linkedMap = new LinkedHashMap<String, String>(); linkedMap.put("k1", "v1"); linkedMap.put("k2", "v2"); linkedMap.put("k3", "v3"); }执行第2行代码的时候,先调用父类HashMap类的HashMap()无参构造函数初始化加载因子和阀值,源码代码如下: //调用无参构造函数 public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; threshold = initialCapacity; init();//LinkedHashMap类中重写了这个方法,所以调用的是LinkedHashMap类中的init()方法 } //LinkedHashMap类中的init()方法 @Override void init() { header = new Entry<>(-1, null, null, null); header.before = header.after = header; }执行方法init()的时候生成了一个Entry对象,就是链表的头部,为了方便理解这里假设header变量指向的引用地址是:0X000,那么执行完这个方法就生成了一个结构类似如下图的对象:

    接着执行代码:linkedMap.put("k1", "v1"),LinkedHashMap类中并没有重写这个方法,它调用的是父类HashMap类中的put(K k, V v)方法,源码如下:

    public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i);//此处调用的是LinkedHashMap类中的该方法,因为重写了该方法(体现了多态性) return null; } put方法中要做的事就是初始化table数组的容量,计算哈希值,根据哈希值算出在table数组中的索引,然后在是保存“键-值”对。关键是看看LinkedHashMap类中方法addEntry()的源码: void addEntry(int hash, K key, V value, int bucketIndex) { super.addEntry(hash, key, value, bucketIndex); // Remove eldest entry if instructed//下面的代码是为了实现LRU算法的缓存用的,这里不用去关心 Entry<K,V> eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }这行代码:super.addEntry(hash, key, value, bucketIndex)它是调用了父类HashMap中的方法,源代码如下: 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 = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex);//此处调用的是LinkedHashMap类中的该方法,因为重写了该方法(体现了多态性) } //LinkedHashMap中的方法 void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry old = table[bucketIndex]; Entry e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; e.addBefore(header); size++; } //LinkedHashMap中的方法 private void addBefore(Entry existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }

    从上面的源码可以看出,父类中HashMap维护了“键-值”对的基本存储结构,也就是说”键—值“对存储在HashMap类中的结构一样。而重点我们就来分析LinkedHashMap类中它是如何建立双向链表的。通过上面main方法中的put代码和方法addBefore(Entry existingEntry)方法来分析。

    代码:linkedMap.put("k1", "v1");假设生成Entry<>对象的地址是:0X001,根据key="k1"计算出的hash值是3214,next为null。分析忽略了具体在table数组中的位置,只分析如何建立双向链表的过程,当执行到e.addBefore(header),它的内存指向图如下所示:

    1.after  = existingEntry,existingEntry它在这里始终是链表的头header,after变量指向的地址是header的地址0X000;

    2.before = existingEntry.before,before变量指向的地址是:0X000;

    3.before.after = this,before指向的是0X000也就是指向header对象的地址,那么before.after也就是等价于header.after指向地址:0X001;

    4.依据上面3可得 after.before指向的地址是:0X001,最后的结果成了一个双向的循环链表。

    代码linkedMap.put("k2", "v2")(假设生成的Entry<>对象为e2,内存地址为0X002,hash值为1243,next=null)执行的结果,组成的双向链表如下图:

    每次put进来一个新的”键—值“对就生成一个Entry<>对象插入到链表header的前面组成一个前后双向的链表,这个就是LinkedHashMap类的关键点,这样我们就可以按照插入的顺序遍历”键—值“对元素了。这里用到了数据结构链表的知识,当我们对未知感到恐惧,是因为我们无知。

    转载请注明原文地址: https://ju.6miu.com/read-35253.html

    最新回复(0)