java - 为什么字典初始化时不会发生内存溢出？

Question

背景:字典使用哈希函数为您输入的每个值生成索引。

1. 虽然说索引在每个输入的情况下都是唯一的，但我只是想知道生成的确切哈希函数是什么每个输入都有唯一的值？
2. 让我们假设(因为我不确定)，存在一个哈希函数，它为每个输入生成唯一的索引。那么字典将被初始化为多大的大小呢？我假设它是动态的，但如果一个索引是 10，而另一个输入的索引是 123456，该怎么办？它必须使用大小为 123457 的数组 - 这不会导致内存溢出吗？

PS:我对哈希函数是什么以及它的作用有理论知识，但我还没有看到它的实际实现。另外，由于许多语言都有用于此目的的内置数据结构，这让我感到好奇:)

Answer 1

您关于哈希函数唯一性的假设是错误的。

如果我们以 Java 的 HashMap 为例，它使用键的 hashCode() 并对其应用补充哈希函数(以防止较差的哈希值)质量哈希函数)。然后将计算出的哈希值映射到映射存储中的索引，该索引通常比哈希值小得多。

因此，即使哈希函数会为每个键返回唯一的值(这不是必需的)，HashMap 仍然会将该值规范化为一个更小的存储索引。 HashMap 。因此不会出现溢出(只要您不向 Map 中插入太多元素)。