Hashmap、Treemap 和 LinkedHashmap 在 Java 中如何工作？

我对地图有各种疑问：

1. 迭代 Hashmap 时，无法保证迭代顺序。这是为什么呢？
2. 为什么 Hashmap 比 Treemap 更快？
3. LinkedHashMap 是如何工作的，它们如何维护顺序？是因为它们有一个双向链表，其中包含有关哪个条目存储在条目之前和之后的信息吗？

我一直在阅读 API 文档，但由于我是编程的初学者，所以在理解它时遇到了一些困难。

迭代 Hashmap 时，无法保证迭代顺序。这是为什么呢？

它们不是按照发生的时间顺序插入的，而是按照它们散列的值插入的。

例如，假设我们有一个哈希函数h(x)对于字符串“Hello”返回 127，对于“Zebra”返回 12。如果我们将这些键输入到哈希映射中，则读出它们的顺序是“Zebra”->（无论附加的值），然后是“Hello”->（无论附加的值）。

这在源代码中很明显HashMap:

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

请注意，这是哈希实际作用和代表的简化变体。可能存在哈希值冲突的情况，并且需要以某种方式解决该冲突。这是作为底漆；密钥是按照其哈希顺序插入的，但是如果您的哈希函数有缺陷或者您的对象的哈希值没有好的值，那么您可能会遇到异常行为。

为什么 Hashmap 比 Treemap 更快？

哈希运算不依赖于整个集合的大小。回想起那个h(x)仅基于我们尝试插入的单个值进行操作。如果我们将元素插入到TreeMap，我们必须考虑它们的自然顺序 - 这涉及遍历结构以找到插入点，并且还可能涉及重新平衡或重新组织结构以确保保持平衡。

有一个lot更多信息来源TreeMap's put method.

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

LinkedHashMap 是如何工作的，它们如何维护顺序？是因为它们有一个双向链表，其中包含有关哪个条目存储在条目之前和之后的信息吗？

你可以自己阅读源码，但这里的主要要点是：

• 键仍然以哈希结构分组在一起，以确保其唯一性。
• 它们的插入顺序由 FIFO 结构（如链表）保存。

可以这样想：您使用哈希函数来确保键是唯一的，如果是，则立即将其及其值插入到列表中。这样，顺序和唯一性都得以保留。