集合类---Map

Map常用的子类：

一、HashMap详解

1.特点

1）线程不安全。如果想要得到线程安全的HashMap，可以使用Collections的静态方法：Map map = Collections.synchronizedMap(new HashMap());

2）允许null键和null值。只能有一个键为null，可以有多个值为null。如果get()返回null，可以表示没有该键，也可以表示该键所对应的值为null。所以应该用containsKey()或containsValue()来判断是否存在。

3）时间复杂度是o(1)。

4）初始容量和装填因子影响其性能。

5）无序。即不能按照输入的顺序输出，而LinkedHashMap可以（双向链表对其进行保证）。

6）没有contains()方法

2.数据结构

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

HashMap的底层是哈希数组，数组元素为Entry。HashMap通过key的hashCode来计算hash值，当hashCode相同时，通过“拉链法”解决冲突。当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。原本Map.Entry接口的实现类Entry改名为了Node。转化为红黑树时改用另一种实现TreeNode。

Node类：

 1     static class Node<K,V> implements Map.Entry<K,V> {
 2         final int hash;//hash值
 3         final K key;
 4         V value;
 5         Node<K,V> next;//指向下一个节点
 6 
 7         Node(int hash, K key, V value, Node<K,V> next) {
 8             this.hash = hash;
 9             this.key = key;
10             this.value = value;
11             this.next = next;
12         }
13 
14         public final K getKey()        { return key; }
15         public final V getValue()      { return value; }
16         public final String toString() { return key + "=" + value; }
17         //重写hashCode
18         public final int hashCode() {
19             return Objects.hashCode(key) ^ Objects.hashCode(value);
20         }
21 
22         public final V setValue(V newValue) {
23             V oldValue = value;
24             value = newValue;
25             return oldValue;
26         }
27         //比较key和value是否equals相等
28         public final boolean equals(Object o) {
29             if (o == this)
30                 return true;
31             if (o instanceof Map.Entry) {
32                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
33                 if (Objects.equals(key, e.getKey()) &&
34                     Objects.equals(value, e.getValue()))
35                     return true;
36             }
37             return false;
38         }
39     }

View Code

3.源码解读

（1）主要属性

 1 //hash表的桶，用一个数组模拟，数组中每个元素都是一个指针，可以是单链表的头指针，也可以是红黑树的根节点的指针  
 2 transient Node<K,V>[] table;
 3 
 4 //用来实现遍历map的set,依次遍历所有的node或者treeNode 
 5 transient Set<Map.Entry<K,V>> entrySet;  
 6 
 7 //该map中所有key-value对的个数
 8 transient int size; 
 9 
10 //修改次数，用来判断该map是否同时被多个线程操作，多线程环境下会抛出异常ConcurrentModificationException
11 transient int modCount;  
12 
13 //= table.size()* loadFactor，当table中实际占用量（不是table中占用的bin的个数，而是所有bin中的Node的总数）超过threshold时，就会进行resize()操作  
14 //eg:table.size()=16,loadFactor=0.75,则当所有Bin中的node的个数超过12时会进行resize.  
15 //table的容量，如果没有设置，则默认等于DEFAULT_INITIAL_CAPACITY=16，且必须为2的整数次幂。  
16 int threshold;
17 
18 //加载因子<=1，当table中实际占用的容量超过table.size()* loadFactor时，会进行table的扩容。默认加载因子为DEFAULT_LOAD_FACTOR=0.75  
19 final float loadFactor;
20   
21 //table默认初始容量 16，必须是2的整数次幂  
22 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
23 
24 //table的最大容量  
25 static final int MAXIMUM_CAPACITY = 1 << 30;
26 
27 //默认加载因子，当table数组的容量超过table.length* loadFactor时，会调用resize()进行扩容。  
28 static final float DEFAULT_LOAD_FACTOR = 0.75f;
29   
30 //当table[i]中的node个数超过8个，会将单链表table[i]转化成红黑树  
31 static final int TREEIFY_THRESHOLD = 8;
32 
33 //当table[i]中红黑树的节点数少于6时，会退化成单链表  
34 static final int UNTREEIFY_THRESHOLD = 6;
35 
36 //当table的length大于64时，才会进行将某条node个数超过8的单链表转化成红黑树操作  
37 static final int MIN_TREEIFY_CAPACITY = 64;

