java - 如果使用直接哈希函数存储节点，主存储区域数组中将有多少个元素

Question

我正在尝试弄清楚，如果要存储在一个数据结构中，每个对象都有 1000 字节的信息，其中包括由 5 位数字组成的关键字段，并且该结构中一次最多有 1500 个节点，那么如何使用除法哈希函数来计算主存储区域数组中的元素数量。我知道为了找到元素的数量，我必须这样做:

h(k)= k % 数组中元素的数量 所以会是 12345 % 1500，但这不会产生整数。我只是想弄清楚这一点。这是我在提出这个问题之前研究过的在线资源: https://modernpathshala.com/Learn/data-structure/Tutorial/8438/divison-hashfunction

Answer 1

哈希表的非常简单的想法是拥有一个包含已知数量元素的数组。每个数组元素都是数据记录的访问点。

数组中的索引是使用某种简单方法根据键确定的。理想情况下，搜索速度比线性搜索快 N 倍，其中 N 是数组大小。但只有当您将数据平均分布在所有数组条目上时，情况才会如此。此外，每个键都应该产生相同的数组索引。

哈希函数在跨数组元素提供键的线性分布方面发挥着重要作用。如果没有它，您可能会面临一个哈希表的风险，其中您的键仅命中少量的数组条目，从而显着削弱搜索性能。

现在，通常数组大小远小于要插入的数据数量。这意味着不同的键可以映射到相同的数组索引。因此，您需要提供额外的机制来在那里找到正确的元素。从这个意义上说，您需要知道进行此搜索的真正 key 。另外，反之亦然，如果键生成数组索引，则不能保证您的数据在那里。您仍然需要进行额外的搜索。

哈希表使用带有整数索引的普通非关联数组。因此，对索引的所有操作都应该产生离散的“int”数据类型。如果您查看指南，就会发现“散列”函数从键中生成一个“int”值。从该散列获取数组索引的最简单方法是使用“%”运算符。它产生了 split 的提醒。因此，如果您执行 hash % N(其中 N 是数组的大小)，您将始终获得从 0 到数组的最后一个元素 N - 1 的值。这将是您的索引。

int hash = hash_function(key);
int index = hash % N;  // 12345 % 1500 = 8 -- from your question

上面的索引将变成整数值8，用于插入和搜索。