Determining if a position is free in a Closed Hashing.

Question

How would you go about determining whether a position is already occupied or not? When the memory is allocated, all that there is in it is garbage (in C++, which is what I'm using atm). I was thinking of using an auxiliary array of bools to know whether the position is occupied, but that would demand quite a lot of additional memory.

I could also set a value for every position, but then I wouldn't be able to use said value. In both cases, I would also lose some performance initializing the values (the bools to false, the other values to 0 to indicate the position is free, for example).

Any other solutions?

Answer 1

Usually, you use a special placeholder element to indicate empty values. In the simplest case, this could be a null pointer but that would of course mean that you introduce an indirection; you can't store your values directly. In all other cases you would have to make allowance for the type actually stored. For example, if you stored 32 bit integers, you would have to reserve at least one predefined value (e.g. 0) as a sentinel element, thus reducing the range of values that may be stored in your hash table.

An additional array with flags is quite a good solution. Consider that this array could be reduced by a factor of at least 8 by storing bit flags instead of whole-byte variables (or even bools, which would require 4 bytes each on most architectures).

Answer 2

You could use boost::optional for this, instead of a raw value. That's the reason it was created, to add a not-initialized value to an item. It has a performance hit similar to initializing the values in the first place, but requires only a small amount of extra memory per item.