为什么我的HashMap实现比JDK慢10倍?
我想知道是什么改变了我在编写代码时应该知道什么。为什么我的HashMap实现比JDK慢10倍?
- 使用相同的参数和方法
put()
,get()
而不打印 - 用于
System.NanoTime()
测试运行时 - 我具有1-10 INT键试图将其与10个值测试 时,所以每一个单个散列返回独特的索引,这是最优化的场景
- 基于此的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");
}
如果您在HashMap
类read the documentation,你看,它实现了一个散列基于的表执行的钥匙。如果映射包含不平凡数量的条目,假设在对其进行排序的“桶”之间进行合理的密钥分配,这比蛮力搜索更有效。
也就是说,基准JVM是non-trivial and easy to get wrong,如果你看到与少量条目有很大差异,它可能很容易成为基准测试错误而不是代码。
'hashCode'在这里是不相关的,因为OP正试图用'int'键创建一个映射。 –
@PaulBoddington:'hashCode'与我在其中使用的句子相关:*“...它[HashMap]根据键的'hashCode'实现一个哈希表。”*我不是在谈论OP的代码在那里。 –
我用下面的方法重写了代码:我不是使用HashEntry类型,而是使用了2个长度相同的数组:'int [] keys'和'String [] values',并且执行速度比JDK快。现在我感到困惑。 @ T.J.Crowder – freestar
如果没有测试显示比较的另一端,即使用'HashMap',问题是不完整的。你还应该展示你的微基准,因为这些微小的错误是完全错误的结果。 – dasblinkenlight