View Code

（2）构造方法

 1     /**
 2      * 根据初始化容量和加载因子构建一个空的HashMap.
 3      */
 4     public HashMap(int initialCapacity, float loadFactor) {
 5         if (initialCapacity < 0)
 6             throw new IllegalArgumentException("Illegal initial capacity: " +
 7                                                initialCapacity);
 8 //设置的初始容量大于最大允许容量，则强制将initialCapacity = MAXIMUM_CAPACITY  
 9         if (initialCapacity > MAXIMUM_CAPACITY)
10             initialCapacity = MAXIMUM_CAPACITY;
11         if (loadFactor <= 0 || Float.isNaN(loadFactor))
12             throw new IllegalArgumentException("Illegal load factor: " +
13                                                loadFactor);
14         this.loadFactor = loadFactor;
15 //调用tableSizeFor将threshold设置成大于initialCapacity的最小的2的整数次幂  
16         this.threshold = tableSizeFor(initialCapacity);
17     }
18 
19     /**
20      * 使用初始化容量和默认加载因子(0.75).
21      */
22     public HashMap(int initialCapacity) {
23         this(initialCapacity, DEFAULT_LOAD_FACTOR);
24     }
25 
26     /**
27      * 使用默认初始化大小(16)和默认加载因子(0.75).
28      */
29     public HashMap() {
30         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
31     }
32 
33     /**
34      * 用已有的Map构造一个新的HashMap.
35      */
36     public HashMap(Map<? extends K, ? extends V> m) {
37         this.loadFactor = DEFAULT_LOAD_FACTOR;
38         putMapEntries(m, false);
39     }

View Code

（3）重要方法

1）put方法

如果是首个插入map的节点，map进行初始化，在resize中进行
如果是put一个新节点，则插入结束后检查对应的bin是否需要转化成红黑树
插入或更新结束后，检查该table是否需要resize扩容

 1 public V put(K key, V value) {  
 2       return putVal(hash(key), key, value, false, true);  
 3   }  
 4 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
 5                  boolean evict) {  
 6       Node<K,V>[] tab; Node<K,V> p; int n, i;  
 7 //如果table为null或者table的长度为0，则调用resize()对table进行初始化  
 8       if ((tab = table) == null || (n = tab.length) == 0)  
 9           n = (tab = resize()).length;  
10 //如果hash号桶中没有node，则将该节点作为首节点放入该桶中  
11       if ((p = tab[i = (n - 1) & hash]) == null)  
12           tab[i] = newNode(hash, key, value, null);  
13 //如果hash号桶中有node，则遍历后添加
14       else {  
15           Node<K,V> e; K k;  
16 //如果key和value都相等，则直接覆盖
17           if (p.hash == hash &&  
18               ((k = p.key) == key || (key != null && key.equals(k))))  
19               e = p;  
20 //在红黑树中查找，e指向查找到的treeNode，向红黑树中添加  
21           else if (p instanceof TreeNode)  
22               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
23 //在单链表中查找
24           else {  
25               for (int binCount = 0; ; ++binCount) {  
26 //当遍历该桶没有找到相同的key时，就新new一个Node，加入到链表末尾
27                   if ((e = p.next) == null) {  
28                       p.next = newNode(hash, key, value, null);  
29 //检查该链表中Node的个数是否>=8，是则要将单链表转化成红黑树  
30                       if (binCount >= TREEIFY_THRESHOLD - 1) 
31                           treeifyBin(tab, hash);  
32                       break;  
33                   }  
34 //在单链表如果key和value都相等，则直接覆盖
35                   if (e.hash == hash &&  
36                       ((k = e.key) == key || (key != null && key.equals(k))))  
37                       break;  
38                   p = e;  
39               }  
40           }  
41           if (e != null) { // existing mapping for key  
42               V oldValue = e.value;  
43         //更新Node的value  
44               if (!onlyIfAbsent || oldValue == null)  
45                   e.value = value;  
46         //回调接口，让LinkedHashMap执行对应的动作。在hashMap中没有动作：void  
47               afterNodeAccess(e);  
48               return oldValue;  
49           }  
50       }  
51       ++modCount;  
52 //检查table的size有没有超过临界值，超过要进行resize扩容  
53       if (++size > threshold)  
54           resize();  
55 //回调接口，让LinkedHashMap执行对应的动作。在hashMap中没有动作：void  
56       afterNodeInsertion(evict);  
57       return null;  
58   }

