我有关于 map 的各种问题:
- 迭代 Hashmap 时,无法保证迭代顺序。这是为什么呢?
- 为什么 HashMap 比树形图更快?
- LinkedHashMap 是如何工作的,它们如何维护顺序?是因为它们有一个双向链表,其中包含有关条目之前和之后存储哪个条目的信息吗?
我一直在阅读 API 文档,但由于我是编程的初学者,所以在理解它时遇到了一些困难。
最佳答案
When iterating a Hashmap, there will be no guarantee about the iteration order. Now why is that?
它们不是按照发生的时间顺序插入的,而是按照它们散列的值插入。
例如,假设我们有一个哈希函数 h(x),它对于字符串“Hello”返回 127,对于“Zebra”返回 12。如果我们将这些键输入 HashMap ,则读出它们的顺序是“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 ,但这里的主要要点是:
- key 仍以哈希结构分组在一起,以确保其唯一性。
- 它们的插入顺序由 FIFO 结构(如链表)保存。
这样想:您使用哈希函数来确保键是唯一的,如果是,则立即将其及其值插入到列表中。这样,顺序和唯一性都得以保留。
关于java - Hashmap、Treemap 和 LinkedHashmap 在 Java 中如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31168093/