
平台论坛博客文库

› 论坛 › 程序设计 › Java › Java HashMap冲突实例

Java HashMap冲突实例 [复制链接]

凝望长空

家境小康

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2011-12-31 16:25 |只看该作者 |倒序浏览

Java HashMap冲突实例

参考：PHP数组的Hash冲突实例 http://www.laruence.com/2011/12/30/2435.html

看到这篇帖子，其实数据结构真实的存在于身边。模仿上文，弄个Java版的。

1、重写hashcode，最好（一定）要重写equals。即hashcode相同则equals返回true

Java代码

1.import java.util.HashMap;
2.
3.public class TestWorstHashMap {
4.
5. private static final int testSize = 100000;
6. private static final int specialId = 1;
7. private static final String specialName = "1";
8.
9. /************************************ test1 **************************************/
10.
11. class BadModel {
12. private int id;
13. private String name;
14.
15. public BadModel(int id, String name) {
16. this.id = id;
17. this.name = name;
18. }
19.
20. /**
21. * @see java.util.HashMap.put(K, V)
22. */
23. @Override
24. public boolean equals(Object obj) {
25. if (obj instanceof BadModel) {
26. return id == ((BadModel) obj).id && name.equals(((BadModel) obj).name);
27. }
28.
29. return false;
30. }
31.
32. @Override
33. public int hashCode() {
34. return id;
35. }
36. }
37.
38. void testBadModel1() {
39. HashMap<BadModel, Object> map = new HashMap<BadModel, Object>();
40.
41. long start = System.currentTimeMillis();
42. for (int i = 0; i < testSize; i++) {
43. BadModel model = new BadModel(specialId, "Name" + i);
44. map.put(model, "test" + i);
45. }
46.
47. long end = System.currentTimeMillis();
48. System.out.println("BadModel the same id : " + (end - start));
49. }
50.
51. void testBadModel2() {
52. HashMap<BadModel, Object> map = new HashMap<BadModel, Object>();
53.
54. long start = System.currentTimeMillis();
55. for (int i = 0; i < testSize; i++) {
56. BadModel model = new BadModel(specialId, specialName);
57. map.put(model, "test" + i);
58. }
59. long end = System.currentTimeMillis();
60.
61. System.out.println("BadModel the same id & name : " + (end - start));
62. }
63.
64. /************************************ test2 **************************************/
65.
66. class GoodModel {
67. private int id;
68. private String name;
69.
70. public GoodModel(int id, String name) {
71. this.id = id;
72. this.name = name;
73. }
74.
75. @Override
76. public boolean equals(Object obj) {
77. if (obj instanceof GoodModel) {
78. return id == ((GoodModel) obj).id && name.equals(((GoodModel) obj).name);
79. }
80.
81. return false;
82. }
83.
84. @Override
85. public int hashCode() {
86. return id + name.hashCode();
87. }
88. }
89.
90. void testGoodModel() {
91. HashMap<GoodModel, Object> map = new HashMap<GoodModel, Object>();
92.
93. long start = System.currentTimeMillis();
94. for (int i = 0; i < testSize; i++) {
95. GoodModel model = new GoodModel(specialId, "Name" + i);
96. map.put(model, "test" + i);
97. }
98.
99. long end = System.currentTimeMillis();
100. System.out.println("GoodModel the same id : " + (end - start));
101. }
102.
103. public static void main(String[] args) {
104. TestWorstHashMap test = new TestWorstHashMap();
105. test.testBadModel1();
106. test.testBadModel2();
107. test.testGoodModel();
108. }
109.
110.}
import java.util.HashMap;
public class TestWorstHashMap {
private static final int testSize = 100000;
private static final int specialId = 1;
private static final String specialName = "1";
/************************************ test1 **************************************/
class BadModel {
private int id;
private String name;
public BadModel(int id, String name) {
this.id = id;
this.name = name;
}
/**
* @see java.util.HashMap.put(K, V)
*/
@Override
public boolean equals(Object obj) {
if (obj instanceof BadModel) {
return id == ((BadModel) obj).id && name.equals(((BadModel) obj).name);
}
return false;
}
@Override
public int hashCode() {
return id;
}
}
void testBadModel1() {
HashMap<BadModel, Object> map = new HashMap<BadModel, Object>();
long start = System.currentTimeMillis();
for (int i = 0; i < testSize; i++) {
BadModel model = new BadModel(specialId, "Name" + i);
map.put(model, "test" + i);
}
long end = System.currentTimeMillis();
System.out.println("BadModel the same id : " + (end - start));
}
void testBadModel2() {
HashMap<BadModel, Object> map = new HashMap<BadModel, Object>();
long start = System.currentTimeMillis();
for (int i = 0; i < testSize; i++) {
BadModel model = new BadModel(specialId, specialName);
map.put(model, "test" + i);
}
long end = System.currentTimeMillis();
System.out.println("BadModel the same id & name : " + (end - start));
}
/************************************ test2 **************************************/
class GoodModel {
private int id;
private String name;
public GoodModel(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof GoodModel) {
return id == ((GoodModel) obj).id && name.equals(((GoodModel) obj).name);
}
return false;
}
@Override
public int hashCode() {
return id + name.hashCode();
}
}
void testGoodModel() {
HashMap<GoodModel, Object> map = new HashMap<GoodModel, Object>();
long start = System.currentTimeMillis();
for (int i = 0; i < testSize; i++) {
GoodModel model = new GoodModel(specialId, "Name" + i);
map.put(model, "test" + i);
}
long end = System.currentTimeMillis();
System.out.println("GoodModel the same id : " + (end - start));
}
public static void main(String[] args) {
TestWorstHashMap test = new TestWorstHashMap();
test.testBadModel1();
test.testBadModel2();
test.testGoodModel();
}
}

复制代码

测试结果：

BadModel the same id : 141454

BadModel the same id & name : 28

GoodModel the same id : 92

1、 table为一个Entry[] 数组。
2、以<key, value>的形式存储为一个Entry。
3、相同hashcode的key，以链头插入的方式保存。

从上图看出，我们造的数据都保存在table的一个Entry的链表中了。

文库|博客

小忻黑夜

丰衣足食

论坛徽章:: 0

2楼 [报告]

发表于 2011-12-31 16:42 |只看该作者

谢谢分享

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

返回列表

Chinaunix › 论坛 › 程序设计 › Java › Java HashMap冲突实例