原文链接： http://www.cnblogs.com/skywang12345/p/3323085.html

一、Map架构

(01) Map 是映射接口，Map中存储的内容是键值对(key-value)。

(02) AbstractMap 是继承于Map的抽象类，它实现了Map中的大部分API。其它Map的实现类可以通过继承AbstractMap来减少重复编码。(03) SortedMap 是继承于Map的接口。SortedMap中的内容是排序的键值对，排序的方法是通过比较器(Comparator)。   NavigableMap 是继承于SortedMap的接口。相比于SortedMap，NavigableMap有一系列的导航方法；如"获取大于/等于某对象的键值对"、“获取小于/等于某对象的键值对”等等。 (05) TreeMap 继承于AbstractMap，实现了NavigableMap接口；TreeMap 是“有序的键值对”！(06) HashMap 继承于AbstractMap，没实现NavigableMap接口；HashMap是"键值对，但不保证次序;(07) Hashtable 不是继承于AbstractMap，它继承于Dictionary(Dictionary也是键值对的接口)，而且也实现Map接口；因此，Hashtable的内容也是“键值对，也不保证次序”。但和HashMap相比，Hashtable是线程安全的，而且它支持通过Enumeration去遍历。(08) WeakHashMap 继承于AbstractMap。它和HashMap的键类型不同，WeakHashMap的键是“弱键”。

public interface Map
    
      {...}
    

Map 是一个(key-value)接口。Map映射中不能包含重复的键；每个键最多只能映射到一个值。

void                 clear()boolean              containsKey(Object key)boolean              containsValue(Object value)Set
    
     
      >     entrySet()boolean              equals(Object object)V                    get(Object key)int                  hashCode()boolean              isEmpty()Set
      
                      keySet()V                    put(K key, V value)void                 putAll(Map
        map)V                    remove(Object key)int                  size()Collection
       
                values()
       
      
     
    

(01) Map 接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。  entrySet()用于返回键-值集的Set集合； keySet()用于返回键集的Set集合； values()用户返回值集的Collection集合；   因为Map中不能包含重复的键；每个键最多只能映射到一个值。所以，键-值集、键集都是Set，值集时Collection。

(02) Map提供了“键-值对”、“根据键获取值”、“删除键”、“获取容量大小”等方法。

interface Entry
    
      {...}
    

Map.Entry是Map中内部的一个接口，Map.Entry是键值对，Map通过 entrySet() 获取Map.Entry的键值对集合，从而通过该集合实现对键值对的操作。

// Map.Entry的APIboolean     equals(Object object)K             getKey()V             getValue()int         hashCode()V             setValue(V object)

SortedMap是一个继承于Map接口的接口。它是一个有序的SortedMap键值映射。

SortedMap的排序方式有两种：自然排序 或者 用户指定比较器。 插入有序 SortedMap 的所有元素都必须实现 Comparable 接口（或者被指定的比较器所接受）。

二、HashMap

public class HashMap
    
      extends AbstractMap
     
          implements Map
      
       , Cloneable, Serializable {...}
      
     
    

   HashMap 是一个散列表，它存储的内容是(key-value)映射。

   HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。    HashMap 线程不安全的。 它的 key、value 都可为 null，它的映射是无序的。    HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量。 "加载因子 "是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。     HashMap将“key为null”的元素都放在table的位置0处，即table[0]中；“key不为null”的放在table的其余位置(计算hashcode)！

  (01) HashMap继承于AbstractMap类，实现了Map接口。

 (02) HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。　　table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的" key-value键值对 "都是存储在Entry数组中的。  size是HashMap的大小，它是HashMap保存的键值对的数量。 　　threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。　　loadFactor就是加载因子。 　　modCount是用来实现fail-fast机制的。

三、HashTable

   和HashMap一样，Hashtable 也是一个散列表，它存储的内容是(key-value)映射。

   Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。   Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射无序的。    Hashtable 的实例有两个参数影响其性能：初始容量 和 加载因子。

   # HashMap 和 HashTable 的区别：

   1. HashMap是非synchronized的，Hashtable是线程安全的   2. HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行。   3. HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。 所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException， 但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。 这条同样也是Enumeration和Iterator的区别。 

   Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator，然后其它的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。 结构上的更改指的是删除或者插入一个元素，这样会影响到map的结构。

   HashMap可以通过下面的语句进行同步： Map m = Collections.synchronizeMap(hashMap);

   Hashtable和HashMap有几个主要的不同：线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable， 而如果你使用Java 5或以上的话，请使用ConcurrentHashMap吧。  

四、TreeMap

   TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。

   TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。    TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。    TreeMap 实现了Cloneable、java.io.Serializable接口，意味着它支持序列化。    TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。    TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。     另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

   (02) TreeMap的本质是R-B Tree(红黑树)，它包含几个重要的成员变量： root, size, comparator。

