Hashmaps、Treemaps 和 LinkedHashmaps 如何在 Java 中工作？

Question

我有很多关于地图的问题：

迭代Hashmap时，迭代顺序不保证。为什么会这样？
为什么 Hashmap 比 Treemap 快？
LinkedHashMaps是如何工作的，它们是如何维护顺序的？是不是因为他们有一个双向链表，包含了一个条目前后存储了哪个条目的信息？

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

Answer 1

为简短起见：映射和集合通常是未排序的数据结构。如果你想要"sorted sets"，你最好使用列表或数组。

您的问题更多是关于数据结构，而不是真正具体的或 java 相关的编程问题，因此，您应该首先阅读这些内容。（抱歉 post 作为答案：评论问题需要 50 个代表）

Answer 2

When iterating a Hashmap, there will be no guarantee about the iteration order. Now why is that?

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

例如，假设我们有一个散列函数 h(x) 其中 returns 127 用于字符串 "Hello"，12 用于 "Zebra"。如果我们将这些键输入到我们的哈希映射中，它们被读出的顺序是 "Zebra" -> （附加的任何值），然后是 "Hello" -> （附加的任何值）。

这在 HashMap 的源代码中很明显：

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

请注意，这是哈希实际作用和代表的简化变体。哈希值可能存在冲突，并且需要以某种方式解决该冲突。这是作为入门书；密钥按其散列顺序插入，但如果您的散列函数有缺陷或者您没有合适的对象散列值，那么您可能运行出现异常行为。

Why are Hashmaps faster than Treemaps?

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

TreeMap 的 put 方法的来源还有很多。

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

How do LinkedHashMaps work, how do they maintain the order? Is it because they have a doubly-linked list that contains the information about which entry is stored before and after an entry?

You can read the source for yourself，但这里的主要内容是：

键仍然以散列结构组合在一起以确保它们的唯一性。
它们的插入顺序由 FIFO 结构保存，就像链表一样。

可以这样想：你使用散列函数来确保键是唯一的，如果是，你就立即将它和它的值插入到列表中。这样，顺序和唯一性都得以保留。

Hashmaps、Treemaps 和 LinkedHashmaps 如何在 Java 中工作？

How do Hashmaps, Treemaps and LinkedHashmaps work in Java?

java

hashmap

treemap

linkedhashmap