关于LinkedList节点哈希表性能的java问题

Question

我在类的init上实现了一个具有可变大小bucket的哈希表，它只是一个在运行时调整大小的链表数组

问题在于，对于必须遍历链表（深度可以达到约5K个节点）的少量存储桶，其性能优于具有三个数量级差异的更多存储桶的哈希表

    int SMALL_BUCKET_SIZE = 10;
    int BIG_BUCKET_SIZE = 10000;

    HashTable<String, Integer> smallHashTable = new HashTable<>(SMALL_BUCKET_SIZE);
    HashTable<String, Integer> bigHashtTable = new HashTable<>(BIG_BUCKET_SIZE);

对于搜索，我希望较大的哈希表为O（1），其中较小的哈希表具有较高的冲突率，由于遍历链接节点而花费更多的时间，但我下面的数字显示较小的哈希表优于较宽的哈希表

Fetch SmallTable: 0.000007
Fetch BigTable: 0.000018

所以我决定循环我的哈希表。获得JIT和JVM优化的千倍因子。现在我看到的数字似乎证实了我的预期

Fetch SmallTable: 0.0000013630
Fetch BigTable: 0.0000002560

我的问题是我的逻辑是否合理，以及这里的其他活动部分。我已经将测试粘贴到了哈希表和底层节点结构实现的链接旁边

从这里的人们那里寻找深度/经验，他们可能能够提供关于影响因素的交互反馈，如键长度和散列冲突率、桶密度等

哈希表测试。java

@Test
public void canInitializeHashTableWithBucketsForPerformance() throws InterruptedException {
    double smallTableTime, bigTableTime;
    int SMALL_BUCKET_SIZE = 10;
    int BIG_BUCKET_SIZE = 10000;

    HashTable<String, Integer> smallHashTable = new HashTable<>(SMALL_BUCKET_SIZE);
    HashTable<String, Integer> bigHashtTable = new HashTable<>(BIG_BUCKET_SIZE);
    List<String> strings = generateRandomStringKeys(1000);

    strings.forEach(string -> bigHashtTable.put(string, 10));
    strings.forEach(string -> smallHashTable.put(string, 10));

    Consumer<String> bigHashGet = bigHashtTable::get;
    Consumer<String> smallHashGet = smallHashTable::get;

    String theString = strings.get(strings.size() - 1);

    smallTableTime = getElapsedTimeFactoringOutJavaOptimization(theString, smallHashGet);
    bigTableTime = getElapsedTimeFactoringOutJavaOptimization(theString, bigHashGet);

    System.out.println(String.format("Fetch SmallTable: %.10f", smallTableTime));
    System.out.println(String.format("Fetch BigTable:   %.10f", bigTableTime));

    assertTrue(smallTableTime > bigTableTime);
}

public double getElapsedTimeFactoringOutJavaOptimization(String s, Consumer<String> aMethod) {
    long start = 0, end = 0;

    for (int i = 0; i < 1000; i++) {
        start = System.nanoTime();
        aMethod.accept(s);
        end = System.nanoTime();
    }

    return (end - start) / 1_000_000_000D;
}

public List<String> generateRandomStringKeys(int numOfRandomKeys) {
    List<String> keys = new ArrayList<>();

    for (int i = 0; i < numOfRandomKeys; i++) {
        byte[] array = new byte[10];
        new Random().nextBytes(array);
        keys.add(new String(array, Charset.forName("UTF-8")));
    }

    return keys;
}

测试可以在这里找到-Github - HashTableTest.java

实现也可以在这里找到-Github - HashTable.java

Answer 1

这里有很多错误，但有几个错误包括：

• 运行此操作1000次并为每个操作取nanoTime的差值不会使基准测试有效。说真的，使用JMH。或者至少运行一千万次
• 对于不同大小的表，哈希表的工作方式实际上没有任何不同。您使用table[getHash(key) % RADIX]，这基本上意味着然而表很大，您只在其中使用10个bucket，并假装其余的bucket不存在
• System.identityHashCode不是一个有用的哈希函数，尤其是在字符串上，尤其是当您希望实际找到其中的元素时。。。或者不是
• 当您使用它时，您没有使用Node.next作为字段，最好将其删除