Java源码集合类LinkedHashMap学习1

小咪咪 2022-09-28 13:28 217阅读 0赞

#### 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，那么执行完这个方法就生成了一个结构类似如下图的对象：

![Center][]

接着执行代码: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)，它的内存指向图如下所示：

![Center 1][]

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)执行的结果，组成的双向链表如下图：

![Center 2][]

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

[Center]: /images/20220708/bc8121db206647838e98955f86701469.png
[Center 1]: /images/20220708/e28198e061304633b9361693d86eb144.png
[Center 2]: /images/20220708/196b7616448c454f95bd6f8429633dde.png