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

Question

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

问题是，对于必须遍历链表的少量bucket(深度可达约5K个节点(，其性能优于HashTable，因为更多bucket的差异大三个数量级。

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

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

Fetch SmallTable: 0.0000013630
Fetch BigTable: 0.0000002560

我的问题是关于我的逻辑的健全性以及这里额外的活动部分。我已经将我的测试粘贴到HashTable和底层Node结构实现的链接旁边。

从这里的人们那里寻找深度/经验，他们可能能够提供关于变量的交互式反馈，这些变量包括密钥长度和哈希冲突率、桶密度等。

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个bucket，并假装其余的都不存在
• System.identityHashCode不是一个有用的散列函数，尤其是在字符串上，尤其是当你希望真正找到其中的元素时。。。是否
• 当你在使用Node.next时，你并没有把它当作一个字段，不妨去掉它