Java深入集合--linkedHashMap

LinkedHashMap 源码介绍

 

一、介绍：

     LinkedHashMap 和hashMap 功能类似，都是维护的键值对集合，连遍历 以及方法都类似，唯一的区别在于

hashMap  里面的元素是根据hash值来决定存放位置的，是无序的，而LinkedHashMap 维护的是一个按顺序存放的双向链表，是有序的。

      所谓的双向链表其实是链表的一种。链表：相当于元素 A->B->C ,也就是我可以通过A 找到B ,从而找到C，可以单向移动。而双向链表：A<->B<->C ，也就是说我可以从B  找到 A 和 C，可以双向移动。

 

二、源码分析：

       

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

    我们可以看到 这东西是继承的HashMap 的，说明拥有hashMap 的功能，那么我们具体来看看 不同在哪里呢？

 

   1. 构造函数：

    

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
}

 public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
}

 public LinkedHashMap(int initialCapacity) {
	super(initialCapacity);
        accessOrder = false;
}
我们看到3个构造函数，其实都是访问的super(..),也就是hashMap 的构造，区别就在accessOrder 
来看看它是什么？

 

 

 
     //The iteration ordering method for this linked hash map: <tt>true</tt>
     //for access-order, <tt>false</tt> for insertion-order.
    // 简单说就是这个用来控制元素的顺序，
    // true: 是访问的顺序，也就是谁最先访问，就排在第一位
    // false:存放顺序，就是你put 元素的时候的顺序
    private final boolean accessOrder;

  这里稍后再看怎么用的，我们先来分析核心内部类 Entry 类，这几乎是所有map 都需要的东西。

 

 private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        // 这里我们看到，Entry<K,V>  类里面多了了两个属性，专门来方便我们进行链表的前后移动        // 的
        Entry<K,V> before, after;
        // 这里调用了hashMap 的entry 构造，说明还是用的HashMap 的Entry
	Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
       // ..剩下的稍后说
}

   

 

 

继续来看这些属性怎么利用起来的。对于集合，我们肯定要关注他的 存放元素 和 取元素的方法啦：
当我们找遍整个类的时候发现，没有找到put 方法- -。但是LinkedHashMap 肯定是可以调用put的，因为继承了hashMap,
那我们把 hashMap 的put方法先取出来吧

 

 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        // 这里都是调用 hashMap 计算位置什么的，前面hashMap 已经分析过啦
        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;
                // 这里被重写了 A
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        // 这里被重写了 B 
        addEntry(hash, key, value, i);
        return null;
    }

 

 

  从上面看出和hashMap 没啥区别，关键就看重写的方法啦，特别是e.recordAccess 这个方法 在hashMap     介绍中，不是提到不知道干什么的嘛，这里详细来看看。

    

private static class Entry<K,V> extends HashMap.Entry<K,V> {
	/**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            // 如果参数为true,也就是根据访问顺序
            if (lm.accessOrder) {
                // 迭代控制的变量
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
	
	// 这里我们发现 before和after 虽然定义了属性，是哪儿赋值的呢？为什么不为null呢？
        // 请回到 构造函数，我们发现有一个init()方法，以前是没用的，这里也进行了重写，请看         // 后面init 方法
        private void remove() {
            // 先移除当前这个空节点
            before.after = after;
            after.before = before;
        }
        
	/**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            // 然后将这个空节点 赋值
            after  = existingEntry;
            // 当前节点 ，赋值于标志位的前节点
            before = existingEntry.before;
            // 然后将复制后的节点的 两个属性，继续赋值为空，等待另一个节点的插入
            before.after = this;
            after.before = this;
        }
        // 整个

}

 

  init() 方法：

 

    /**
     * The head of the doubly linked list.
     */
  private transient Entry<K,V> header;
  void init() {
        // 这里默链表 表头是header,并让hash值为-1,其他都为null,仅仅是作为一个标志位
        // 初始化这个节点
        header = new Entry<K,V>(-1, null, null, null);
        // 赋值在这里，默认这是起点，相当于还没有其他元素
        header.before = header.after = header;
    }

 