View Code

2）get方法

 1     public V get(Object key) {
 2         Node<K,V> e;
 3         return (e = getNode(hash(key), key)) == null ? null : e.value;
 4     }
 5 
 6     /**
 7      * Implements Map.get and related methods
 8      *
 9      * @param hash hash for key
10      * @param key the key
11      * @return the node, or null if none
12      */
13     final Node<K,V> getNode(int hash, Object key) {
14         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
15 //如果table不为空，table.length>0,且hash对应的桶中有值  
16         if ((tab = table) != null && (n = tab.length) > 0 &&
17             (first = tab[(n - 1) & hash]) != null) {
18 //如果第一个节点就是要查找的节点，则返回第一个节点
19             if (first.hash == hash && // always check first node
20                 ((k = first.key) == key || (key != null && key.equals(k))))
21                 return first;
22 //否则依次遍历后来的节点
23             if ((e = first.next) != null) {
24 //查找红黑树
25                 if (first instanceof TreeNode) 
26                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
27 //查找单链表
28                 do {
29                     if (e.hash == hash &&
30                         ((k = e.key) == key || (key != null && key.equals(k))))
31                         return e;
32                 } while ((e = e.next) != null);
33             }
34         }
35         return null;
36     }
37 
38     // 遍历红黑树搜索节点
39     /**
40      * Calls find for root node.
41      */
42     final TreeNode<K,V> getTreeNode(int h, Object k) {
43         return ((parent != null) ? root() : this).find(h, k, null);
44     }
45 
46     /**
47      * Returns root of tree containing this node.
48      */
49     final TreeNode<K,V> root() {
50         for (TreeNode<K,V> r = this, p;;) {
51             if ((p = r.parent) == null)
52                 return r;
53             r = p;
54         }
55     }
56 
57     /**
58      * Finds the node starting at root p with the given hash and key.
59      * The kc argument caches comparableClassFor(key) upon first use
60      * comparing keys.
61      */
62     final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
63         TreeNode<K,V> p = this;
64         do {
65             int ph, dir; K pk;
66             TreeNode<K,V> pl = p.left, pr = p.right, q;
67             if ((ph = p.hash) > h) // 当前节点hash大
68                 p = pl; // 查左子树
69             else if (ph < h) // 当前节点hash小
70                 p = pr; // 查右子树
71             else if ((pk = p.key) == k || (k != null && k.equals(pk)))
72                 return p; // hash、key都相等，即找到，返回当前节点
73             else if (pl == null) // hash相等，key不等，左子树为null，查右子树
74                 p = pr;
75             else if (pr == null)
76                 p = pl;
77             else if ((kc != null ||
78                       (kc = comparableClassFor(k)) != null) &&
79                      (dir = compareComparables(kc, k, pk)) != 0)
80                 p = (dir < 0) ? pl : pr;
81             else if ((q = pr.find(h, k, kc)) != null)
82                 return q;
83             else
84                 p = pl;
85         } while (p != null);
86         return null;
87     }

View Code

