集合框架源码分析五之LinkedHashMap,LinkedHashSet

发布时间:2017-5-23 5:18:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"集合框架源码分析五之LinkedHashMap,LinkedHashSet",主要涉及到集合框架源码分析五之LinkedHashMap,LinkedHashSet方面的内容,对于集合框架源码分析五之LinkedHashMap,LinkedHashSet感兴趣的同学可以参考一下。

   LinkedHashMap是为了解决遍历Hash表的无序问题,它内部维护了一个链表用于记录你插入元素(或你访问元素的顺序)的位置,遍历时直接遍历链表,元素的顺序即为你插入的顺序,但是Entry对象要多加两个成员变量before和after用于记录链表的前驱和后继。所以LinkedHashMap的的存储效率要低于HashMap,但是遍历效率要高于HashMap。 java.util.LinkedHashMap Java代码   import java.util.ConcurrentModificationException;  import java.util.HashMap;  import java.util.Iterator;  import java.util.Map;  import java.util.NoSuchElementException;    /**  * LinkedHashMap内部不仅存储了一个散列表,  * 也维护了一个链表,  * 根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用get方法)的链表。  * 默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素  * 移至链表尾部,不断访问可以形成按访问顺序排序的链表。  * 可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素  */  public class LinkedHashMap<K,V> extends HashMap<K,V>      implements Map<K,V>  {        private static final long serialVersionUID = 3801124242820219131L;        /**      * 此Map中维护的一个双向循环链表的头节点      */      private transient Entry<K,V> header;        /**      *       * 遍历Map的顺序的变量,      * true为按访问顺序遍历      * false为按插入顺序遍历      */      private final boolean accessOrder;        /**      *       * 构造一个空的,按插入顺序遍历的LinkedHashMap实例,      * 初始容量与加载因子由自己指定      */      public LinkedHashMap(int initialCapacity, float loadFactor) {          super(initialCapacity, loadFactor);          accessOrder = false;      }        /**      * 构造一个空的,按插入顺序遍历的LinkedHashMap实例,      * 初始容量由自己指定      */      public LinkedHashMap(int initialCapacity) {          super(initialCapacity);          accessOrder = false;      }        /**      *       * 构造一个空的,按插入顺序遍历的LinkedHashMap实例      * 初始容量与加载因子按HashMap的默认值16与0.75      */      public LinkedHashMap() {          super();          accessOrder = false;      }        /**      * 构造一个非空,按插入顺序遍历的LinkedHashMap实例      */      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每个构造方法中都会调用一次此init()方法      * 这里是初始化一个双向循环链表的头节点      */      void init() {          header = new Entry<K,V>(-1, null, null, null);          header.before = header.after = header;      }        /**      *       * 在父类HashMap进行容量扩充时会调用此方法      * 把原来Entry数组中的对象经过重新计算索引转移到此newTable中      * 这里与HashMap中的transfer方法的实现不再相同,而且比它更快。      *       * HashMap是遍历Entry数组,需要检查是否为null,如果不为空的话则就需      * 要遍历数组中的链表,而这里所有的元素都链接成了一个链表,直接遍历此      * 链表就可以遍历出LinkedHashMap中的所有元素。      */      void transfer(HashMap.Entry[] newTable) {          int newCapacity = newTable.length;          for (Entry<K,V> e = header.after; e != header; e = e.after) {              int index = indexFor(e.hash, newCapacity);   //根据新容量重新计算index              e.next = newTable[index];   //最后添加的节点放最前面              newTable[index] = e;          }      }          /**      *       *  查找Map中是否含有本值,这里重写了HashMap的containsValue方法      *  因为在LinkedHashMap中只需要遍历链表查找,这比HashMap遍历table查找更加      *  高效和快速      */      public boolean containsValue(Object value) {          // Overridden to take advantage of faster iterator          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;      }        /**      *       * 通过key值获得value,如果没有找到此key则返回null。      * 不过返回null也可能是其value为null      * 通过contain方法可判断Map中是否含有此键      *       * 重写此方法的原因是:      * 如果map中链表是按照访问顺序进行排序,      * 就需要把本次访问的元素移到链表尾部,表示      * 这是你最新访问的元素,以后可能会继续访问它      *       */      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;      }        /**      * 移除元素,清空链表      */      public void clear() {          super.clear();          header.before = header.after = header;      }        /**      * LinkedHashMap 的Entry对象.      */      private static class Entry<K,V> extends HashMap.Entry<K,V> {          // 包含其前驱和后继的信息.          Entry<K,V> before, after;            Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {              super(hash, key, value, next);          }            /**          *           * 在链表中移除此对象只需要修改前驱和后继的指针          */          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;          }            /**          *           * 当调用父类的put或putAll方法,发现要插入的键已经存在时会调用此方法,          * 当调用LinkedHashMap的get方法时会调用此方法。          * 如果LinkedHashMap是按访问顺序遍历的,就移动此Entry          * 到链表的最后位置,否则do nothing          */          void recordAccess(HashMap<K,V> m) {              LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;              if (lm.accessOrder) {                  lm.modCount++;                  remove();       //移除它                  addBefore(lm.header);   //再把她添加到链表尾部              }          }            /**          * 在移除元素时会调用此方法,即调用          * 父类的remove(key)方法时调用它          * 这里是改变链表指针,移除链表中的此元素          */          void recordRemoval(HashMap<K,V> m) {              remove();          }      }        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;          }            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<K,V> nextEntry() {              if (modCount != expectedModCount)                  throw new ConcurrentModificationException();              if (nextEntry == header)                  throw new NoSuchElementException();                    Entry<K,V> e = lastReturned = nextEntry;              nextEntry = e.after;              return e;          }      }        //依次重写next方法,返回不同的迭代器。      private class KeyIterator extends LinkedHashIterator<K> {          public K next() { return nextEntry().getKey(); }      }        private class ValueIterator extends LinkedHashIterator<V> {          public V next() { return nextEntry().value; }      }        private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {          public Map.Entry<K,V> next() { return nextEntry(); }      }        // These Overrides alter the behavior of superclass view iterator() methods      Iterator<K> newKeyIterator()   { return new KeyIterator();   }      Iterator<V> newValueIterator() { return new ValueIterator(); }      Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }        /**      *       * 重写父类addEntry方法      */      void addEntry(int hash, K key, V value, int bucketIndex) {          createEntry(hash, key, value, bucketIndex);                      /*如果子类重写了removeEldestEntry方法并返回true,                           将在map中移除链表中的第一个元素,否则检测是否需要扩充容量。           eldest元素即为链表中的第一个元素*/          Entry<K,V> eldest = header.after;          if (removeEldestEntry(eldest)) {              removeEntryForKey(eldest.key);          } else {              if (size >= threshold)                  resize(2 * table.length);   //扩充至原来的2倍          }      }        /**      *       * 重写父类的createEntry方法,此方法不需要检测是否要扩充容量,      * 与HashMap中此方法的唯一区别时,这里不仅把元素插入到散列表中,      * 而且将元素插入到了链表尾      */      void createEntry(int hash, K key, V value, int bucketIndex) {          HashMap.Entry<K,V> old = table[bucketIndex];          Entry<K,V> e = new Entry<K,V>(hash, key, value, old);          table[bucketIndex] = e;          e.addBefore(header);          size++;      }        /**      *       * 此方法会在调用put()或putAll()方法时调用,此方法告诉linkedHashMap      * 是否在添加一个元素后移除最老的元素      * 比如下面代码会让LinedHashMap的大小始终保持在100      *     private static final int MAX_ENTRIES = 100;      *      *     protected boolean removeEldestEntry(Map.Entry eldest) {      *        return size() > MAX_ENTRIES;      *     }      *  此方法默认返回false,需要子类去复写此方法      *        *  什么是eldest元素?      *  如果按插入问顺序来说,是map中最先插入的元素      *  如果按访问顺序来说,是map中最久未被访问的元素      */      protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {          return false;      }  }   关于LinkedHashSet Java代码   /**  * LinkedHashSet实际上是基于LinkedHashMap的基础上实现的,  * LinkedHashSet继承自HashSet,在HashSet中有一构造方法  * HashSet(int initialCapacity, float loadFactor, boolean dummy)   * 第三个参数dummy为true时new出了一个LinkedHashMap实例,以Set中的  * 元素为键,以一个Object的虚假的对象为值,所以HashSet中的元素不可能重复。  * 以下构造函数dummy都为true  */  public class LinkedHashSet<E>  extends HashSet<E>  implements Set<E>, Cloneable, java.io.Serializable {    private static final long serialVersionUID = -2851667679971038690L;      public LinkedHashSet(int initialCapacity, float loadFactor) {      super(initialCapacity, loadFactor, true);  }      public LinkedHashSet(int initialCapacity) {      super(initialCapacity, .75f, true);  }      public LinkedHashSet() {      super(16, .75f, true);  }      public LinkedHashSet(Collection<? extends E> c) {      super(Math.max(2*c.size(), 11), .75f, true);      addAll(c);  }  } 

上一篇:结构体之位域全面分析
下一篇:集合框架源码分析六之堆结构的实现(PriorityQueue)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

腹肌贴健身器材智能腹部训练健腹器肌