Java 中 Hashtable 、HashMap 、TreeMap 有什么不同？

王小明_HIT

发布于 2020-07-06 15:18:30

5500

发布于 2020-07-06 15:18:30

文章被收录于专栏：程序员奇点程序员奇点

Java 中 Hashtable 、HashMap 、TreeMap 有什么不同？

HashTable 最早期的 Java 类库提供的一个 Hash表实现，本身是同步的，不支持 null 键和值，对同步有导致性能开销，很少被推荐使用。
HashMap 是应该更加广泛的哈希表实现，行为上与 hashtable 一致，主要区别是 Hashmap 不是同步的，支持null 建和值。 HashMap 进行 put 或者 get 操作，可以达到常熟时间的性能，所以绝大多数场景都使用 HashMap。
TreeMap 则是基于红黑树提供的顺序访问的。与HashMap不同，它的get put remove之类的操作都是 O(log(N))的时间复杂度，具体顺序可以通过的 Comparator 或者根据键的自然顺序来判断。

Map 整体结构

Hashtable 是扩展了 Dictonary 类，类结构上与 HashMap 之类不同，HashMap 继承的是 abstractMap

HashMap 等其他 Map 都是扩展了 AbstractMap ,里面包含了通用方法抽象。

HashMap 的性能表现非常依赖哈希表的有效性。

equals 和 hashcode 基本约定

equals 相等，hashcode 一定要相等。
重写了 hashcode也要重写 eqquals
hashCode 需要保持一致性，状态改变，返回的 hash 值也需要保持一致。
equals 的对称，反射，传递等特性。

LinkedHashMap

LinkedHashMap 通常提供的是遍历顺序符合插入顺序，它的实现通过键值对维护一个双向链表，通过特定的构造函数，可以创建反映顺序的实例，通过put get computed等操作作为访问。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
    
hashMap：
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

LinkedHashMap 的使用示例：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapSample {
    public static void main(String[] args) {
        LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true) {
            protected boolean removeEldesEntry(Map.Entry<String, String> eldes) { // 实现自定义删除策略，否则行为就和普遍Map没有区别
                return size() > 3;
            }
        };
        accessOrderedMap.put("Project1", "Valhalla");
        accessOrderedMap.put("Project2", "Panama");
        accessOrderedMap.put("Project3", "Loom");
        accessOrderedMap.forEach((k, v) -> {
            System.out.println(k + ":" + v);
        });
        // 模拟访问
        accessOrderedMap.get("Project2");
        accessOrderedMap.get("Project2");
        accessOrderedMap.get("Project3");
        System.out.println("Iterate over should be not afected:");
        accessOrderedMap.forEach((k, v) -> {
            System.out.println(k + ":" + v);
        });
        // 触发删除
        accessOrderedMap.put("Project4", "Mission Control");
        System.out.println("Oldes entry should be removed:");
        accessOrderedMap.forEach((k, v) -> {// 遍历顺序不变
                    System.out.println(k + ":" + v);
                });
    }
}

LinkedHashMap 是怎么保证有序的？

LinkedHashMap 只定义了两个属性：

/**
 * The head of the doubly linked list.
 * 双向链表的头节点
 */
private transient Entry<K,V> header;
/**
 * The iteration ordering method for this linked hash map: true
 * for access-order, false for insertion-order.
 * true表示最近最少使用次序，false表示插入顺序
 */
private final boolean accessOrder;

结构如下：

image

image

构造函数：

// 构造方法1，构造一个指定初始容量和负载因子的、按照插入顺序的LinkedList
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 构造方法2，构造一个指定初始容量的LinkedHashMap，取得键值对的顺序是插入顺序
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 构造方法3，用默认的初始化容量和负载因子创建一个LinkedHashMap，取得键值对的顺序是插入顺序
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 构造方法4，通过传入的map创建一个LinkedHashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
// 构造方法5，根据指定容量、装载因子和键值对保持顺序创建一个LinkedHashMap
public LinkedHashMap(int initialCapacity,
             float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

从构造方法中可以看出，默认采用插入顺序来维持取出键值对的次序，所有改造方法都是通过父类的构造方法来创建对象。主要顺序调整，靠 put 方法中afterNodeAccess实现:

LinkedHashMap 中 afterNodeAccess 实现：

 void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
从header的角度看，新的entry需要插入到双向链表的尾部。

总得来看，再说明一遍，LinkedHashMap的实现就是HashMap+LinkedList的实现方式，以HashMap维护数据结构，以双向链表LinkedList的方式维护数据插入顺序。

TreeMap

TreeMap 整体顺序是由键的顺序关键决定，通过 Comparator 或者 Comparable 顺序来决定。

 public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

TreeMap 是如何保证顺序的？

主要是使用：

Comparator<? super K> cpr = comparator;

方式进行比较，然后插入，保证顺序。

HashMap

HashMap内部实现基本点分析。
容量（capcity）和负载系数（load factor）。
树化。

HashMap 内部的结构

HashMap 是数组+链表/红黑树的实现。数组被分为一个个桶（bucket），通过对哈希值的键值进行数组的寻址，如果哈希值相同，然后以链表形式存储。

image

HashMap 构造函数

    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);
    }

为什么HashMap要树化呢？

本质上这是个安全问题。因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端CPU大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除

http