3）remove方法

 1 public V remove(Object key) {  
 2         Node<K,V> e;  
 3         return (e = removeNode(hash(key), key, null, false, true)) == null ?  
 4             null : e.value;  
 5     }  
 6 //removeNode：删除指定的key所对应的Node,matchValue为true表示只有key和value都对应才删除；movable表示在删除时不移动其他node  
 7   
 8 final Node<K,V> removeNode(int hash, Object key, Object value,  
 9                                boolean matchValue, boolean movable) {  
10         Node<K,V>[] tab; Node<K,V> p; int n, index;  
11         //只有在table不为空，table的length大于0，hash&(n-1)号桶中有值时才进行查找删除  
12         if ((tab = table) != null && (n = tab.length) > 0 &&  
13             (p = tab[index = (n - 1) & hash]) != null) {  
14             Node<K,V> node = null, e; K k; V v;  
15             //如果头结点是查找的节点则令node指向它  
16             if (p.hash == hash &&  
17                 ((k = p.key) == key || (key != null && key.equals(k))))  
18                 node = p;  
19             else if ((e = p.next) != null) {  
20                 //如果这个桶中存储的是红黑树，则通过getTreeNode找到对应的node  
21                 if (p instanceof TreeNode)  
22                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);  
23                 else {  
24                     //如果是单链表，则依次查找node，知道找到，令node指向它  
25                     do {  
26                         if (e.hash == hash &&  
27                             ((k = e.key) == key ||  
28                              (key != null && key.equals(k)))) {  
29                             node = e;  
30                             break;  
31                         }  
32                         p = e;  
33                     } while ((e = e.next) != null);  
34                 }  
35             }  
36             //当Node==null表示没有找到该节点  
37             //只有当不要求匹配value或者要求匹配并且node的value也相等时，才进行删除  
38             if (node != null && (!matchValue || (v = node.value) == value ||  
39                                  (value != null && value.equals(v)))) {  
40                 //在红黑树中删除节点，把movable传递进去  
41                 if (node instanceof TreeNode)  
42                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);  
43                 //头结点删除  
44                 else if (node == p)  
45                     tab[index] = node.next;  
46                 //p指向node的前一个节点  
47                 else  
48                     p.next = node.next;  
49                 ++modCount;  
50                 --size;  
51                 //回调接口，让LinkedHashMap执行对应的动作。在hashMap中没有动作：void afterNodeRemoval(Node<K,V> p) { }  
52                 afterNodeRemoval(node);  
53                 return node;  
54             }  
55         }  
56         return null;  
57     }

View Code

4）resize方法

