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

Question

我在 Class 的 init 上实现了一个具有可变大小桶的哈希表，只是一个 linked 列表的数组在运行时大小。

问题在于，对于必须遍历 linked-list 的少量存储桶（深度可以达到大约 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);

我希望较大的 HashTable 的搜索时间复杂度为 O(1)，其中较小的哈希table 具有较高的冲突率，由于遍历 linked 节点需要更多时间，但是我下面的数字显示较小的 table 优于较宽的 table.

Fetch SmallTable: 0.000007
Fetch BigTable: 0.000018

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

Fetch SmallTable: 0.0000013630
Fetch BigTable: 0.0000002560

我的问题是关于我的逻辑的合理性以及这里的其他活动部分。我已将我的测试与 link 一起粘贴到 HashTable 和底层节点结构的实现中。

从这里的人那里寻找 depth/experience，他们可能能够提供有关影响此因素的变量的交互式反馈，例如密钥长度和哈希冲突率、存储桶密度等

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，您的散列 table 实际上并没有任何不同。您使用 table[getHash(key) % RADIX]，这基本上意味着然而大 table 是，您只使用其中的 10 个桶并假装其余的不存在。
System.identityHashCode 不是一个有用的散列函数，尤其是在字符串上，尤其是当您希望真正找到其中存在的元素时……或不存在。
当您使用它时，您并没有将 Node.next 用作一个字段，不妨摆脱它。

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

Question regarding performance of HashTable of LinkedList Nodes

java

hashtable

data-structures