为什么在建立散列表时若采用线性探测再散列法处理散列冲突容易产

[问答题]

为什么在建立散列表时若采用线性探测再散列法处理散列冲突容易产生聚集（clustering）?采用其他什么方法可以减少这种聚集？

郭新鹏

线性探测再散列法

原理是：计算出的位置如果冲突了，则依次向后查找空位置插入。则一段内没有剩余空间，则在冲突时，只能向后查找空余位置再插入，则会产生聚集

采用：二次探测再散列法，可以避免产生聚集。

原理：

冲突位置+1^2 判断该位置是否为空，

冲突位置-1^2 判断该位置是否为空，

冲突位置+2^2 判断该位置是否为空，

冲突位置-2^2 判断该位置是否为空，

冲突位置+3^2 判断该位置是否为空，

......

如有误，欢迎讨论

发表于 2017-10-16 15:20:13 回复(0)

提交观点

问题信息

哈希

上传者：城市里的养猫者

难度：

1条回答 4收藏 2633浏览

扫一扫，把题目装进口袋