#yyds干货盘点# Map - LinkedHashSet&Map源码解析

少年意气强不羁，虎胁插翼白日飞。这篇文章主要讲述#yyds干货盘点# Map - LinkedHashSet&Map源码解析相关的知识，希望能为你提供帮助。
Map - LinkedHashSet& Map源码解析
事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(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时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
将对象放入到LinkedHashMap或LinkedHashSet中时，有两个方法需要特别关心: hashCode()?和equals()?。hashCode()?方法决定了对象会被放到哪个?bucket?里，当多个对象的哈希值冲突时，?equals()?方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到LinkedHashMap?或LinkedHashSet?中，需要@Override hashCode()?和equals()方法。

方法剖析
get()
get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样，读者可自行参考前文(opens new window)，这里不再赘述。
put()
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

// 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++;

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

remove()
remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。

// 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
【#yyds干货盘点# Map - LinkedHashSet&Map源码解析】前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法。

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;

......