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

Question

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

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


}

Answer 1

如果你read the documentation在 HashMap 类中，您会看到它实现了一个基于键的 hashCode 的哈希表实现。如果 map 包含大量条目，这比蛮力搜索效率要高得多，假设在将条目分类到的“桶”中有合理的 key 分布。

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