若table没有初始化，则采用默认的cap和加载因子（或者使用new map对象时传递进来的thr和f）进行初始化，为table申请空间
若table已经初始化，则将cap*2，thr*2。同时若cap已经超过了MAX_CAP,则直接将thr设置与cap相等。
将oldTable中的node都映射到newTable中。OldTable[i]中的node要么映射到newTable的i中，要么是i+oldcap中，由node.hash的第oldCap二进制中1所在位置j的那个位置bit值决定。

 1 final Node<K,V>[] resize() {  
 2         Node<K,V>[] oldTab = table;  
 3         //cap是数组的容量，thr是数组进行扩容的临界值  
 4         int oldCap = (oldTab == null) ? 0 : oldTab.length;  
 5         int oldThr = threshold;  
 6         int newCap, newThr = 0;  
 7         //不是数组初始化  
 8         if (oldCap > 0) {  
 9             //当原table的size已经达到MAXIMUM_CAPACITY时，不对cap进行调整，只是将扩容临界值thr调整为与cap相同，让table空间得到100%的利用  
10             if (oldCap >= MAXIMUM_CAPACITY) {  
11                 threshold = Integer.MAX_VALUE;  
12                 return oldTab;  
13             }  
14             //否则就将cap和thr进行*2扩容  
15             //即使newCap<<1，它的值也始终小于Integer.MAX_VALUE,因为newCap是一个int型的整数  
16             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
17                      oldCap >= DEFAULT_INITIAL_CAPACITY)  
18                 newThr = oldThr << 1; // double threshold  
19         }  
20         //通过初始化传递了thr但是还没有进行table的初始化操作，这时将cap设置为oldCap的值  
21         else if (oldThr > 0) // initial capacity was placed in threshold  
22             newCap = oldThr;  
23 //初始化没有传递任何参数，cap和thr都采用默认值  
24         else {               // zero initial threshold signifies using defaults  
25             newCap = DEFAULT_INITIAL_CAPACITY;  
26             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
27         }  
28         //如果上面没有设置newThr的值，这里统一进行处理.  
29         //主要有两个地方，第一个else if ((newCap = oldCap << 1)，第二个else if (oldThr > 0)；    
30       if (newThr == 0) {  
31             float ft = (float)newCap * loadFactor;  
32             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
33                       (int)ft : Integer.MAX_VALUE);  
34         }  
35         //重新设置扩容后的临界值  
36         threshold = newThr;  
37         //利用上面计算的newCap重新为数组申请扩容后的空间  
38         @SuppressWarnings({"rawtypes","unchecked"})  
39             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
40         table = newTab;  
41         //将原数组中内容转移到新数组中  
42         if (oldTab != null) {  
43             //原table中每个桶中的node逐个进行重新hash处理  
44             for (int j = 0; j < oldCap; ++j) {  
45                 Node<K,V> e;  
46                 if ((e = oldTab[j]) != null) {  
47                     //将原table中每个链表的头指针置null  
48                     oldTab[j] = null;  
49                     //如果oldTable[i]这条链表只有头指针，则将该node重新hash映射到新链表的某个位置上  
50                     if (e.next == null)  
51                         newTab[e.hash & (newCap - 1)] = e;  
52                     //如果该条链表是以红黑树的形式存储的，则调用红黑树的相关操作  
53                     else if (e instanceof TreeNode)  
54                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
55                     //对oldTable[i]链表中每个元素逐一处理  
56                     else { // preserve order  
57                         //lo表示原链表中的node在新链表中的映射仍在同一位置table[i]  
58                         Node<K,V> loHead = null, loTail = null;  
59                         //hi 表示原链表中的node在新链表中的映射在table[i+oldCap]。只有这两种位置  
60                         Node<K,V> hiHead = null, hiTail = null;  
61                         Node<K,V> next;  
62                         do {  
63                             next = e.next;  
64                             //i=e.hash&(oldCap-1),那么e.hash&oldCap的值为e.hash在oldCap二进制形式中那个唯一(cap的值都为2的整数次幂，所以二进制形式中只有一个1)的1所在位置的值，要么为0，要么为1.。  
65                             //因此，oldTable中的table[i]中的node，在新链表中的位置要么为i，要么为i+oldCap  
66                             //之所以直接采用(e.hash & oldCap)是为了计算简便，避免每次都用e.hash&(newCap-1)  
67 if ((e.hash & oldCap) == 0) {  
68                                 if (loTail == null)  
69                                     loHead = e;  
70                                 else  
71                                     loTail.next = e;  
72                                 loTail = e;  
73                             }  
74                             else {  
75                                 if (hiTail == null)  
76                                     hiHead = e;  
77                                 else  
78                                     hiTail.next = e;  
79                                 hiTail = e;  
80                             }  
81                         } while ((e = next) != null);  
82                         //在新table中映射位置为j的,相对顺序与oldTable中的相同  
83                         if (loTail != null) {  
84                             loTail.next = null;  
85                             newTab[j] = loHead;  
86                         }  
87                         //在新链表中映射位置为j+oldCap的  
88                         if (hiTail != null) {  
89                             hiTail.next = null;  
90                             newTab[j + oldCap] = hiHead;  
91                         }  
92                     }  
93                 }  
94             }  
95         }  
96         return newTab;  
97     }

View Code

5）treeifyBin和untreeify方法

