java - 关于LinkedList节点的HashTable的性能问题

Question

我在类的初始化中实现了一个具有可变大小存储桶的哈希表，只是一个在运行时调整大小的链表数组。

问题是，对于必须遍历链表的少量存储桶(深度可以达到大约 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)，其中较小的哈希表具有较高的冲突率，由于遍历链接节点而花费更多时间，但下面的数字显示较小的表优于较宽的表表。

获取 SmallTable:0.000007
获取BigTable:0.000018

所以我决定循环我的 HashTable.get 一千次来考虑 JIT 和 JVM 优化。现在我开始看到的数字似乎证实了我的预期。

获取 SmallTable:0.0000013630
获取BigTable:0.0000002560

我的问题是关于我的逻辑的健全性以及这里的其他 Activity 部分。我将我的测试与 HashTable 和底层 Node 结构的实现的链接一起粘贴。

从这里寻找深度/经验的人，他们可能能够提供有关影响此因素的变量的交互式反馈，例如 key 长度和散列冲突率、存储桶密度等。

HashTableTest.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个桶并假装其余的不存在.
• System.identityHashCode 不是一个有用的哈希函数，尤其是在字符串上，尤其是当您希望实际找到其中存在的元素...或不存在时。
• 当您使用它时，您并没有使用 Node.next 作为字段，因此最好摆脱它。