LinkedHashMap源码解读
程序员文章站
2024-02-26 19:49:22
...
LinkedHashMap是HashMap的子类，唯一的区别在于LinkedHashMap对顺序的维护，是有序的
构造函数
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}构造函数参数容量，加载因子都继承hashMap，唯一的区分在于对于属性accessOrder的维护
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
private final boolean accessOrder;accessOrder字段表示对顺序的维护。true表示按照访问顺序，false表示按照插入顺序（插入可能不是在尾部顺序添加，可能是按照索引添加，顺序可能不一致）
LinkedHashMap构造默认是维护元素插入的顺序
linkedHashMap的数据结构的最小单元
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);
}
/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}在HashMap.Entry的基础上新增了两个属性before,after 表示 顺序上的前一个元素的地址和后一个元素的地址，而原next只是表示在一个数组位置处的链表上的，下一个元素位置。
而且，LinkedHashMap对构造器中的init方法重写
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();
}
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}构造LinkedHashMap的时候就会创建一个header节点，不放在数组中，只是用来维护顺序
存放元素
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);
return null;
}void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}* 调用remove方法，将当前元素从顺序中移除，使得它的前面和后面形成顺序关系，当前元素的顺序after、before都没有指向。
* 后面的addBefore方法，是将当前元素和header节点，和header节点的下一个节点构成顺序，结果是加到header前面，也就是链表末尾，形成双向链表，就是按照LinkedList的数据结构维护顺序
而且，不论是accessOrder是true还是false都是会调用addBefore方法，将新加的元素放到链表末尾
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
查询元素
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}如何进行遍历
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}这类是LinkedHashMap实现迭代的最上层的类，如果modCount!=expectedModCount就是抛出异常，就是fast-fail机制，
这种机制，使得数据结构不能在迭代的期间发生更改，也就不是线程安全的。
* LinkedHashMap错误的迭代方式,按照hashMap取出key，在获取值
public static void loopHashMap(LinkedHashMap<String, String> map ){
Set<String> keySet = map.keySet();
Iterator<String> iterator = keySet.iterator();
while(iterator.hasNext()){
System.out.print(map.get(iterator.next()));
}
System.out.println();
}public static void main(String[] args) {
LinkedHashMap<String, String> lhm = new LinkedHashMap<String, String>(16, 0.75f, true);
loopHashMap(lhm);
}LinkedHashMap调用get方法的时候，如果accessOrder=true,会调用recordAccess修改modCount数值，导致modCount!=exceptedModCount抛出异常,不建议使用key，在获取值的方式进行遍历。
* 正确的迭代方式
public static void loopHashMap(LinkedHashMap<String, String> map ){
Set<Entry<String, String>> entrySet = map.entrySet();
Iterator<Entry<String, String>> iterator = entrySet.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next().getValue());
}
System.out.println();
}
验证LinkedHashMap，在accessOrder为true的顺序，当前操作的元素会放到链表末尾
public static void main(String[] args) {
LinkedHashMap<String, String> lhm = new LinkedHashMap<String, String>(16, 0.75f, true);
lhm.put("1", "1");
lhm.put("2", "2");
lhm.put("3", "3");
lhm.put("4", "4");
loopHashMap(lhm);
lhm.get("1");
loopHashMap(lhm);
lhm.get("4");
loopHashMap(lhm);
}输出结果
第一次遍历，最后放的元素是4，元素4会放到链表末尾
第二次遍历，先操作元素1，元素1会放到链表末尾
第三次遍历，操作元素4，元素4会放到链表末尾
1234
2341
2314验证accessOrder为false时候，LinkedHashMap是按照元素的添加顺序遍历
public static void main(String[] args) {
LinkedHashMap<String, String> lhm = new LinkedHashMap<String, String>(16, 0.75f, false);
lhm.put("1", "1");
lhm.put("2", "2");
lhm.put("3", "3");
lhm.put("4", "4");
loopHashMap(lhm);
lhm.get("1");
loopHashMap(lhm);
lhm.get("4");
loopHashMap(lhm);
}输出
1234
1234
1234总结：accessOrder为true，按照元素的访问顺序，get(key)方法会改变顺序
accessOrder为false，按照元素的添加顺序，get(key)方法不会改变顺序
参考文章：http://www.cnblogs.com/xrq730/p/5052323.html
上一篇： 对象间的联动----观察者模式