数据结构中的存储桶方法
进行存储桶构建时,将哈希表作为2D数组而不是一维数组。数组中的每个条目都很大,足以容纳M个项目(M不是数据量。只是一个常数)。
问题
大量浪费的空间被创造出来。
如果超过M,则需要实施另一种策略。
对于基于内存的实现而言,性能不是很好,但是如果存储桶基于磁盘,则可以实现。
对于桶装,λ>1是可以的。但是,λ越大,碰撞的机会越高。λ>1保证至少有1次碰撞(鸽子洞原理)。这样既可以增加运行时间,又可以增加用尽存储桶的可能性。
对于M个位置和每个位置Y个存储桶的哈希表
成功搜索-O(Y)最坏的情况
搜索失败-O(Y)最坏的情况
插入-O(Y)-假设成功,则存储就没有处理不成功插入的好方法。
删除-O(Y)
储存:O(M*Y)
热门推荐
10 五一公司放假祝福语简短
11 追星女孩的祝福语简短
12 给长辈端午祝福语 简短
13 生日祝福语有诗意简短
14 团圆日祝福语简短
15 中秋商务祝福语简短最新
16 温暖文艺简短祝福语短句
17 男孩上学祝福语简短的
18 入住酒店文案祝福语简短