Java集合之HashMap

男娘i 2021-08-13 18:13 420阅读 0赞

### HashMap ###

*  1. 简介
 *  2. 继承关系
 *  3. 深入源码
 *   *  3.1 属性
     *  3.2 内部类
     *   *  3.2.1 Node
         *  3.2.2 TreeNode
     *  3.3 构造方法
     *   *  3.3.1 HashMap()
         *  3.3.2 HashMap(int initialCapacity)
         *  3.3.3 HashMap(int initialCapacity, float loadFactor)
         *  3.3.4 HashMap(Map<? extends K, ? extends V> m)
     *  3.4 哈希计算
     *  3.5 添加元素
     *  3.6 获得元素
     *   *  3.6.1 get(Object key)
     *  3.7 删除元素
     *   *  3.7.1 remove(Object key)
     *  3.8 扩容
     *   *  3.8.1 resize()
     *  3.9 树化
 *  4. 常见问题

# 1. 简介 #

>        在 `JDK 1.8` 中 `HashMap` 是一种基于 数组 + 链表 + 红黑树 形成的数据结构，其特点是获取指定元素的时间复杂度可以视做`O(1)`，而数组和链表获取指定元素的时间复杂度则为`O(N)`。

# 2. 继承关系 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70_pic_center]

通过继承关系，我们可以看到 `Map` 接口与 `Collection` 接口并没有任何继承关系，两者算一种平级关系，很多人认为 `HashMap` 也属于集合便认为其是 `Collection` 接口的实现类。

# 3. 深入源码 #

## 3.1 属性 ##

/** * 默认初始容量，必须是 2 的整数次幂 */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /** * 数组最大长度 */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /** * 默认加载因子 */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /** * 当一条链表节点大于等于 8 时树化。 * * 我理解的树化是链表转换为红黑树才算树化，此时树化的另一个需要满足的条件是数组长度大于等于64. * 一次面试中，面试官认为调用树化的方法便是树化,此时并没有 64 这个约束。 */
        static final int TREEIFY_THRESHOLD = 8;
    
        /** * 当红黑树中节点的个数小于等于 6 时转为链表 */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /** * 链表转红黑树时，数组长度需要大于等于 64 */
        static final int MIN_TREEIFY_CAPACITY = 64;
    
        /** * 存储元素的数组，相当于桶，每个桶中并不仅仅只能存放一个元素，长度始终是 2 的整数次幂 */
        transient Node<K,V>[] table;
    
        /** * 用于保存键值对 */
        transient Set<Map.Entry<K,V>> entrySet;
    
        /** * 键值对个数 */
        transient int size;
    
        /** * 当对map修改时，会更改该值。快速失败策略 */
        transient int modCount;
    
        /** * 扩容阈值 (capacity * load factor). * 当键值对个数大于扩容阈值时，将进行扩容 */
        int threshold;
    
        /** * 加载因子 * */
        final float loadFactor;

## 3.2 内部类 ##

### 3.2.1 Node ###

// 用于表示链表节点的类
    	static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) { 
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
        }

### 3.2.2 TreeNode ###

// 用于表示红黑树的节点的类
        static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
            TreeNode(int hash, K key, V val, Node<K,V> next) { 
                super(hash, key, val, next);
            }
       }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]  
        `TreeNode` 算是 `Node` 节点的子类，所以其可以使用父类的属性。

## 3.3 构造方法 ##

### 3.3.1 HashMap() ###

/** * 使用该构造方法时，在第一次添加元素时，其数组默认长度将为 16，加载因子为默认值0.75 */
        public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

### 3.3.2 HashMap(int initialCapacity) ###

// 传入数组初始化容量，需要注意的是，并不代表 initialCapacity 的值就是数组长度的初始容量，且看下面分析
        public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

### 3.3.3 HashMap(int initialCapacity, float loadFactor) ###

