Java-09：Hashtable、HashMap、TreeMap有什么不同？

你的名字 2023-01-10 11:47 96阅读 0赞

惯例，看类对比，先来看下继承结构关系

#### 1.继承图谱 ####

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

Map接口表示这个集合是一个键值映射的数据结构，Map不能包含重复的Key，每个键只能映射到一个值。Map提供了三种遍历集合的方法，分别是entrySet()，KeySet()，values()来得到Map中的数据，除此之外，还提供了很多操作Map的方法，如put()，remove()，get(Object)等。

Dictionary抽象类：Map接口替代了它

AbstractMap抽象类：实现Map接口的常用方法

SortMap接口：提供排序的基本方法

NavigableMap接口： 提供了给定搜索目标报告最接近匹配项的导航方法 ，方法有lowerEntry()，lowerKey()，floorEntry()，floorKey()等。

HashMap是基于哈希表实现Map接口，允许空键值，但不能保证元素顺序，它与HashTable的差别就是HashMap支持null，线程不安全。

TreeMap是基于红黑树的NavigableMap实现。 根据映射键的自然顺序或在映射创建时提供的Comparator对映射进行排序，具体取决于所使用的构造函数。

下面，我们具体来看下HashMap的实现细节

#### 2. HashMap ####

在HashMap类上的说明写到，HashMap是基于哈希表实现Map接口，允许空键和空值，不保证元素顺序，通过哈希函数将元素正确地分散在桶中。

HashMap存在两个影响性能的因素：加载因子和初始容量。负载因子默认为0.75，这设置在时间和空间成本之间提供了一个很好的权衡。

我们知道哈希表的底层结构是一个数组，存放的对象为entry，也就是(key-value)，key通过执行哈希算法得到数组的下标。但哈希表避免不了哈希冲突，解决哈希冲突的方法有开放地址法(重新选择一块空闲位置，二维数组)，再散列法，链地址法。

由此，哈希表的两个关键点：哈希算法和哈希冲突。

哈希表采用不同解决哈希冲突的方法会有不同数据结构支持，在HashMap中，HashMap采用链地址法来解决哈希冲突。

由此，我们可以想象到一个正常的HashMap的图示会是如下所示：

![在这里插入图片描述][20210123232925777.jpg_pic_center]

下面，我们来看下，HashMap的具体实现：

1.  entry节点：由于是链地址法，所以在Node中会存在next指向下一个节点

static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            ... 
        }

1.  HashMap中重要的成员变量：

/** * 哈希表引用 */
    	transient Node<K,V>[] table;
        /** * 下次扩容的阀值 = 容量 * 加载因子. * threshold = capacity * load factor */
        int threshold;
        /** * 加载因子 */
        final float loadFactor;

1.  HashMap中重要的静态变量：一些默认初始值和阈值

/** * 默认初始容量 */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
        /** * 最大容量 */
        static final int MAXIMUM_CAPACITY = 1 << 30;
        /** * 默认加载因子 */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        /** * 链表达到一个长度会转化为红黑树 */
        static final int TREEIFY_THRESHOLD = 8;
        /** * 红黑树达到一定小的长度会转化为链表 */
        static final int UNTREEIFY_THRESHOLD = 6;
        /** * 当哈希表的容量达到这个树，才能将链表转化为红黑树 */
        static final int MIN_TREEIFY_CAPACITY = 64;

1.  HashMap中常用的构造函数，空参数构造只赋值一个成员变量

public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
        }
    
    	/** * 主要构造方法 */
    	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;
            this.threshold = tableSizeFor(initialCapacity);
        }
    
    	/** * 对于给定的目标容量，返回两倍大小的幂。 * Returns a power of two size for the given target capacity. */
        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;
        }

1.  put方法，主要方法还是putVal()

在看源码之前，我们可以先做个流程判断

*  在正常情况下，我们通过哈希算法和Key得到数组中存放的位置，如果那个位置有数据，我们就加到链表的尾部
 *  特殊情况
    
     *  如果table为null，我们需要初始化它
     *  如果我们加入数据时，刚好达到这个table的阈值，该进行扩容了
     *  如果我们加入的表中已经有了
     *  如果我们加入到链表的尾部，刚好达到了可以树化的阈值

我们用上面的逻辑来看看