root 是红黑数的根节点。它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。    红黑数排序时，根据Entry中的key进行排序；Entry中的key比较大小是根据比较器comparator来进行判断的。 size是红黑数中节点的个数。

 五、WeakHashMap

   WeakHashMap 继承于AbstractMap，实现了Map接口。WeakHashMap 是一个散列表，存储(key-value)映射，而且键和值都可以是null。

   不过WeakHashMap的键是“弱键”。在 WeakHashMap 中，当某个键不再正常使用时，会被从WeakHashMap中被自动移除。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。某个键被终止时，它对应的键值对也就从映射中有效地移除了。这个“弱键”的原理呢？大致上就是，通过WeakReference和ReferenceQueue实现的。 WeakHashMap的key是“弱键”，即是WeakReference类型的；ReferenceQueue是一个队列，它会保存被GC回收的“弱键”。实现步骤是：    (01) 新建WeakHashMap，将“键值对”添加到WeakHashMap中。 实际上，WeakHashMap是通过数组table保存Entry(键值对)；每一个Entry实际上是一个单向链表，即Entry是键值对链表。    (02) 当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。    (03) 当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对； 同步它们，就是删除table中被GC回收的键值对。 这就是“弱键”如何被自动从WeakHashMap中删除的步骤了。

   和HashMap一样，WeakHashMap是不同步的。可以使用 Collections.synchronizedMap 方法来构造同步的 WeakHashMap  

http://www.cnblogs.com/skywang12345/p/3311126.html

##  Map概括   (01) Map 是“键值对”映射的抽象接口。    (02) AbstractMap 实现了Map中的绝大部分函数接口。它减少了“Map的实现类”的重复编码。    (03) SortedMap 有序的“键值对”映射接口。    (04) NavigableMap 是继承于SortedMap的，支持导航函数的接口。    (05) HashMap, Hashtable, TreeMap, WeakHashMap这4个类是“键值对”映射的实现类。它们各有区别！

   HashMap 是基于“拉链法”实现的散列表。一般用于单线程程序中。

   Hashtable 也是基于“拉链法”实现的散列表。它一般用于多线程程序中。  WeakHashMap 也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值对也会被从WeakHashMap中删除；而HashMap中的键是强键。    TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。 

HashMap和Hashtable异同

   # HashMap和Hashtable的相同点    1. HashMap和Hashtable都是存储“键值对(key-value)”的散列表，而且都是采用拉链法实现的。 存储的思想都是：通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单向链表，Entry链表中的每一个节点就保存 了key-value键值对数据。    添加key-value键值对：首先，根据key值计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。 然后，根据数组索引找到Entry(即，单向链表)，再遍历单向链表，将key和链表中的每一个节点的key进行对比。 若key已经存在Entry链表中，则用该value值取代旧的value值； 若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。    删除key-value键值对：首先，还是根据key计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。 然后，根据索引找出Entry(即，单向链表)。若节点key-value存在与链表Entry中，则删除链表中的节点即可。    # HashMap和Hashtable的不同点   1. Hashtable的key或value，都不能为null！否则，会抛出异常NullPointerException。       HashMap的key、value都可以为null。 当HashMap的key为null时，HashMap会将其固定的插入table[0]位置 (即HashMap散列表的第一个位置)；而且table[0]处只会容纳一个key为null的值，当有多个key为null的值插入的时候， table[0]会保留最后插入的value。   2. Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。       而HashMap的函数则是非同步的，它不是线程安全的。   3. HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。       Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。

   4. HashMap只支持Iterator(迭代器)遍历。

      而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。   5. HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。       Hashtabl是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。   6. HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。          负载因子都是 0.75       Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。    负载因子都是 0.75   7. HashMap添加元素时，是使用自定义的哈希算法。       Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。   8. 。。。。。   

Set架构 

   (01) Set 是继承于Collection的接口。它是一个不允许有重复元素的集合。

   (02) AbstractSet 是一个抽象类，它继承于AbstractCollection，AbstractCollection实现了Set中的绝大部分函数，为Set的实现类提供了便利。    (03) HastSet 和 TreeSet 是Set的两个实现类。            HashSet依赖于HashMap，它实际上是通过HashMap实现的。HashSet中的元素是无序的。            TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。TreeSet中的元素是有序的。

   HashSet   

    http://www.cnblogs.com/skywang12345/p/3311252.html      HashSet 是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。    HashSet是非同步的。如果多个线程同时访问一个哈希 set，那么它必须 保持外部同步。                 Set s = Collections.synchronizedSet(new HashSet(...));    HashSet通过iterator()返回的迭代器是fail-fast的。

   TreeSet

   TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。    TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。    TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。

   TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。 

     TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。

     另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

Iterator 和 Enumeration 比较：

public interface Enumeration
    
      {    boolean hasMoreElements();    E nextElement();}public interface Iterator
     
       {    boolean hasNext();    E next();    void remove();}
     
    

(01) 函数接口不同

      Enumeration 有2个函数接口。我们只能读取集合的数据，不能对数据进行修改。       Iterator 有3个函数接口。Iterator除了能读取集合的数据之外，也能数据进行删除操作。    (02) Iterator支持fail-fast机制，而Enumeration不支持。       Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类，这些类都是JDK 1.0中加入的，Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步，而在Vector、Hashtable实现Enumeration时，添加了同步。       而Iterator 是JDK 1.2才添加的接口，它也是为了HashMap、ArrayList等集合提供遍历接口。 Iterator是支持fail-fast机制的：当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。