Hashmap、Treemaps和LinkedHashmap在Java中是如何工作的？-Java问题

How do Hashmaps, Treemaps and LinkedHashmaps work in Java?(Hashmap、Treemaps和LinkedHashmap在Java中是如何工作的？)

本文介绍了Hashmap、Treemaps和LinkedHashmap在Java中是如何工作的？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有关于地图的各种问题：

迭代Hashmap时，不能保证迭代顺序。为什么呢？
为什么哈希图比树图快？
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);
}

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

为什么哈希图比树图快？

散列操作不依赖于整个集合的大小。回想一下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;
}