// @param onlyIfAbsent if true, don't change existing value
    	// @param evict if false, the table is in creation mode.
    	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
            
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            // 1. 判断table是否为null
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            // 2. 判断插入的位置是否有数据
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else { 
                Node<K,V> e; K k;
                // 3. 判断新插入数据的Key是否与链表的首个节点相同
                if (p.hash == hash &&
                    (  (k = p.key) == key || (key != null && key.equals(k)) ))
                    e = p;
                // 4. 判断是不是已经树化结构，如果是把它加入到树中
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { 
                    // 5. 遍历链表有没有节点的数据和新加入的数据相同，如果没有，则添加到链表尾部
                    for (int binCount = 0; ; ++binCount) { 
                        if ((e = p.next) == null) { 
                            p.next = newNode(hash, key, value, null);
                            // 6. 链表是否已经达到树化的条件
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        
                        p = e;
                    }
                }
                if (e != null) { 
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            // 7. 查看添加数据是否需要扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

从上面看下来，流程和我们表述地差不多，有一个关键方法：resize()。

1.  扩容方法：resize()

我们还是照上面的方式来一遍，什么时候需要进行扩容

*  table还没有构建好的时候，也就是没有数据的时候，仅仅调用了构造参数
 *  添加数据后，table中的数据大于了threshold

那，它会如何扩容呢？

*  如果是从空table的情况过来，有几种情况
    
     *  有初始容量值传入，按照一定规则生成table
     *  没有初始值传入，得到默认大小的table，也就是DEFAULT\_INITIAL\_CAPACITY大小，也就是16。
 *  如果是添加数据后需要扩容的，那它会按照一定的倍数扩容，想ArrayList那般1.5倍扩容，扩容后，将所有数据重新通过哈希算法加入表中。

final Node<K,V>[] resize() { 
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            // 1. 插入数据后table需要扩容
            if (oldCap > 0) { 
                // 如果table的容量已经达到最大值的情况
                if (oldCap >= MAXIMUM_CAPACITY) { 
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                // 扩容大小为旧容量*2 且扩容后的容量大小不超过最大值且扩容前的容量不小于默认初始值
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; 
            }
            // 2. 构造参数时传入初始值
            else if (oldThr > 0) 
                newCap = oldThr;
            // 3. table为空表的情况
            else {                
                newCap = DEFAULT_INITIAL_CAPACITY; // 16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16*0.75=12
            }
            // 4. 传入容量初始值的构造器情况或者插入数据后，newThr确认失败
            if (newThr == 0) { 
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            // 5. 重新计算hash，重新入位
            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;
                                if ((e.hash & oldCap) == 0) { 
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else { 
                                    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;
        }

这里总结下resize()方法中各种情况：

1.  使用空参构造器构造
    
     *  这种情况，在构造器方法时只会初始化参数 `loadFactor = DEFAULT_LOAD_FACTOR;`，在resize方法中得到oldCap和oldThr都为0，就会走步骤3，将newCap和NewThre赋值16和16\*0.75，最后初始化一个newCap大小的Node数组返回。
2.  使用有参(指定容量)构造器构造
    
     *  这种情况，调用构造器方法时会对`this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);`赋值，resize方法中得到的oldCap和oldThr的值会是0和2倍的initialCapacity传入值。
     *  先走步骤二，将oldThr赋值给newCap，那newCap的大小就是initialCapacity\*2，再走步骤4计算newThr。
3.  数据插入后需要扩容
    
     *  先走步骤一，这里有三种情况：
     *  情况一：newCap = oldCap \* 2，如果newCap小于MAXIMUM\_CAPACITY且大于DEFAULT\_INITIAL\_CAPACITY，则newThr = oldThr \* 2；
     *  情况二：newCap计算出来的值大于MAXIMUM\_CAPACITY，那newThr会直接赋值Integer.MAX\_VALUE；
     *  情况三：newCap计算出来的值小于DEFAULT\_INITIAL\_CAPACITY，会按newCap \* loadFactor计算；
4.  hash算法

hash算法的目的：我们只要把下面这个方法理解成我将不同key的hashCode散射到int的不同值去，在通过低位掩码的方式来取得数组下标。

static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    	// 低位掩码的方式
    	first = tab[(n - 1) & hash]

[Hash算法原理链接][Hash]

这就是HashMap的简单流程，其他方法都可以采用实现模拟的方式来学习。

**TreeMap**，等我 ，红黑树还没搞定！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/5a2fe7954c224e40bebf8520b9479a1a.png
[20210123232925777.jpg_pic_center]: /images/20221119/fc0e5a6013b34351866c9c364ebe3f87.png
[Hash]: https://www.zhihu.com/question/20733617