// 传入数组初始化容量和加载因子
        public HashMap(int initialCapacity, float loadFactor) { 
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            // 阈值为给定的目标容量的第一个大于等于2的次幂的值
            this.threshold = tableSizeFor(initialCapacity);
        }
    
        /** * 对于给定的目标容量，返回两倍大小的幂 */
        static final int tableSizeFor(int cap) { 
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

### 3.3.4 HashMap(Map<? extends K, ? extends V> m) ###

// 将 Map 加入到当前Map中
        public HashMap(Map<? extends K, ? extends V> m) { 
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }
    
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
            int s = m.size();
            if (s > 0) { 
                if (table == null) {  // pre-size
                    float ft = ((float)s / loadFactor) + 1.0F;
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                else if (s > threshold)
                    resize();
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }

## 3.4 哈希计算 ##

static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

在计算`hash` 值时，是其 `hashCode` 右移`16`位与原 `hashCode` 进行异或运算。  
        为什么不直接取 `hashCode` 作为值呢？答案是，通常我们的`hashCode` 的高 `16` 位都是`0`，如果直接取 `hashCode，`那么高位通常不能参与运算，势必使`hash` 冲突的概率增加。

## 3.5 添加元素 ##

public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }

/** * * @param hash hash(key) * @param key the key * @param value the value to put * @param onlyIfAbsent 如果为true，则不要更改当前key的value * @param evict 如果为false，则表处于创建模式。 * @return 返回当前 key 的上一个 value，没有则为 null */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            
            // 如果数组为null或长度0，则初始化
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            
            // 如果数组中某一个位置还没有元素，那么直接在该位置放入元素
            // 如果计算某一位置？
            // 假设 hash 值对应的二进制为 01010101
            // 数组长度为16 ， 其二进制为 00010000
    		// 那么 n-1 之后的二进制则为 00001111
    		// hash&(n-1)的最大值为 15，最小值为0
    		// 所以这便是数组长度为什么始终是2的次幂，保证了不会越界 
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else { 
                Node<K,V> e; K k;
                // 如果桶中第一个元素和目标元素相同，则令 e 指向当前数组
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                // 如果桶中第一个元素是树节点，则以红黑树的方式添加元素 
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                // 如果桶中第一个元素是链表节点，则以链表的方式添加元素 
                else { 
                    for (int binCount = 0; ; ++binCount) { 
                        if ((e = p.next) == null) { 
                       		// 如果链表中没有目标 key，则添加到链表末尾
                            p.next = newNode(hash, key, value, null);
                            // 如果链表长度大于等于8，则调用树化方法
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        // 如果链表中存在指定元素，则令e指向当前元素
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                // 如果找到了对应key的元素
                if (e != null) {  // existing mapping for key
                    // 记录下旧值
                    V oldValue = e.value;
                    // 替换旧值为新值
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    // 在节点被访问后，做点什么事，hashMap中该方法并没有被实现 
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            // 如果键值对个数大于阈值，则扩容
            if (++size > threshold)
                resize();
            // 在节点被插入后，做点什么事，hashMap中该方法并没有被实现 
            afterNodeInsertion(evict);
            return null;
        }

（1）计算`key`的`hash`值；

（2）如果桶（数组）数量为`0`，则初始化桶；

（3）如果`key`所在的桶没有元素，则直接插入；

（4）如果`key`所在的桶中的第一个元素的`key`与待插入的`key`相同，说明找到了元素，转后续流程（9）处理；

（5）如果第一个元素是树节点，则调用树节点的`putTreeVal()`寻找元素或插入树节点；

（6）如果不是以上三种情况，则遍历桶对应的链表查找`key`是否存在于链表中；

（7）如果找到了对应`key`的元素，则转后续流程（9）处理；

（8）如果没找到对应`key`的元素，则在链表最后插入一个新节点并判断是否需要树化；

（9）如果找到了对应`key`的元素，则判断是否需要替换旧值，并直接返回旧值；

（10）如果插入了元素，则数量加`1`并判断是否需要扩容；

## 3.6 获得元素 ##

### 3.6.1 get(Object key) ###

public V get(Object key) { 
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            
             // 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { 
                // 桶中第一个元素是要查找的值，则直接返回
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;    
                if ((e = first.next) != null) { 
                	// 如果第一个元素是树节点，则以红黑树的方式查找
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do { 
                    	// 如果第一个元素是链表，则遍历链表
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

（1）计算`key`的`hash`值；

（2）找到`key`所在的桶及其第一个元素；

（3）如果第一个元素的`key`等于待查找的`key`，直接返回；

（4）如果第一个元素是树节点就按树的方式来查找，否则按链表方式查找；

## 3.7 删除元素 ##

### 3.7.1 remove(Object key) ###

public V remove(Object key) { 
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

/** * Implements Map.remove and related methods * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue 如果为true，则仅在值相等时删除 * @param movable 如果为false，则在删除时不要移动其他节点 * @return the node, or null if none */
        final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) { 
            Node<K,V>[] tab; Node<K,V> p; int n, index;
    		// 如果数组不为空且对应的桶中存在元素
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) { 
                Node<K,V> node = null, e; K k; V v;
                // 如果第一个元素是要找的值
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
                else if ((e = p.next) != null) { 
                	// 如果第一个元素是树节点，则以树的方式查找
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else { 
                    	// 如果是链表，则以链表的方式查找
                        do { 
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) { 
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) { 
                    // 以树的方式删除 
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    // 如果第一个元素就是目标值，则放入链表中第二个元素 
                    else if (node == p)
                        tab[index] = node.next;
                    // 以链表方式删除 
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

（1）先查找元素所在的节点；

（2）如果找到的节点是树节点，则按树的移除节点处理；

（3）如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置；

（4）否则按链表删除节点处理；

（5）修改`size`，调用移除节点后置处理等；

## 3.8 扩容 ##

### 3.8.1 resize() ###

final Node<K,V>[] resize() { 
        	// 旧数组
            Node<K,V>[] oldTab = table;
            // 旧容量
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 旧扩容门槛
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) { 
                if (oldCap >= MAXIMUM_CAPACITY) { 
                	// 如果旧容量达到了最大容量，则不再进行扩容
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                     // 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两部，阈值也变为2倍 
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
             	// 使用非默认构造方法创建的map，第一次插入元素会走到这里
            	// 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛
                newCap = oldThr;
            else {                // zero initial threshold signifies using defaults
            	// 调用默认构造方法创建的map，第一次插入元素会走到这里
           		// 如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) { 
            	// 如果新扩容门槛为0，则计算为容量*装载因子，但不能超过最大容量
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
             // 赋值扩容门槛为新门槛
            threshold = newThr;
            @SuppressWarnings({ "rawtypes","unchecked"})
            // 新建一个新容量的数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            // 把原数组赋值为新数组
            table = newTab;
            if (oldTab != null) { 
            	// 遍历旧数组
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;
                    // 如果桶中存在元素
                    if ((e = oldTab[j]) != null) { 
                        oldTab[j] = null;
                        // 如果只有一个元素，则放入新的桶中
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        // 如果第一个元素是树节点，则将树分化为两个树，放入到链表中 
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else {  // preserve order
                       		// 将原链表分化为两个链表
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do { 
                                next = e.next;
                                // (e.hash & oldCap) == 0的元素放在低位链表中
                                if ((e.hash & oldCap) == 0) { 
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else { 
                                	// (e.hash & oldCap) != 0的元素放在高位链表中
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            // 将低位链表放入新数组中和旧桶一样的位置
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            // 将高位链表放入新数组中和新桶一样的位置
                            if (hiTail != null) { 
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

（1）如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为`16`，扩容门槛为`12`；

（2）如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的`2`的`n`次方；

（3）如果旧容量大于`0`，则新容量等于旧容量的2倍，但不超过最大容量`2`的`30`次方，新扩容门槛为旧扩容门槛的`2`倍；

（4）创建一个新容量的桶；

（5）搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置；

## 3.9 树化 ##

如果插入元素后链表的长度大于等于`8`则判断是否需要树化。

final void treeifyBin(Node<K,V>[] tab, int hash) { 
            int n, index; Node<K,V> e;
            // 如果数组长度不足64，则扩容
            // 此时，原链表可能会分化为两个链表
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
            else if ((e = tab[index = (n - 1) & hash]) != null) { 
                TreeNode<K,V> hd = null, tl = null;
                do { 
      				// 把所有节点换成树节点
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                    	// hd指向头结点
                        hd = p;
                    else { 
                    	// 将单链表转化为双向链表
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                 // 如果进入过上面的循环，则从头节点开始树化
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

# 4. 常见问题 #

1.  为什么容量始终是2的幂次？

>        1、因为计算key所在的桶是 （hash & n-1），如果n是2的幂次，则保证了key所在桶的范围是0 <= index <= n-1。  
>   
>        2、在进行扩容时，原链表会分化为两条链表，高位的位置时 旧容量+从前的位置

1.  加载因子为什么是0.75？

>        假设loadfactory = 1，则键值对个数达到数组容量时，进行扩容，能够极大的利用空间，但是查询慢。  
>   
>        假设loadfactory = 0.5，则键值对达到数组容量一半时，进行扩容，查询快，但是利用的空间较少。  
>   
>        而0.75则是为了再空间与时间取一个平衡。  
>

1.  既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于等于8个的时候才转换红黑树？

>        根据泊松分布的概率学统计，当key所在的桶的链表长度增加，那么新的key到这个桶的概率在不断降低。  
>   
>        当链表8长度为时，下一个键值对到这个链表的概率接近于0，所以产生红黑树的概率也不高。

* 0:    0.60653066
         * 1:    0.30326533
         * 2:    0.07581633
         * 3:    0.01263606
         * 4:    0.00157952
         * 5:    0.00015795
         * 6:    0.00001316
         * 7:    0.00000094
         * 8:    0.00000006
         * more: less than 1 in ten million

1.  `JDK1.7` 扩容死锁产生原因

void resize(int newCapacity){ 
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if(oldCapacity == MAXIMUM_CAPACITY){ 
            threshold = Integer.MAX_VALUE;
            return ;
        }
        
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable,initHashSeedAsNeeded(newCapacity));	
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactory,MAXIMUM_CAPACITY + 1);
    }
    
    void transfer(Entry[] newTable,boolean rehash){ 
        int newCapacity = newTable.length;
        for(Entry<K,V> e:table){ 
            while (null != e){ 
                Entry<K,V> next = e.next;
                if(rehash){ 
    				// ...
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }
    }

使用两个指针来回翻转，多线程操作形成了环。

1.  `JDK1.8` 为什么不会形成环，如何做到无需`rehash`？

>        通过两组指针，将原链表直接截断分为两组高低位链表，避免了向`1.7`那样节点间相互翻转，形成环，同时也不需要`rehash`。

1.  `HashMap`为什么不选择其他树？

>        AVL树和红黑树有几点比较和区别：  
>        （1）AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。  
>        （2）红黑树更适合于插入修改密集型任务。  
>        （3）通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。

>        B树和B+树更多的是针对磁盘读取，针对磁盘读取而设计的树。

7.`HashMap` 和 `HashTable`的区别

>        **线程安全性**：`HashMap` 是线程不安全的，而`HashTable` 是线程安全的，大部分方法都是由 `synchronized`修饰。  
>   
>   
>        **效率**：`HashMap`由于不是线程安全的，所以就单线程环境下，效率高于 `HashTable`  
>   
>   
>         **容量**：`HashMap` 默认初始容量为 `16`，而 `HashTable` 模式初始容量为 `11`。如果指定初始容量的话，`HashMap` 为第一个大于等于 `2` 的整数次幂的值，而 `HashTable` 则为指定值。  
>   
>         **扩容**：`HashMap` 每次扩容容量为原来的 `2` 倍，而`HashTable` 为 `2n + 1`。  
>   
>         **底层数据结构**：`HashMap 1.7` 后，采用数组+链表+红黑树的数据结构，而`HashTable`并没有采用红黑树的数据结构。

1.  `HashMap` 和 `HashSet` 区别

>        `HashSet` 底层就是基于`HashMap` 实现的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70_pic_center]: /images/20210813/8cc123d9a3384cae948d15075063deb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210813/65d8df8653014acfb6f0ec2b848f9ef3.png