HashMap、HashTable、TreeMap的理解

问题：

对比HashMap、HashTable、TreeMap有什么区别？

知识点

1. Map相关的简单类图

   
   image
2. hashcode、equals的一些约定

• [x] equals相等，hashcode一定相等。
• [x] 重写hashcode方法，也要重写equals方法。
• [x] hashcode要保持一致性，状态改变后返回的哈希值仍然要一致。
• [x] equals的对称、反射、传递等特性。

3. HashMap源码分析，后续文章会专门介绍（以及并发的时候无线循环占用CPU，size计算不准确等）
   部分核心精彩源码：

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            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) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

回答问题：

HashMap、HashTable、TreeMap都是常见的一些Map实现、是以键值对的形式存储和操作数据的容器类型。

HashTable是早期的Java类库提供的一个哈希表实现，本身是同步的，不支持null键和值，由于同步导致的性能开销，所以已经很少被推荐使用。

HashMap是应用更加广泛的哈希表的实现，行为上大致与HashTable一致，主要区别在于HashTable不是同步的，支持null值和键。通常情况下，HashMap进行put或者get操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选。

TreeMap是基于红黑树的一种提供顺序访问的Map，和HashMap不同，它的get、put、remove之类操作都是O（log(n))的时间复杂度，具体顺序可以由指定的Comparator来决定，或者根据键的自然顺序来判断。

参考：

• 集合中部分源码
• 极客时间APP核心技术第九讲| 对比Hashtable、HashMap、TreeMap有什么区别？
• 自己写的Demo中部分代码

声明：此为原创，转载请联系作者

---

作者：微信公众号添加公众号-遛狗的程序员 ，或者可以扫描以下二维码关注相关技术文章。

qrcode_for_gh_1ba0785324d6_430.jpg

当然喜爱技术，乐于分享的你也可以可以添加作者微信号：

WXCD.jpeg