为什么字典初始化时不发生内存溢出
本文关键字：内存 溢出 字典 初始化 为什么 | 更新日期: 2023-09-27 18:32:04
背景：字典使用哈希函数为您输入的每个值生成索引。
- 虽然说索引在每个输入的情况下都是唯一的，但我只是想知道生成确切的哈希函数是什么每个输入的唯一值 ？
- 让我们假设（因为我不确定），存在一个哈希函数，它为每个输入生成唯一的索引。那么字典将被初始化为什么大小？我假设它是动态的，但是如果一个索引是 10 而另一个输入是123456呢？它必须使用大小123457数组 - 这不会导致内存溢出吗？
PS ：我对哈希函数是什么以及它的作用有理论知识，但我还没有看到它的实际实现。此外，由于许多语言都有用于此目的的内置数据结构，这让我感到好奇:)
你关于哈希函数唯一性的假设是错误的。
例如，如果我们以 Java HashMap为例，它使用密钥的hashCode()并在其上应用补充哈希函数（以防止质量差的哈希函数）。然后是获取计算出的哈希值并将其映射到映射存储中的索引，该索引通常比哈希值小得多。
因此，即使哈希函数将为每个键返回一个唯一值（不是必需的），HashMap仍将该值规范化为HashMap存储的更小索引。因此没有溢出（只要您不要在Map中插入太多元素）。