假设我使用线性散列，假设每个块有 3 个数字并且没有溢出缓冲区。我想插入 100 个零。好像无论我分割多少次，这个数字都插不进去。线性哈希如何处理这个问题？我知道在这种情况下数据非常明显，但我只想知道线性哈希如何处理它。或者说这就是线性哈希的局限性。
这是正确的 - 数据无法容纳。如果没有溢出块，并且哈希冲突的数量超出了初始块的容量，则无法存储数据。据推测，实施会以某种方式发出失败信号。
哈希表是摊销常数时间，但最坏情况是线性时间。我会用经典的 B 树来备份哈希表，作为单个“溢出桶”，这或多或少保证了对数时间。一旦存储桶已满，该存储桶的更多内容就会被放入 B 树中。如果您的桶可以容纳至少 10 条记录，并且平均占用率保持在 40% 以内，那么少于 0.01% 的记录会溢出。然而，如果你的哈希函数由于某种原因受到损害（大量冲突开始发生），B-树将会出现，e