Mat*_*att 5 algorithm hashtable
只是试图理解线性探测逻辑.
使用开放寻址作为哈希表,如何确认元素不在表中.
例如,假设您有一个10桶哈希映射.假设您对一个键进行哈希,然后插入它.现在,如果要插入元素A和B并将其散列并减少到同一个桶,那么如果使用线性探针,元素A和B可能会彼此相邻.
现在,仅仅因为存储桶是空的,似乎并不意味着地图中不存在元素.例如,首先删除元素A后搜索元素B. 首先你得到一个你想要B的空桶,但是你需要再探测一个,你会找到B.它确实存在.如果该逻辑是正确的,那么您是否不必搜索整个表以确认密钥是否存在？即每次O(n)表现.
我所说的是,你不需要通过整个地图来真实地确认它不存在吗？
使用针对hashmap的单独链接方法,该问题不存在.
编辑:我的意思是在看这张照片 http://upload.wikimedia.org/wikipedia/commons/b/bf/Hash_table_5_0_1_1_1_1_0_SP.svg
如果John Smith被删除,我们会尝试找到Sandra Dee.
或者使用线性寻址是为了移动元素,以便没有这样的孔.即如果John Smith被删除,那么152到154之间的元素会被移回一个地方吗？它在描述中并没有真正看到,但这可能会有所帮助.除非ted面包师散列到154,而不是如上所述153.需要比我想象的更多的工作.
可能只需要在每个桶中使用简单的链接列表.
小智 4
在绝对最坏的情况下，确定某些项目是否在表中的算法是 O(n)。然而，在正确管理的哈希表中，这种情况永远不会发生。
当一个物品被移除时，一个墓碑应该被放置在它被移除的桌子槽位上。墓碑只是一些数据，表明那里曾经有一个元素，但已被移除。这样，每次搜索元素时，都必须遵循所使用的探测序列，直到找到空的槽。如果某个槽为空，则您已完成该哈希值的探测序列，并且知道它不会位于表中的任何其他位置。
必须搜索探测序列中每个槽的唯一方法是探测序列中没有空槽。由于您应该始终将哈希表的目标设置为大约一半为空，因此这种情况不应该发生。
