数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法学研究数据结构中的分块法
分块构建将哈希表作为二维数组，而不是一维数组。数组中的每个条目非常大，足以容纳 M 个项目（M 不是数据量。只是一个常数）。
问题
- 浪费了大量空间。
- 如果超过 M，则需要实现另一种策略。
- 基于内存的实现性能不太好，但如果分块是基于磁盘的，则可以实现。
对于分块来说，λ>1是可以的。但是，λ越大，碰撞的可能性就越大。λ>1 可以保证至少发生 1 次碰撞（抽屉原理）。这将增加运行时间和用完分块的可能性。
对于 M 个位置和每个位置 Y 个分块的哈希表
- 成功的搜索 - 最坏情况为 O(Y)
- 不成功的搜索 - 最坏情况为 O(Y)
- 插入 - O(Y) - 假设成功，分块没有很好的方法来处理不成功的插入。
- 删除 - O(Y)
- 存储：O(M * Y)
更新于：2020-01-07
574 个浏览量
广告