2018/02/06 20:25

LinkedHashMap 的排序方式有两种：

• 根据写入顺序排序。
• 根据访问顺序排序。

## 数据结构

	@Test
public void test(){
Map<String, Integer> map = new LinkedHashMap<String, Integer>();
map.put("1",1) ;
map.put("2",2) ;
map.put("3",3) ;
map.put("4",4) ;
map.put("5",5) ;
System.out.println(map.toString());

}


    /**
*/

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

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 LinkedHashMap(int initialCapacity,
boolean accessOrder) {
this.accessOrder = accessOrder;
}


## 构造方法

LinkedHashMap 的构造方法:

    public LinkedHashMap() {
super();
accessOrder = false;
}


HashMap 实现：

    public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
throw new IllegalArgumentException("Illegal load factor: " +

threshold = initialCapacity;
init();
}


    @Override
void init() {
header = new Entry<>(-1, null, null, null);
}


## put() 方法

LinkedHashMapput() 方法之前先看看 HashMapput 方法：

    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++;
return null;
}

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);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}


LinkedHashMap 的实现：

        //就是判断是否是根据访问顺序排序，如果是则需要将当前这个 Entry 移动到链表的末尾
void recordAccess(HashMap<K,V> m) {
if (lm.accessOrder) {
lm.modCount++;
remove();
}
}

//调用了 HashMap 的实现，并判断是否需要删除最少使用的 Entry(默认不删除)
void addEntry(int hash, K key, V value, int bucketIndex) {

// Remove eldest entry if instructed
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}

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;
size++;
}

//写入到双向链表中
after  = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}



## get 方法

LinkedHashMap 的 get() 方法也重写了：

    public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;

//多了一个判断是否是按照访问顺序排序，是则将当前的 Entry 移动到链表头部。
e.recordAccess(this);
return e.value;
}

void recordAccess(HashMap<K,V> m) {
if (lm.accessOrder) {
lm.modCount++;

//删除
remove();
//添加到头部
}
}


clear() 清空就要比较简单了：

    //只需要把指针都指向自己即可，原本那些 Entry 没有引用之后就会被 JVM 自动回收。
public void clear() {
super.clear();
}


0 评论
17 收藏
0