为什么我的 HashMap 实现比 JDK 慢 10 倍？

Question

我想知道有什么不同，我在写代码时应该注意什么。

测试时使用相同的参数和方法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");


}

Answer 1

如果您 read the documentation 的 HashMap class，您会看到它实现了基于键 hashCode 的散列 table 实现。如果地图包含大量条目，这比蛮力搜索效率要高得多，假设在将条目排序到的 "buckets" 中合理分配密钥。

也就是说，对 JVM 进行基准测试 non-trivial and easy to get wrong，如果您发现少量条目存在很大差异，则很可能是基准测试错误，而不是代码。

Answer 2

当它取决于性能时，从不假设一些事情。

您的假设是 "My HashSet implementation which is based on this is almost as fast as the JDK's"。不，显然不是。

这是做性能工作时最棘手的部分：怀疑一切，除非你测量得非常准确。更糟的是，您甚至进行了测量，而测量结果告诉您，您的实施速度较慢；而不是检查您的来源以及您要衡量的事物的来源；你确定测量过程一定是错误的...

为什么我的 HashMap 实现比 JDK 慢 10 倍？

Why is my HashMap implementation 10 times slower than the JDK's?

java

performance

hashmap

runtime