数据结构中的存储桶方法

进行存储桶构建时,将哈希表作为2D数组而不是一维数组。数组中的每个条目都很大,足以容纳M个项目(M不是数据量。只是一个常数)。

问题

  • 大量浪费的空间被创造出来。

  • 如果超过M,则需要实施另一种策略。

  • 对于基于内存的实现而言,性能不是很好,但是如果存储桶基于磁盘,则可以实现。

对于桶装,λ> 1是可以的。但是,λ越大,碰撞的机会越高。λ> 1保证至少有1次碰撞(鸽子洞原理)。这样既可以增加运行时间,又可以增加用尽存储桶的可能性。

对于M个位置和每个位置Y个存储桶的哈希表

  • 成功搜索-O(Y)最坏的情况

  • 搜索失败-O(Y)最坏的情况

  • 插入-O(Y)-假设成功,则存储就没有处理不成功插入的好方法。

  • 删除-O(Y)

  • 储存:O(M * Y)