treeifyBin将某个hash桶的单链表转化成红黑树；untreeify将红黑树转化成单链表，在删除红黑树节点时会用到
基本步骤：
a、检查table.length是否>=64，如果不成立，则进行resize扩容，结束。
b、通过hash&(n-1)定位到table相应的bin中，检查bin中是否有Node，将单链表中的Node类型依次转化成treenode类型，并链接在一个双链表中
c、调用treeNode.treeify方法将该桶中的treeNode双链表转化成红黑树。

 1    final void treeifyBin(Node<K,V>[] tab, int hash) {  
 2        int n, index; Node<K,V> e;  
 3     //若table的len没有达到最小树化值，则进行扩容处理  
 4        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  
 5            resize();  
 6     //若该桶中有node，则将该桶中的单链表转化成红黑树  
 7        else if ((e = tab[index = (n - 1) & hash]) != null) {  
 8            TreeNode<K,V> hd = null, tl = null;  
 9            do {  
10             //将每个node节点的值重新生成一个TreeNode节点  
11                TreeNode<K,V> p = replacementTreeNode(e, null);  
12             //hd指向红黑树的根节点  
13                if (tl == null)  
14                    hd = p;  
15                else {  
16                 //prev指向前一个节点，next指向后一个节点  
17                    p.prev = tl;  
18                    tl.next = p;  
19                }  
20                tl = p;  
21            } while ((e = e.next) != null);  
22         //上面的while循环将单链表转化成了双链表，节点类型由node编程了treeNode,hd指向头结点  
23            if ((tab[index] = hd) != null)  
24             //将该双链表构建成红黑树  
25                hd.treeify(tab);  
26        }  
27    }  
28 //红黑树退化成单链表  
29 //a、通过treeNode.next遍历红黑树，并将节点依次replacementNode成Node类型。  
30 //b、将转化后的节点依次链接成一条单链表，返回头结点的指针  
31  final Node<K,V> untreeify(HashMap<K,V> map) {  
32            Node<K,V> hd = null, tl = null;  
33            for (Node<K,V> q = this; q != null; q = q.next) {  
34             //将红黑树中的节点treeNode依次转化成node  
35                Node<K,V> p = map.replacementNode(q, null);  
36                if (tl == null)  
37                    hd = p;  
38                else  
39                    tl.next = p;  
40                tl = p;  
41            }  
42         //返回单链表的头结点  
43            return hd;  
44        }

View Code

常用遍历方法：

https://blog.csdn.net/shenshen123jun/article/details/9074523

Hashmap 不是线程安全的，所以如果在使用迭代器的过程中有其他线程修改了 map，则会抛出 ConcurrentModificationException，这就是所谓的 fast-fail 策略，是通过 modcount 实现，对 Hashmap 内容的修改都将增加这个值，那么在迭代器初始化时会将这个值赋给迭代器的 exceptedmodcount。在迭代过程中，判断 modcount 和 exceptedmodcount 是否相等，若不相等，则说明其他线程修改了 map。Modcount 是 volatile 的。

二、HashTable详解

1.特点

1）线程安全。put,get,remove等方法上都有synchronized关键字保持同步。

2）不允许null键和null值，如果存入会报空指针异常。

2.数据结构

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

3.源码解读

（1）主要属性

 1 private transient Entry<?,?>[] table  
 2 private transient int count;//table中所有entry的个数  
 3 private int threshold;//扩容的临界值count >= threshold,threshold=loadFactor*capacity,  
 4 private float loadFactor;//加载因子threshold=loadFactor*capacity,加载因子越大，table的利用率越高  
 5 private transient int modCount = 0;//单线程，多线程操作可能会引起Hashtable fail-fast，抛出ConcurrentModificationException异常  
 6   
 7 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//table的最大size  
 8   
 9 //三种遍历方式  
10 private transient volatile Set<K> keySet;  
11 private transient volatile Set<Map.Entry<K,V>> entrySet;  
12 private transient volatile Collection<V> values;

View Code

