您将如何确定职位是否已被占用？分配内存时，其中的所有内容都是垃圾(在 C++ 中，这就是我正在使用的 atm)。我正在考虑使用 bool 值的辅助数组来了解该位置是否已被占用，但这需要大量额外的内存。
我也可以为每个位置设置一个值，但那样我就无法使用所述值。在这两种情况下，我也会损失一些初始化值的性能(例如， bool 值为 false，其他值为 0 以指示位置空闲)。
还有其他解决方案吗？
最佳答案
通常，您使用特殊的占位符元素来指示空值。在最简单的情况下，这可能是一个空指针，但这当然意味着您引入了一个间接寻址；你不能直接存储你的值。在所有其他情况下，您必须考虑实际存储的类型。例如，如果您存储 32 位整数，则必须至少保留一个预定义值(例如 0)作为标记元素，从而减少可能存储在哈希表中的值的范围。
带有标志的附加数组是一个很好的解决方案。考虑到通过存储位标志而不是全字节变量(甚至是 bool，在大多数架构中每个都需要 4 个字节)，这个数组可以减少至少 8 倍。
关于c++ - 确定一个位置在封闭哈希中是否空闲，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/431647/