数据结构中的存储桶方法
进行存储桶构建时,将哈希表作为2D数组而不是一维数组。数组中的每个条目都很大,足以容纳M个项目(M不是数据量。只是一个常数)。
问题
大量浪费的空间被创造出来。
如果超过M,则需要实施另一种策略。
对于基于内存的实现而言,性能不是很好,但是如果存储桶基于磁盘,则可以实现。
对于桶装,λ>1是可以的。但是,λ越大,碰撞的机会越高。λ>1保证至少有1次碰撞(鸽子洞原理)。这样既可以增加运行时间,又可以增加用尽存储桶的可能性。
对于M个位置和每个位置Y个存储桶的哈希表
成功搜索-O(Y)最坏的情况
搜索失败-O(Y)最坏的情况
插入-O(Y)-假设成功,则存储就没有处理不成功插入的好方法。
删除-O(Y)
储存:O(M*Y)