（2）构造方法

 1 //传递一个table的初始容量和加载因子，table的初始化在构造函数中进行(与HashMap不同，hashmap在put第一个node中进行)。  
 2  public Hashtable(int initialCapacity, float loadFactor) {  
 3         if (initialCapacity < 0)  
 4             throw new IllegalArgumentException("Illegal Capacity: "+  
 5                                                initialCapacity);  
 6         if (loadFactor <= 0 || Float.isNaN(loadFactor))  
 7             throw new IllegalArgumentException("Illegal Load: "+loadFactor);  
 8   
 9         if (initialCapacity==0)  
10             initialCapacity = 1;  
11         //设置loadFactor，threshold的值，为table申请空间  
12         this.loadFactor = loadFactor;  
13         //与HashMap不同，table的size可以随意指定，不用为2的整数次幂，甚至都不用超过11（默认的初始容量）  
14         table = new Entry<?,?>[initialCapacity];  
15         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
16     }  
17 //默认的loadFactor=0.75  
18 public Hashtable(int initialCapacity) {  
19         this(initialCapacity, 0.75f);  
20     }  
21 //默认的capacity=11  
22 public Hashtable() {  
23         this(11, 0.75f);  
24     }  
25 //2*t.size()保证不用插进去就需要扩容  
26 public Hashtable(Map<? extends K, ? extends V> t) {  
27         this(Math.max(2*t.size(), 11), 0.75f);  
28         putAll(t);  
29     }

View Code

（3）不同方法

1)rehash:扩容，不是同步的
思路：
将capatity*2,根据loadfactor重新设置threshold
依次逆序遍历oldMap中所有Bin中的节点，重新映射到newMap的bin中。这里是从链表头插入，所以顺序与OldMap中的相反。hashMap是插入链表尾部，顺序相同。

与hashMap的resize不同点：
（1）hashMap的resize中可能对table进行初始化，这里初始化在构造函数中进行
（2）扩容方式：hashmap中 newCap=oldCap*2,这样保证新容量依然是2的整数次幂；hashTable中，newCap=oldCap*2+1
（3）映射方式：hashMap中oldMap中同一个bin中node只可能映射到i和i+oldCap两个桶中；hashTable中由于不要求cap是2的整数次幂，所以oldCap中同一个bin中可能映射到newMap的各个Bin中
（4）转移数据方式：hashMap中oldMap和newMap中node在链表中相对顺序不变，是在链表尾部插入的；hashTable中顺序逆向了，在链表首部插入的。
（5）效率：hashMap效率更高，采用&操作映射；HashTable效率低，采用%
（6）桶的结构：hashMap中当节点数大于8时，单链表会转化成红黑树；HashTable始终以单链表存储

 1 protected void rehash() {  
 2         int oldCapacity = table.length;  
 3         Entry<?,?>[] oldMap = table;  
 4   
 5         // 扩容方法：新容量=就容量*2+1  
 6         int newCapacity = (oldCapacity << 1) + 1;  
 7         if (newCapacity - MAX_ARRAY_SIZE > 0) {  
 8             if (oldCapacity == MAX_ARRAY_SIZE)  
 9                 // Keep running with MAX_ARRAY_SIZE buckets  
10                 return;  
11             newCapacity = MAX_ARRAY_SIZE;  
12         }  
13         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];  
14   
15         modCount++;  
16         //确定新的临界值threshold  
17         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
18         table = newMap;  
19         //逆序遍历oldMap的桶中的所有节点，并依次映射到newMap中的桶  
20         for (int i = oldCapacity ; i-- > 0 ;) {  
21             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {  
22                 Entry<K,V> e = old;  
23                 old = old.next;  
24                 //oldMap映射到newMap的bin的方法：直接取余  
25                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;  
26                 //每次都从newMap的链表的头部插入  
27                 e.next = (Entry<K,V>)newMap[index];  
28                 newMap[index] = e;  
29             }  
30         }  
31     }

View Code

三、TreeMap详解

1.特点

1）有序

2）非线程安全

3）时间复杂度是o(lgn)

2.数据结构

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

四、LinkedHashMap详解

1.特点

1）保证插入顺序或访问顺序有序。

2）key和value都允许为空。

3）非线程安全。

4）LinkedHashMap=LinkedList+HashMap，多态实现。

https://blog.csdn.net/justloveyou_/article/details/71713781

注： HashSet子类依靠hashCode()和equal()方法来区分重复元素。

HashSet内部使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。而Map中保存key值的,会去判断当前Map中是否含有该Key对象，内部是先通过key的hashCode,确定有相同的hashCode之后，再通过equals方法判断是否相同。