JDK的LinkedHashMap怎么使用_程序开发

JDK的LinkedHashMap怎么使用

创始人

2024-12-25 23:02:01

0次

package org.corey.demo;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
Map map = new LinkedHashMap(4);
map.put("1", "corey");
map.put("2", "syna");
map.put("3", "bobo");
Iterator it=map.keySet().iterator();
System.out.println("-------------------------linked hash map----------------------");
while(it.hasNext()){
String key=(String)it.next();
System.out.println(key+":"+map.get(key));
}
Map map2 = new HashMap(4);
map2.put("1", "corey");
map2.put("2", "syna");
map2.put("3", "bobo");
Iterator it2=map2.keySet().iterator();
System.out.println("-------------------------hash map----------------------");
while(it2.hasNext()){
String key=(String)it2.next();
System.out.println(key+":"+map2.get(key));
}
}
}

console:

-------------------------linked hash map----------------------
1:corey
2:syna
3:bobo
-------------------------hash map----------------------
2:syna
1:corey
3:bobo

从而可见，我们的问题得到了解决；

现在我们从LinkEdHashMap代码内部来详细的分析其实现原理；

private transient Entry header;

在LinkedHashMap中含有一个Entry的属性；注意，这个Entry不是上一次我们在HashMap中见到的单向Entry,他被扩充了：

private static class Entry extends HashMap.Entry {
//他有两个指针分别指向了before和after的Entry
//请注意，不要把next和他们混淆了，next的用处还是和HashMap中一//样；
Entry before, after;
Entry(int hash, K key, V value, HashMap.Entry next) {
super(hash, key, value, next);
}
private void remove() {
before.after = after;
after.before = before;
}
、
//在当前节点前面插入节点；
private void addBefore(Entry existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void recordRemoval(HashMap m) {
remove();
}
}

因为LinkedHashMap是继承的HashMap,那么他们的增删改的操作基本一致，只是利用了模板模式具有了不同的实现；
我们来看一下put方法吧；
下面是HashMap的put方法：

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry 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 addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}

在上一节中我们已经详细的分析过了，在LinkedHashMap中被重载的方法是addEntry;

void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
Entry eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}

void createEntry(int hash, K key, V value, int bucketIndex) {
//和以前一样，首先操作了table序列的链表枝条；
HashMap.Entry old = table[bucketIndex];
Entry e = new Entry(hash, key, value, old);
table[bucketIndex] = e;
//关键在于这一步做了什么；我们知道他在header之前插入了Entry;
e.addBefore(header);
size++;
}

Header元素在构造的时候被初始化，记得吗，这个方法是HashMap在构造函数中利用模板模式传下来的

void init() {
header = new Entry(-1, null, null, null);
header.before = header.after = header;
}

开始的时候Header头尾都是指向自身的；

JDK的LinkedHashMap怎么使用

第二步的时候就是被e.addBefore(header);

private void addBefore(Entry existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

JDK的LinkedHashMap怎么使用
如果再put那么就是：

JDK的LinkedHashMap怎么使用
我们再来看一看他的keySet是如何得到的：

重载了newKeyIterator() 的方法：

Iterator newKeyIterator() { return new KeyIterator(); }

我们看一下迭代器是如何实现的：

private abstract class LinkedHashIterator implements Iterator {
//从开始的图3我们可见，第一次加入的节点是位于header.after的位置；
Entry nextEntry = header.after;
Entry lastReturned = null;
int expectedModCount = modCount;
//nextnEntry不是header就不是末尾
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
Entry nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
//指针沿着after往下走
Entry e = lastReturned = nextEntry;
//预先把nextEntry移动到了下一位
nextEntry = e.after;
return e;
}
}

把next方法抽象出去是因为values和keySet的迭代次序是一样的，就是返回的数值不同，所以可以把
Entry的遍历方式推到上层，而values和keys分别留给子类实现；

private class KeyIterator extends LinkedHashIterator {
public K next() { return nextEntry().getKey(); }
}
private class KeyIterator extends LinkedHashIterator {
public K next() { return nextEntry().getKey(); }
}
private class ValueIterator extends LinkedHashIterator {
public V next() { return nextEntry().value; }
}
private class EntryIterator extends LinkedHashIterator> {
public Map.Entry next() { return nextEntry(); }
}

上一篇：JDK的HashMap怎么使用

下一篇：JDK的Set源码分析

JDK的LinkedHashMap怎么使用

相关内容

热门资讯