c++ - 关于散列图和术语 C++ 的一些确认

Question

我正在做一个介绍 C++ 的实验，我们已经开始使用用户名和密码数据库，我的教授希望我们将其实现为具有动态分配的 LinkedList 数组的 HashMap 。我只想确认我正在做的事情，以便我知道我做的是正确的...

1) Buckets 是存储信息的地方。我假设每个桶都是一个单独的 LinkedList。

2) 哈希函数 % 桶数将决定我在数组中使用哪个索引来存储用户和密码信息。

3) Key-Value ...我对此有点困惑。 key 是我的用户名，值是我的密码吗？

4) 负载因子是存储的键数除以桶数。所以在我的例子中，如果我有 50 个用户存储在我的 hashmap 中，它会是 50/100 吗？我的头脑很难理解这个概念。这是否意味着有时不会使用每个桶？

Answer 1

1) 正确。理想情况下，每个“桶”只包含一个值。如果哈希算法中存在冲突，那么多个值将存储在同一个桶中，因此使用链表。

2) 正确。哈希算法让您知道在 HashMap 中的何处存储/检索数据。

3) 正确。

4) 正确。你不希望 hashmap 的负载因子太高，否则插入/检索的运行时间开始接近 O(N)。散列的有用方面是它(理想情况下)允许在负载因子较低时在 O(1) 时间内插入和检索。

通常，一旦负载因子达到一定水平，hashmap 的大小就会增加并重新哈希，以降低负载因子。 HashMap 比典型的数组使用更多的空间，但这通常被插入/检索数据的速度所抵消。