   可能上面的文字描述很难理解，我们假设：这个双链表结构相当于 一条一节一节连起来的项链，当然每一节肯定有链接前before 和 after 这样的连接位置（属性），中间才是宝石（数据）。然后，一般项链都有一个明显的位置，方便你去下来的（header），那里其实是用来首位相连的，当我们觉得长度不够，需要添加一个宝石的时候，首先会从那里打开，也就是执行（remove）方法，然后把你需要的宝石连接在最后的位置(after  = existingEntry,before = existingEntry.before;);，从程序上来说 就是把那个header 的位置，原先连接器的先取掉掉，那个位置就从新连接新的元素。

    

继续讲解put 方法，继续往下看 还有一个addEntry(hash, key, value, i)方法，也进行了重写

 

    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 存放元素
        createEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        // 这里始终返回的是false，也就是说 方便我们扩展，重写的- -！
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);
        }
 }
 void createEntry(int hash, K key, V value, int bucketIndex) {
        // 通过key 和长度 计算出的位置，去获得那个元素，可能为空
        HashMap.Entry<K,V> old = table[bucketIndex];
        // 然后在这个位置创建一个新元素，并让next 指向old
	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        // 把这个元素放进数组的这个位置
        table[bucketIndex] = e;
        // 然后把header 的after before属性，和元素节点从新连接起来
        // 元素就在header 之前了，也就是可以保证最先访问(这里通过Set 集合遍历顺序是反的- -!)
        e.addBefore(header);
        size++;
    }

 

   上面可以看出，linkedHashMap，元素默认是放在链表前，也就是根据存放顺序放的，而实际情况还是用的hashMap 里面的table 数组，元素位置是随机存放的，只是linkedHashMap扩展，加入了属性，对每个元素存放的位置进行了像链表结构那样的链接。那么当我们设置accessOrder=true 的时候如何才控制根据访问顺序进行排列呢？首先请看get 方法：

    }    // 也进行了重写
    public V get(Object key) {
        // 调用父类的get方法
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        // 这里还是调用的刚才的方法，把当前元素放在header 之前，也就完成了 根据访问顺序排序
        e.recordAccess(this);
        return e.value;
    }

 

上面对该集合实现双链表结构的原理 以及代码大概讲述了一下，可以去看看图例更加清晰，下面继续看看一些方法。

 

 1.keySet()，entrySet（），values方法：
  这里还是调用的父类的，但是它重写了几个方法：
  // 这是重写的
  Iterator<K> newKeyIterator()   { return new KeyIterator();   }
  Iterator<V> newValueIterator() { return new ValueIterator(); }
  terator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
  // 这里返回值方式类似，都是通过 nextEntry()返回不同的内容，但是继承对象变成了LinkedHashIterator，不是原来的  // HashIterator
  private class KeyIterator extends LinkedHashIterator<K> {
	public K next() { return nextEntry().getKey(); }
   }
   // 看看区别吧
   private abstract class LinkedHashIterator<T> implements Iterator<T> {
        // 后一个节点
	Entry<K,V> nextEntry    = header.after;
        // 最后返回的节点
	Entry<K,V> lastReturned = null;

	// 迭代的那个变量控制
	int expectedModCount = modCount;
        // 如果下一个元素师头元素，说明已经到底呢，没有其他元素了
        public boolean hasNext() {
            return nextEntry != header;
	}
       // 获得下一个元素
       Entry<K,V> nextEntry() {
            // 这里就不明白了，当排序参数设置为true 是，有lm.modCount ++,这里进行.next 迭代的时候，老报错
            // 不明白的意义了
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
            // 这里元素迭代完了， 直接抛异常- -，不懂为什么这样设计
            if (nextEntry == header)
                throw new NoSuchElementException();
            // 返回下一个元素，并且将nextEntry 指向下下一个元素
            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
	}
        // 删除
        public void remove() {
            // 这里同上
	    if (lastReturned == null)
		throw new IllegalStateException();
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	    // 这里看出lastReturned 作用就是记录遍历的当前位置，方便删除
            // 这里直接调用removeEntryForKey 方法就好了，这个- - 看着不爽，反正又不要返回值
            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
	}
   }

 

 

