如果 keySet() 维护 HashMap 的顺序,为什么我们需要 LinkedHashMap?
Why do we need LinkedHashMap if keySet() maintains order for a HashMap?
public class HashMapKeySet {
public static void main(String[] args) {
Map<HashCodeSame,Boolean> map=new HashMap();
map.put(new HashCodeSame(10),true);
map.put(new HashCodeSame(2),false);
for(HashCodeSame i:map.keySet())
System.out.println("Key: "+i+"\t Key Value: "+i.getA()+"\t Value: "+map.get(i)+"\t Hashcode: "+i
.hashCode());
System.out.println("\nEntry Set******");
for(Map.Entry<HashCodeSame, Boolean> i:map.entrySet())
System.out.println("Key: "+i.getKey().getA()+"\t Value: "+i.getValue()+"\t Hashcode: "+i.hashCode());
System.out.println("\nValues******");
for(Boolean i:map.values())
System.out.println("Key: "+i+"\t Value: "+map.get(i)+"\t Hashcode: "+i.hashCode());
}
static class HashCodeSame{
private int a;
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
HashCodeSame(int a){
this.a=a;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
HashCodeSame that = (HashCodeSame) o;
return a == that.a;
}
@Override
public int hashCode() {
return 1;
}
}
}
如果你能在上面的例子中看到,我已经在所有情况下明确地将 hashcode() return 设置为 1,以检查当 key.hashcode() 发生冲突时会发生什么哈希图。发生了什么,为这些 Map.Entry 对象维护了一个链表,例如
1(key.hashcode()) will link to <2,false> will link to <10,true>
(据我了解,因为在真值之后输入了假值)。
但是当我执行 keySet() 时,true 先 returned 然后 false,而不是 false 先 returning。
所以,我在这里假设的是,因为 keySet() 是一个集合并且集合保持顺序,所以我们在迭代时得到 true 和 false。但是,话又说回来,为什么我们不说 hashmap 维护顺序,因为唯一的检索方式是按顺序。或者我们为什么要使用LinkedHashMap?
Key: DS.HashMapKeySet$HashCodeSame@1 Key Value: 10 Value: true Hashcode: 1
Key: DS.HashMapKeySet$HashCodeSame@1 Key Value: 2 Value: false Hashcode: 1
Entry Set******
Key: 10 Value: true Hashcode: 1230
Key: 2 Value: false Hashcode: 1236
Values******
Key: true Value: null Hashcode: 1231
Key: false Value: null Hashcode: 1237
现在,当我将 chsnge 哈希码方法添加到 return 时,我点赞了
@Override
public int hashCode() {
return a;
}
我得到相反的顺序。再加上
map.put(new HashCodeSame(10),true);
map.put(new HashCodeSame(2),false);
map.put(new HashCodeSame(7),false);
map.put(new HashCodeSame(3),true);
map.put(new HashCodeSame(9),true);
收到的输出是,
Key: DS.HashMapKeySet$HashCodeSame@2 Key Value: 2 Value: false Hashcode: 2
Key: DS.HashMapKeySet$HashCodeSame@3 Key Value: 3 Value: false Hashcode: 3
Key: DS.HashMapKeySet$HashCodeSame@7 Key Value: 7 Value: false Hashcode: 7
Key: DS.HashMapKeySet$HashCodeSame@9 Key Value: 9 Value: true Hashcode: 9
Key: DS.HashMapKeySet$HashCodeSame@a Key Value: 10 Value: true Hashcode: 10
Entry Set******
Key: 2 Value: false Hashcode: 1239
Key: 3 Value: false Hashcode: 1238
Key: 7 Value: false Hashcode: 1234
Key: 9 Value: true Hashcode: 1222
Key: 10 Value: true Hashcode: 1221
Values******
Key: false Value: null Hashcode: 1237
Key: false Value: null Hashcode: 1237
Key: false Value: null Hashcode: 1237
Key: true Value: null Hashcode: 1231
Key: true Value: null Hashcode: 1231
现在又让我想知道,为什么顺序是有序的。?谁能详细解释一下 hashmap 的 keySet()、entrySet() 方法是如何工作的?
的 Java 文档中回答您的问题
Hashtable和Map接口的链表实现,具有predictable迭代顺序。此实现与 HashMap 的不同之处在于它通过其所有条目维护一个双向链表 运行。该链表定义了迭代顺序,通常是将键插入映射的顺序(插入顺序)。请注意,如果将键重新插入到映射中,插入顺序不会受到影响。 (如果调用 m.put(k, v) 而 m.containsKey(k) 在调用之前 return 为真,则将密钥 k 重新插入到映射 m 中。)
此实现使其客户端免于 HashMap(和 Hashtable)提供的未指定的、通常混乱的排序,而不会增加与 TreeMap 相关的成本。它可用于生成与原始地图具有相同顺序的地图副本,而不管原始地图的实现如何:
void foo(Map m) {
Map copy = new LinkedHashMap(m);
...
}
HashMap
没有定义的迭代顺序,LinkedHashMap
有指定的迭代顺序.
HashMap
的困难在于很容易构建简单的示例,其中迭代顺序相当 predictable 并且相当 stable,即使这不能保证。
例如,假设您这样做了:
Map<String, Boolean> map = new HashMap<>();
String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (int i = 0; i < str.length(); i++) {
map.put(str.substring(i, i+1), true);
}
System.out.println(map.keySet());
结果是
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]
嘿!那些是有序的!嗯,原因是 String 的 hashCode() 函数非常糟糕,而且对于单字符字符串来说特别糟糕。这是 String 的 hashCode() specification. Essentially it's a sum-and-multiply, but for a single-character string it's just the Unicode value of that char
. So the hashcodes of the single-character strings above are 65, 66, ... 90. The internal table of HashMap
is always a power of two, and in this case it's 64 entries long. The table entry used is the key's hashCode()
value right-shifted by 16 bits and XORed with itself, modulo the table size. (See the code here。)因此,这些单字符字符串最终在 HashMap
table 中的顺序存储桶中,在数组位置 1、2、... 26 中。
密钥迭代按顺序通过桶进行,因此密钥最终会按照它们放入的顺序出现。同样,这不能保证,它只是碰巧以这种方式工作,因为如上所述的各种实现。
现在考虑 HashCodeSame
其中 hashCode()
函数每次 returns 1。将这些对象中的一些添加到 HashMap
将导致它们最终都在同一个桶中,并且由于迭代按顺序向下遍历链表,它们将按顺序出现:
Map<HashCodeSame, Boolean> map = new HashMap<>();
for (int i = 0; i < 8; i++) {
map.put(new HashCodeSame(i), true);
}
System.out.println(map.keySet());
(我添加了一个 toString()
方法来完成显而易见的事情。)结果是:
[HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(5), HCS(6), HCS(7)]
同样,由于实现的巧合,密钥按顺序出现,但原因与上述不同。
但是等等!在JDK 8中,如果同一个桶中出现过多条目,HashMap
会将桶从线性链表转换为平衡树。如果超过 8 个条目最终出现在同一个桶中,就会发生这种情况。让我们试试看:
Map<HashCodeSame, Boolean> map = new HashMap<>();
for (int i = 0; i < 20; i++) {
map.put(new HashCodeSame(i), true);
}
System.out.println(map.keySet());
结果是:
[HCS(5), HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(6),
HCS(18), HCS(7), HCS(11), HCS(16), HCS(17), HCS(15), HCS(13),
HCS(14), HCS(8), HCS(12), HCS(9), HCS(10), HCS(19)]
底线是 HashMap
而不是 维护定义的迭代顺序。如果您想要特定的迭代顺序,您 必须 使用 LinkedHashMap
或排序映射,例如 TreeMap
。不幸的是,HashMap
有一个相当 stable 和 predictable 的迭代顺序,事实上,predictable 足以让人们认为它的顺序很好-已定义,但实际上并未定义。
为了帮助解决这个问题,在 JDK 9 中,新的基于哈希的集合实现将 随机化 它们的迭代顺序 运行 运行.例如:
Set<String> set = Set.of("A", "B", "C", "D", "E",
"F", "G", "H", "I", "J");
System.out.println(set);
当 运行 在 JVM 的不同调用中打印出以下内容:
[I, H, J, A, C, B, E, D, G, F]
[C, B, A, G, F, E, D, J, I, H]
[A, B, C, H, I, J, D, E, F, G]
(在 JVM 的单个 运行 中,迭代顺序是 stable。此外,现有集合如 HashMap
做 not 将它们的迭代顺序随机化。)
public class HashMapKeySet {
public static void main(String[] args) {
Map<HashCodeSame,Boolean> map=new HashMap();
map.put(new HashCodeSame(10),true);
map.put(new HashCodeSame(2),false);
for(HashCodeSame i:map.keySet())
System.out.println("Key: "+i+"\t Key Value: "+i.getA()+"\t Value: "+map.get(i)+"\t Hashcode: "+i
.hashCode());
System.out.println("\nEntry Set******");
for(Map.Entry<HashCodeSame, Boolean> i:map.entrySet())
System.out.println("Key: "+i.getKey().getA()+"\t Value: "+i.getValue()+"\t Hashcode: "+i.hashCode());
System.out.println("\nValues******");
for(Boolean i:map.values())
System.out.println("Key: "+i+"\t Value: "+map.get(i)+"\t Hashcode: "+i.hashCode());
}
static class HashCodeSame{
private int a;
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
HashCodeSame(int a){
this.a=a;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
HashCodeSame that = (HashCodeSame) o;
return a == that.a;
}
@Override
public int hashCode() {
return 1;
}
}
}
如果你能在上面的例子中看到,我已经在所有情况下明确地将 hashcode() return 设置为 1,以检查当 key.hashcode() 发生冲突时会发生什么哈希图。发生了什么,为这些 Map.Entry 对象维护了一个链表,例如
1(key.hashcode()) will link to <2,false> will link to <10,true>
(据我了解,因为在真值之后输入了假值)。
但是当我执行 keySet() 时,true 先 returned 然后 false,而不是 false 先 returning。
所以,我在这里假设的是,因为 keySet() 是一个集合并且集合保持顺序,所以我们在迭代时得到 true 和 false。但是,话又说回来,为什么我们不说 hashmap 维护顺序,因为唯一的检索方式是按顺序。或者我们为什么要使用LinkedHashMap?
Key: DS.HashMapKeySet$HashCodeSame@1 Key Value: 10 Value: true Hashcode: 1
Key: DS.HashMapKeySet$HashCodeSame@1 Key Value: 2 Value: false Hashcode: 1
Entry Set******
Key: 10 Value: true Hashcode: 1230
Key: 2 Value: false Hashcode: 1236
Values******
Key: true Value: null Hashcode: 1231
Key: false Value: null Hashcode: 1237
现在,当我将 chsnge 哈希码方法添加到 return 时,我点赞了
@Override
public int hashCode() {
return a;
}
我得到相反的顺序。再加上
map.put(new HashCodeSame(10),true);
map.put(new HashCodeSame(2),false);
map.put(new HashCodeSame(7),false);
map.put(new HashCodeSame(3),true);
map.put(new HashCodeSame(9),true);
收到的输出是,
Key: DS.HashMapKeySet$HashCodeSame@2 Key Value: 2 Value: false Hashcode: 2
Key: DS.HashMapKeySet$HashCodeSame@3 Key Value: 3 Value: false Hashcode: 3
Key: DS.HashMapKeySet$HashCodeSame@7 Key Value: 7 Value: false Hashcode: 7
Key: DS.HashMapKeySet$HashCodeSame@9 Key Value: 9 Value: true Hashcode: 9
Key: DS.HashMapKeySet$HashCodeSame@a Key Value: 10 Value: true Hashcode: 10
Entry Set******
Key: 2 Value: false Hashcode: 1239
Key: 3 Value: false Hashcode: 1238
Key: 7 Value: false Hashcode: 1234
Key: 9 Value: true Hashcode: 1222
Key: 10 Value: true Hashcode: 1221
Values******
Key: false Value: null Hashcode: 1237
Key: false Value: null Hashcode: 1237
Key: false Value: null Hashcode: 1237
Key: true Value: null Hashcode: 1231
Key: true Value: null Hashcode: 1231
现在又让我想知道,为什么顺序是有序的。?谁能详细解释一下 hashmap 的 keySet()、entrySet() 方法是如何工作的?
Hashtable和Map接口的链表实现,具有predictable迭代顺序。此实现与 HashMap 的不同之处在于它通过其所有条目维护一个双向链表 运行。该链表定义了迭代顺序,通常是将键插入映射的顺序(插入顺序)。请注意,如果将键重新插入到映射中,插入顺序不会受到影响。 (如果调用 m.put(k, v) 而 m.containsKey(k) 在调用之前 return 为真,则将密钥 k 重新插入到映射 m 中。)
此实现使其客户端免于 HashMap(和 Hashtable)提供的未指定的、通常混乱的排序,而不会增加与 TreeMap 相关的成本。它可用于生成与原始地图具有相同顺序的地图副本,而不管原始地图的实现如何:
void foo(Map m) {
Map copy = new LinkedHashMap(m);
...
}
HashMap
没有定义的迭代顺序,LinkedHashMap
有指定的迭代顺序.
HashMap
的困难在于很容易构建简单的示例,其中迭代顺序相当 predictable 并且相当 stable,即使这不能保证。
例如,假设您这样做了:
Map<String, Boolean> map = new HashMap<>();
String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (int i = 0; i < str.length(); i++) {
map.put(str.substring(i, i+1), true);
}
System.out.println(map.keySet());
结果是
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]
嘿!那些是有序的!嗯,原因是 String 的 hashCode() 函数非常糟糕,而且对于单字符字符串来说特别糟糕。这是 String 的 hashCode() specification. Essentially it's a sum-and-multiply, but for a single-character string it's just the Unicode value of that char
. So the hashcodes of the single-character strings above are 65, 66, ... 90. The internal table of HashMap
is always a power of two, and in this case it's 64 entries long. The table entry used is the key's hashCode()
value right-shifted by 16 bits and XORed with itself, modulo the table size. (See the code here。)因此,这些单字符字符串最终在 HashMap
table 中的顺序存储桶中,在数组位置 1、2、... 26 中。
密钥迭代按顺序通过桶进行,因此密钥最终会按照它们放入的顺序出现。同样,这不能保证,它只是碰巧以这种方式工作,因为如上所述的各种实现。
现在考虑 HashCodeSame
其中 hashCode()
函数每次 returns 1。将这些对象中的一些添加到 HashMap
将导致它们最终都在同一个桶中,并且由于迭代按顺序向下遍历链表,它们将按顺序出现:
Map<HashCodeSame, Boolean> map = new HashMap<>();
for (int i = 0; i < 8; i++) {
map.put(new HashCodeSame(i), true);
}
System.out.println(map.keySet());
(我添加了一个 toString()
方法来完成显而易见的事情。)结果是:
[HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(5), HCS(6), HCS(7)]
同样,由于实现的巧合,密钥按顺序出现,但原因与上述不同。
但是等等!在JDK 8中,如果同一个桶中出现过多条目,HashMap
会将桶从线性链表转换为平衡树。如果超过 8 个条目最终出现在同一个桶中,就会发生这种情况。让我们试试看:
Map<HashCodeSame, Boolean> map = new HashMap<>();
for (int i = 0; i < 20; i++) {
map.put(new HashCodeSame(i), true);
}
System.out.println(map.keySet());
结果是:
[HCS(5), HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(6),
HCS(18), HCS(7), HCS(11), HCS(16), HCS(17), HCS(15), HCS(13),
HCS(14), HCS(8), HCS(12), HCS(9), HCS(10), HCS(19)]
底线是 HashMap
而不是 维护定义的迭代顺序。如果您想要特定的迭代顺序,您 必须 使用 LinkedHashMap
或排序映射,例如 TreeMap
。不幸的是,HashMap
有一个相当 stable 和 predictable 的迭代顺序,事实上,predictable 足以让人们认为它的顺序很好-已定义,但实际上并未定义。
为了帮助解决这个问题,在 JDK 9 中,新的基于哈希的集合实现将 随机化 它们的迭代顺序 运行 运行.例如:
Set<String> set = Set.of("A", "B", "C", "D", "E",
"F", "G", "H", "I", "J");
System.out.println(set);
当 运行 在 JVM 的不同调用中打印出以下内容:
[I, H, J, A, C, B, E, D, G, F]
[C, B, A, G, F, E, D, J, I, H]
[A, B, C, H, I, J, D, E, F, G]
(在 JVM 的单个 运行 中,迭代顺序是 stable。此外,现有集合如 HashMap
做 not 将它们的迭代顺序随机化。)