如何在Java中实现HashMap数据结构？

Question

我想实现一个HashMap数据结构，但是我不太清楚该如何处理底层数组结构。如果我没记错的话，在HashMap中，每个键都经过哈希处理并转换为整数，该整数用于引用数组索引。由于直接引用，搜索时间为O（1）。假设K是关键，V是值。我们可以创建一个大小为n的V型数组，该数组将驻留在hash（K）函数产生的索引中。但是，hash（K）不会产生连续的索引，Java的数组也不稀疏，要解决此问题，我们可以创建一个非常大的数组来容纳元素，但效率不高，它将容纳很多NULL元素。一种解决方案是按连续顺序存储元素，要查找元素，我们必须搜索整个数组并检查元素的键，但这将是线性时间。我想实现直接访问。

Answer 1

您可以通过将哈希对数组大小取模来使用较小的数组进行基础存储，如下所示：

hash = hashfunc(key)
index = hash % array_size

这是一个很好的解决方案，因为您可以使基础数组保持相对密集，而不必修改哈希函数，并且它不会影响时间复杂度。