2.containsKey() 这里是访问hashMap 的方法，这里就不说了。
   containsValue() 进行了重写

   public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        // 这里仅仅是通过链表的两个属性进行遍历，hashMap 是通过table 数组进行遍历，效果差不        // 多
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;

 

最近我不能直接在iteye 进行编辑，不知道为什么，老是卡死，都是记事本写了，复制过来，没图片和格式，望见谅！

总结：1.linkedhashMap 是继承于hashMap 也就是拥有了他一切功能

           2.他是双链表结构，好处可以存取顺序

           3.可以进行扩展，用来对那些最近访问元素的优先获得权

           4.存放效率，如果构造参数设置为true ，由于要维护链表结构，效率比hashMap 低一点，但是默认是放在最后，能直接从header 进行操作，效率其实没多大影响。

           5.get 元素类似。如果构造参数为true ,需要进行链表的操作，效率低于hashMap,否则效率一样。

           6.通过Iterator.keySet().iterator() 这样迭代，数据3000000 的情况，数据默认一个数字，linkedhashMap 慢几十毫秒，基本没影响。如果构造参数为true ，则linkedHashMap 迭代异常。

             

        // 我内存不够，i大了要内存溢出
   	public static  void test(){
		LinkedHashMap p = new  LinkedHashMap(3000000,0.75f,false);
		for(int i =0;i<3000000;i++){
			p.put(i, 2);
		}
		long a = System.currentTimeMillis();
		Iterator it1 = p.keySet().iterator();
		while(it1.hasNext()){
			Object o = it1.next();
			p.get(o);
		}
		long b = System.currentTimeMillis();
		System.out.println(b-a);// 250 毫秒
		
	}
	public static void test2(){
		Map m = new HashMap(3000000);
		for(int i =0;i<3000000;i++){
			m.put(i, 2);
		}
		long a = System.currentTimeMillis();
		Iterator it1 = m.keySet().iterator();
		while(it1.hasNext()){
			Object o = it1.next();
			m.get(o);
		}
		long b = System.currentTimeMillis();
		System.out.println(b-a);// 210 毫秒
	}

评论

6 楼 greemranqq 2013-09-03  

hailongshih 写道

看的有些费解,有些内部实现复杂没看懂

我才看的时候也是一样的 ，建议 从头开始看,你看我的目录，我从 简单的看起

5 楼 greemranqq 2013-09-01  

hailongshih 写道

看的有些费解,有些内部实现复杂没看懂

可能我写得不好，而且排版很差，见谅啊，后面会改进的。
1。建议如果你是分析源代码，可以参考我的说明
2。如果你仅仅了解其中一部分代码原理，就只看那相关部分
3。如果只是从头开始看，如果不细看并且分析，其实没有意义的，我自己大概写过这个东西，才理解一些，才写的。

4 楼 greemranqq 2013-09-01  

steafler 写道

理论来讲，LinkedHashMap的增删效率应该更高

LinkedHashMap 调用的是hashMap 的put方法，并且有额外的开销，为什么会更高呢？

3 楼 dingran 2013-08-28  

我之前看过李刚的一本书：

疯狂java--突破程序员基本功的16课

这本书对java集合方面做了很多介绍，受用匪浅啊，所以看到楼主的这篇文章就感觉亲切很多。

2 楼 steafler 2013-08-28  

理论来讲，LinkedHashMap的增删效率应该更高

1 楼 hailongshih 2013-08-28  

看的有些费解,有些内部实现复杂没看懂