为什么我的 HashMap 实现比 JDK 慢 10 倍?
Why is my HashMap implementation 10 times slower than the JDK's?
我想知道有什么不同,我在写代码时应该注意什么。
- 测试时使用相同的参数和方法
put()
、get()
不打印
- 已使用
System.NanoTime()
测试运行时
- 我用 1-10 个 int 键和 10 个值进行了尝试,所以每个散列 returns 唯一索引,这是最佳方案
- 基于此的我的 HashSet 实现几乎与 JDK 的
一样快
这是我的简单实现:
public MyHashMap(int s) {
this.TABLE_SIZE=s;
table = new HashEntry[s];
}
class HashEntry {
int key;
String value;
public HashEntry(int k, String v) {
this.key=k;
this.value=v;
}
public int getKey() {
return key;
}
}
int TABLE_SIZE;
HashEntry[] table;
public void put(int key, String value) {
int hash = key % TABLE_SIZE;
while(table[hash] != null && table[hash].getKey() != key)
hash = (hash +1) % TABLE_SIZE;
table[hash] = new HashEntry(key, value);
}
public String get(int key) {
int hash = key % TABLE_SIZE;
while(table[hash] != null && table[hash].key != key)
hash = (hash+1) % TABLE_SIZE;
if(table[hash] == null)
return null;
else
return table[hash].value;
}
这是基准:
public static void main(String[] args) {
long start = System.nanoTime();
MyHashMap map = new MyHashMap(11);
map.put(1,"A");
map.put(2,"B");
map.put(3,"C");
map.put(4,"D");
map.put(5,"E");
map.put(6,"F");
map.put(7,"G");
map.put(8,"H");
map.put(9,"I");
map.put(10,"J");
map.get(1);
map.get(2);
map.get(3);
map.get(4);
map.get(5);
map.get(6);
map.get(7);
map.get(8);
map.get(9);
map.get(10);
long end = System.nanoTime();
System.out.println(end-start+" ns");
}
如果您 read the documentation 的 HashMap
class,您会看到它实现了基于键 hashCode
的散列 table 实现。如果地图包含大量条目,这比蛮力搜索效率要高得多,假设在将条目排序到的 "buckets" 中合理分配密钥。
也就是说,对 JVM 进行基准测试 non-trivial and easy to get wrong,如果您发现少量条目存在很大差异,则很可能是基准测试错误,而不是代码。
当它取决于性能时,从不假设一些事情。
您的假设是 "My HashSet implementation which is based on this is almost as fast as the JDK's"。不,显然不是。
这是做性能工作时最棘手的部分:怀疑一切,除非你测量得非常准确。更糟的是,您甚至进行了测量,而测量结果告诉您,您的实施速度较慢;而不是检查您的来源以及您要衡量的事物的来源;你确定测量过程一定是错误的...
我想知道有什么不同,我在写代码时应该注意什么。
- 测试时使用相同的参数和方法
put()
、get()
不打印 - 已使用
System.NanoTime()
测试运行时 - 我用 1-10 个 int 键和 10 个值进行了尝试,所以每个散列 returns 唯一索引,这是最佳方案
- 基于此的我的 HashSet 实现几乎与 JDK 的 一样快
这是我的简单实现:
public MyHashMap(int s) {
this.TABLE_SIZE=s;
table = new HashEntry[s];
}
class HashEntry {
int key;
String value;
public HashEntry(int k, String v) {
this.key=k;
this.value=v;
}
public int getKey() {
return key;
}
}
int TABLE_SIZE;
HashEntry[] table;
public void put(int key, String value) {
int hash = key % TABLE_SIZE;
while(table[hash] != null && table[hash].getKey() != key)
hash = (hash +1) % TABLE_SIZE;
table[hash] = new HashEntry(key, value);
}
public String get(int key) {
int hash = key % TABLE_SIZE;
while(table[hash] != null && table[hash].key != key)
hash = (hash+1) % TABLE_SIZE;
if(table[hash] == null)
return null;
else
return table[hash].value;
}
这是基准:
public static void main(String[] args) {
long start = System.nanoTime();
MyHashMap map = new MyHashMap(11);
map.put(1,"A");
map.put(2,"B");
map.put(3,"C");
map.put(4,"D");
map.put(5,"E");
map.put(6,"F");
map.put(7,"G");
map.put(8,"H");
map.put(9,"I");
map.put(10,"J");
map.get(1);
map.get(2);
map.get(3);
map.get(4);
map.get(5);
map.get(6);
map.get(7);
map.get(8);
map.get(9);
map.get(10);
long end = System.nanoTime();
System.out.println(end-start+" ns");
}
如果您 read the documentation 的 HashMap
class,您会看到它实现了基于键 hashCode
的散列 table 实现。如果地图包含大量条目,这比蛮力搜索效率要高得多,假设在将条目排序到的 "buckets" 中合理分配密钥。
也就是说,对 JVM 进行基准测试 non-trivial and easy to get wrong,如果您发现少量条目存在很大差异,则很可能是基准测试错误,而不是代码。
当它取决于性能时,从不假设一些事情。
您的假设是 "My HashSet implementation which is based on this is almost as fast as the JDK's"。不,显然不是。
这是做性能工作时最棘手的部分:怀疑一切,除非你测量得非常准确。更糟的是,您甚至进行了测量,而测量结果告诉您,您的实施速度较慢;而不是检查您的来源以及您要衡量的事物的来源;你确定测量过程一定是错误的...