从哈希表中删除条目的最佳方式 [英] Best way to remove an entry from a hash table

问题描述

从使用线性检测的哈希表中删除条目的最佳方法是什么？一个方法是使用一个标志来表示删除的元素？有没有比这更好的方法？

解决方案

一个简单的技巧是：

1. 查找并删除所需的元素


2. 转到下一个料斗


3. 如果料斗为空，退出


4. 如果存储桶已满，请删除该存储区中的元素，并使用常规方法将其重新添加到散列表中。在重新添加之前，必须删除该项目，因为可能会将该项目添加回其原始位置。


5. 重复步骤2。

这种技术保持你的桌子整洁，减少了较慢的删除。

What is the best way to remove an entry from a hashtable that uses linear probing? One way to do this would be to use a flag to indicate deleted elements? Are there any ways better than this?

解决方案

An easy technique is to:

1. Find and remove the desired element
2. Go to the next bucket
3. If the bucket is empty, quit
4. If the bucket is full, delete the element in that bucket and re-add it to the hash table using the normal means. The item must be removed before re-adding, because it is likely that the item could be added back into its original spot.
5. Repeat step 2.

This technique keeps your table tidy at the expense of slightly slower deletions.

这篇关于从哈希表中删除条目的最佳方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！