`

集合框架 Map篇(1)----HashMap、LinkedHashMap、IdentityHashMap

阅读更多
Map
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
-----------------------------------------------------

1.HashMap:

HashMap里面存入的键值对在取出的时候是随机的,是比较常用的Map.它根据key的HashCode值存储数据,根据key可以直接取出它的值(当然也有冲突的情况,不过遍历链表就可了),具有很快的访问速度。在Map中插入、删除和定位元素,HashMap是最好的选择(因为它不必为元素的排序而消耗开销)。

哈希(Hash)相关---Java中的Hash机制(HashMap、HashSet及对其源码解析)

一文中做了详细描述,在这不再重复。

补充一下HashMap的存储结构示意图:


------------------

2.LinkedHashMap

LinkedHashMap是HashMap的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap。

(1)LinkedHashMap的 Entry[]数组存储结构和HashMap的类似如上图所示:

不同的是,LinkedHashMap多了一个双向链表:


---------------------------------------------------------------------
         LinkedHashMap是HashMap的子类,LinkedHashMap是为了解决遍历Hash表的无序问题,它内部维护了一个链表用于记录你插入元素(或你访问元素的顺序)的位置,遍历时直接遍历链表,元素的顺序即为你插入的顺序,同时Entry对象要多加两个成员变量before和after用于记录链表的前驱和后继。所以LinkedHashMap的的存储效率要低于HashMap,但是遍历效率要高于HashMap。
根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用get方法)的链表。 
默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。  可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
    //-------------比父类HashMap多出的两个成员变量----------------------------
    //双向链表的头部
 private transient Entry<K, V> header;    

//true表示按照访问顺序迭代,false时表示按照插入顺序
 private final boolean accessOrder;
  //-------------5个构造函数---------------------------
    /**5个构造函数,都是通过super调用父类的实现,可以参考HashMap
 *并在前4个构造中默认该LinkedHashMap对象是按照插入顺序迭代的,
 *在最后一个构造中可以设定accessOrder*/
 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;
 }
 /**
 *遍历Map的顺序的boolean变量:
 *true为按访问顺序遍历;
 *false为按插入顺序遍历
 */
 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
 }
    //------------------init()方法是在HashMap构造函数初始化的时候调用的,
 //HashMap中是空实现,LinkedHashMap重写了init方法。代码中表达的意思也很明确了,这是双向链表的初始化状态。
 void init() {
  header = new Entry<K, V>(-1, null, null, null);
  header.before = header.after = header;
 }
     
 /*该transfer()是Hashtable中的实现:遍历整个表的各个桶位,然后对桶进行遍历得到每一个Entry,重新hash到newTable中,
 //我放在这里是为了和下面LinkedHashMap重写该法的比较,
 void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }
 */
 /**
 *transfer()方法是其父类HashMap调用resize()的时候调用的方法,它的作用是表扩容后,把旧表中的key重新hash到新的表中。
 *这里从写了父类HashMap中的该方法,是因为考虑到,LinkedHashMap拥有的双链表,在这里Override是为了提高迭代的效率。
 */
 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);
   e.next = newTable[index];
   newTable[index] = e;
  }
 }
 
    /**
 *查找Map中是否包含给定的value,还是考虑到,LinkedHashMap拥有的双链表,在这里Override是为了提高迭代的效率。
 */
 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,
 *关键是:e.recordAccess(this);这一句,它的作用可以查看recordAccess()方法,
 *如果是accessOrder==true,就是按照访问顺序存储,就是把本次访问的元素移到链表尾部
 *(这也使得Header的before指向尾部元素,可以参考上图),表示最新访问的元素。
 */
 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;
 }
    /**clear链表,设置header为初始状态*/
 public void clear() {
  super.clear();
  header.before = header.after = header;
 }
    /**
 *LinkedHashMap为了实现额外的双链表结构,实现了自己特有的Entry结构:主要是为了实现迭代多了两个向前向后的两个引用befor和after
 */
 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);
  }

  /**
   * remove
   */
  private void remove() {
   before.after = after;
   after.before = before;
  }

  /**
   * 插入到Header的前面,在父类中是调用addBefore(header)实现加入元素的,具体可以参考上面的双链表结构的图示
   */
  private void addBefore(Entry<K, V> existingEntry) {
   after = existingEntry;
   before = existingEntry.before;
   before.after = this;
   after.before = this;
  }

  /** 
         * 当调用父类的put或putAll方法,发现要插入的键已经存在时会调用此方法, 
         * 当调用LinkedHashMap的get方法时会调用此方法。
         * 如果LinkedHashMap是按访问顺序遍历的,就移动此Entry到链表的最后位置。
         */ 
  void recordAccess(HashMap<K, V> m) {
   LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>) m;
   if (lm.accessOrder) {
    lm.modCount++;
    remove();
    addBefore(lm.header);
   }
  }

  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;

  /**
   * 通过和modCount比较,用于判断并发不同步的情况,不同步时会抛出ConcurrentModificationException异常
   */
  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;
  }
 }

 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方法(该方法是在put操作时调用的),判断是否去掉header。after所对应的Entry
  * 如果是则删掉,否则判断键值对的个数是否超过了临界值,如果超过了就进行扩容
  */
 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;
  if (removeEldestEntry(eldest)) {
   removeEntryForKey(eldest.key);
  } else {
   if (size >= threshold)
    resize(2 * table.length);
  }
 }

 /**
  * 重写了父类中的方法,多了e.addBefore(header);将元素插入到了链表尾 也就是赋值给header.before
  */
 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++;
 }
   //是否在添加一个元素后移除最老的元素header.after
 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
  return false;
 }
}


-----------------------------------------

3.IdentityHashMap


使用==代替equals()对key进行比较的散列表。专为特殊问题而设计的。

可以参考API的描述:

public class IdentityHashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Serializable, Cloneable


java.util.IdentityHashMap类利用哈希表实现 Map 接口,比较键(和值)时使用引用相等性代替对象相等性。
换句话说,在 IdentityHashMap 中,当且仅当 (k1==k2) 时,才认为两个键 k1 和 k2 相等(在正常 Map 实现(如 HashMap)中,
当且仅当满足下列条件时才认为两个键 k1 和 k2 相等:(k1==null ? k2==null : e1.equals(e2)))。
此类不是 通用 Map 实现! 此类实现 Map 接口时,它有意违反 Map 的常规协定, 该协定在比较对象时强制使用 equals 方法。

此类设计仅用于其中需要引用相等性语义的罕见情况。 此类的典型用法是拓扑保留对象图形转换,如序列化或深层复制。

要执行这样的转换,程序必须维护用于跟踪所有已处理对象引用的“节点表”。 节点表一定不等于不同对象,即使它们偶然相等也如此。此类的另一种典型用法是维护代理对象。 例如,调试设施可能希望为正在调试程序中的每个对象维护代理对象。
此类提供所有的可选映射操作,并且允许 null 值和 null 键。此类对映射的顺序不提供任何保证;特别是不保证顺序随时间的推移保持不变。
此类提供基本操作(get 和 put)的稳定性能,假定系统标识了将桶间元素正确分开的哈希函数 (System.identityHashCode(Object))。
此类具有一个调整参数(影响性能但不影响语义):expected maximum size。此参数是希望映射保持的键值映射关系最大数。
在内部,此参数用于确定最初组成哈希表的桶数。未指定所期望的最大数量和桶数之间的确切关系。

默认的价值加载因子为2/3,在重新哈希后,加载因子变为1/3.当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用 reszie 方法将容量翻倍,重新进行哈希。增加桶数,重新哈希,可能相当昂贵。
因此创建具有足够大的期望最大数量的标识哈希映射更合算。另一方面,对 collection 视图进行迭代所需的时间与哈希表中的桶数成正比,
所以如果特别注重迭代性能或内存使用,则不宜将期望的最大数量设置得过高。 IdentityHashMap 源码分析:

public V put(K key, V value) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        Object item;
        while ( (item = tab[i]) != null) {
            if (item == k) {
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
            i = nextKeyIndex(i, len);
        }

        modCount++;
       tab[i] = k;//这和HashMap中的Entry的区别之处,IdentityHashMap保存key 在i,value就这i+1处,
        tab[i + 1] = value;
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        return null;
    }

private static int nextKeyIndex(int i, int len) {//IdentityHashMap特有的键值存储方式决定了i+2的步长,寻找下一个key
        return (i + 2 < len ? i + 2 : 0);

}


 public V get(Object key) {
        Object k = maskNull(key);
 Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);
        while (true) {
     Object item = tab[i];//i为键的位置是,值的位置就是i+1
            if (item == k)
                return (V) tab[i + 1];
            if (item == null)
                return null;
            i = nextKeyIndex(i, len);
        }
    }

 public boolean equals(Object o) {
        if (o == this) {//这是其equals的实现要点,比较的是关键字key对象引用,而不是像HashMap中的那样用equals比较
            return true;
        } else if (o instanceof IdentityHashMap) {
            IdentityHashMap m = (IdentityHashMap) o;
            if (m.size() != size)
                return false;

            Object[] tab = m.table;
            for (int i = 0; i < tab.length;i+=2) {//步长为2
                Object k = tab[i];
                if (k != null && !containsMapping(k, tab[i + 1]))
                    return false;
            }
            return true;
        } else if (o instanceof Map) {
            Map m = (Map)o;
            return entrySet().equals(m.entrySet());
        } else {
            return false;  // o is not a Map
        }
    }
所以虽然称为IdentityHashMap,它和java.util.HashMap的实现有很大的区别。(当然,有hash操作的map 就可以称为hashmap)

--------------------------------------------
  • 大小: 11.8 KB
  • 大小: 8.2 KB
分享到:
评论

相关推荐

    Java Collections Framework

    - **`IdentityHashMap`**:基于对象自身进行比较而非其 hashCode 和 equals 方法的 Map 实现。 - **`ConcurrentHashMap`**:线程安全的 Map 实现。 - **`WeakHashMap`**:键是弱引用的 Map 实现,适用于缓存场景...

    java集合框架 解析

    java集合框架 3.6. LinkedHashSet类 4. Map接口 4.1. Map.Entry接口 4.2. SortedMap接口 4.3. AbstractMap抽象类 4.4. HashMap类和TreeMap类 4.4.1. HashMap类 4.4.2. TreeMap类 4.5. LinkedHashMap类 4.6. ...

    java Collection&Map

    - Map接口用于存储键值对,主要实现有HashMap、TreeMap和LinkedHashMap。 - HashMap:快速查找,无序存储键值对,键值对的顺序不确定。 - TreeMap:有序存储键值对,支持自然排序或自定义比较器排序,实现了...

    jdk 的集合框架的主体结构

    `Map`接口用于存储键值对,如`HashMap`、`TreeMap`、`LinkedHashMap`、`IdentityHashMap`和`WeakHashMap`。`HashMap`是最常用的实现,提供快速查找,键和值的`equals()`和`hashCode()`方法同样需要正确实现。`...

    set,list,map区别与联系.docx

    【标题】:集合框架中的set、list和map区别与联系 在Java编程中,集合框架是数据结构的核心,其中set、list和map是最常见的三种数据结构。这些数据结构各有特点,适应不同的应用场景。 1. **List(列表)** - **...

    java知识点总结

    1. **高效实现**:集合框架中的基本类集实现了高效的动态数组、链表、树、散列表等数据结构。 2. **统一接口**:确保不同类型的集合能够以一致的方式工作,通过接口和抽象类来分离具体实现。 3. **易于扩展**:设计...

    java 运用映射的相关类(Map)

    在Java编程语言中,`Map`接口是集合框架的一部分,它提供了一种存储键值对的数据结构。Map接口不直接实现任何具体的集合类,而是由若干实现类来完成,如HashMap、TreeMap、LinkedHashMap等。这些实现类各自具有不同...

    java集合与通用集合

    `Map`的主要实现类有`HashMap`、`TreeMap`、`LinkedHashMap`、`IdentityHashMap`和`WeakHashMap`。其中,`HashMap`提供基本的键值对存储,`TreeMap`支持有序遍历,`LinkedHashMap`保持插入顺序,`IdentityHashMap`...

    java中list、set和map 的区别

    在Java编程语言中,`List`、`Set`和`Map`是集合框架中的三个核心接口,它们分别代表了不同类型的集合数据结构,各自有着独特的特性和应用场景。 #### List `List`接口是最常用的集合之一,它允许重复元素,并且每个...

    java中集合的用法与区别.docx

    Map接口的实现类有Hashtable、HashMap、LinkedHashMap、WeakHashMap和IdentityHashMap。Hashtable与HashMap类似,但它是线程安全的,不接受null键值。HashMap是非同步的,允许null键和null值。LinkedHashMap保持了...

    java 集合部分笔记

    其他实现如LinkedHashMap保持插入顺序,WeakHashMap使用弱引用,IdentityHashMap比较对象的内存地址而非equals()。 示例代码: ```java // 创建ArrayList并添加元素 List&lt;String&gt; list = new ArrayList(); list.add...

    Java 基础核心总结.md

    Java中的集合框架提供了一系列的数据结构来存储和操作对象集合。 - **Iterable接口**:提供了遍历集合的标准方法。 - **顶层接口**:如`Collection`和`Map`。 - **ArrayList**:实现了`List`接口,允许重复元素。 -...

    map,list,set,stack,queue,vector等区别和特点1

    在Java编程语言中,集合框架是处理对象组织和操作的核心工具。本文将深入探讨标题和描述中提到的一些关键集合类型,包括Map、Set、List、Queue、Stack以及它们的特点和用法。 首先,Collection接口是所有集合类型的...

    Java 基础核心总结 +经典算法大全.rar

    -、Iterator Iterable ListIterator 二、Map 和 Collection 接口Map 集合体系详解 HashMap LinkedHashMap TreeMap WeakHashMap Hashtable Collection 集合体系详解 Set 接口 AbstractSet 抽象类SortedSet 接口...

    java-all.pdf

    - **Map**:键值对集合。 - **HashMap**:基于哈希表的映射。 - **TreeMap**:基于红黑树的映射。 - **LinkedHashMap**:保持插入顺序的哈希映射。 - **Hashtable**:线程安全的映射。 - **IdentityHashMap**:...

    set,list,map区别与联系.pdf

    在Java编程语言中,集合框架提供了多种数据结构实现,包括`List`、`Set`和`Map`,它们各自有着独特的特性和用途。 1. **List**: - **有序性**:List是一个有序的数据结构,这意味着它维护了元素插入时的顺序。当...

    Java 基础核心总结,初级程序员必备,面试必考

    #### 集合框架 - **List接口**: - `ArrayList`:动态数组实现。 - `Vector`:线程安全的ArrayList。 - `LinkedList`:双向链表实现。 - **Set接口**: - `HashSet`:基于哈希表实现。 - `TreeSet`:基于红黑树...

    java中级面试题(自己汇总)

    本文总结了Java中级面试题,涵盖了集合、HashMap、HashSet、HashTable、ConcurrentHashMap、红黑树、Java 8对HashMap的优化、LinkedHashMap、TreeMap、IdentityHashMap等知识点。 集合 * List和Set都是继承自...

    java.util包源码pdf版

    - **HashSet**: 基于`HashMap`实现的集合并提供了基本的集合操作。 - **特点**:线程不安全,不允许重复元素。 - **实现方法**:`add(E e)`, `remove(Object o)`等。 - **Hashtable**: 同样基于哈希表实现,但它...

Global site tag (gtag.js) - Google Analytics