Hash table probing and removal of elements

[Kon V]

For our experiment of DOS attacks and probing in case of collisions it
seems that removing elements from the Hash table can cause problems.
If we rely on probing to see if an element is already in the hash
table, we will conclude that it isn't if we reach an empty bucket.
However if this bucket is empty because it's element was removed we
can reach a wrong conclusion. It can also be expensive to move
elements around especially because different hash mapping output can
reach the same bucket.
I was thinking of leaving the removed element in place, but putting
some sort of disconnected flag on it signifying it's no longer valid.
This way probing technique doesn't get broken, and if the same element
needs to be inserted again, it can just be flagged connected again.
Upon rehashing all disconnect flags will be ignored.

Is there another more accepted solution for this problem?

- Kon

[Gregory Enriquez]

Yes, including a 'deleted' or 'removed,' flag works. The flag is
sometimes called a 'modify bit,' ''delete bit,' or 'dirty bit' and the
process is also called 'lazy deletion.' I think its the cheapest way
to handle it. Also, depending on how sensitive the information is you
can just clear the data for that entry with like nulls or blank
strings. Just make sure for insert() you check the flag OR if its
empty and of course to negate the flag after. Re-hashing the same
element might not necessarily end up in the same hash index.

[Konstantin Vyshetsky]

Hi Gregory,

What would be a good way to manipulate individual bits in a number? For example, if I would like to split a 32 bit unsigned int into 2 unsigned shorts. Whats the best (speed wise) approach? I would like to use the 16 least significant bits of an IP number as hashing method. I want to compare the speed efficiency of this approach vs using mod 65536.

[Frank (sjsu) Lin]

Is 65536 a prime number?  It is a good number for hash table size?

For split, how about % and / with casting?

[Gregory Enriquez]

Hey,

If all you want is the lower 16 do what Frank said and typecast an
unsigned short. If you want to save the high order 16 bits for some
other purpose shift right by 16 and typecast.

From a security point of view, and Frank can correct me if I'm wrong,
putting a value through a hash function without utilizing the mod
operation is pretty much the same thing as storing each value
sequentially in a static array of size 65536. Since the maximum number
of combinations for the lower 16 bits is 65536 (256 is max for an 8-
bit segment: therefore 256x256 possible combinations = 65536) each
entry would just be its index in the array, which although sorted
defeats the purpose of a hash table (imo).

On Oct 17, 7:48 pm, Konstantin Vyshetsky <kvyshet...@gmail.com> wrote:
> Hi Gregory,
>
> What would be a good way to manipulate individual bits in a number? For
> example, if I would like to split a 32 bit unsigned int into 2 unsigned
> shorts. Whats the best (speed wise) approach? I would like to use the 16
> least significant bits of an IP number as hashing method. I want to compare
> the speed efficiency of this approach vs using mod 65536.
>

> On Sun, Oct 16, 2011 at 5:58 PM, Gregory Enriquez <gregoryenriq...@gmail.com

[Konstantin Vyshetsky]

65536 isn't prime, however 65537 is. I wanted to test for speed of hashing function. Since % is expensive, what if we get the key just by shifting bits around. If we assume IP addresses are uniformly distributed (they're not, and there's ~20 million reserved out of the ~4.5 possibilities comes to less than 0.5%), then the 16 least significant digits should give a fairly uniform distribution in the 1-65536 range. I wanted to try and make the hash table sizes which are next prime after a multiple of 2 and play around with it.

[Michael Cox]

For doing the splitting into the high and low words (or even each individual byte), you could try using a union/struct construction like this:

typedef union
{
struct
{
char b0;
char b1;
char b2;
char b3;
} pieces ;
int rawAddress;
}splitter;

Alternatively, you could use 2 unsigned shorts instead of the chars. Using this structure, accessing the first byte would look like this:

splitter mySplit;
mySplit.rawAddress = address;
char firstByte = mySplit.pieces.b0;

Since the union shares memory, it makes it quite easy to split the int and understand what is happening. Not sure about how efficient this is, although I wouldn't think that it would be worse than using multiple mathematical manipulations to achieve the same results.

-Michael Cox

[Konstantin Vyshetsky]

Thanks Michael,

I tried something else with bit operations. Suppose we have a 32 bit unsigned long "value", thats equal to 4,000,000,000.
to break it into 4 parts 8 bit long, I did the following:

partA = value >> 24; // shift 24 bits to the right
partB = (value >> 16) & 255; // shift 16 bits to the right and do bitwise AND with 11111111
partC = (value >> 8) & 255; // shift 8 bits to the right and do bitwise AND
partD = value & 255;

now A = 238, B = 107, C = 40, D = 0
238 * (256)^3 + 107 * (256)^2 + 40 * 256 + 0 =  4,000,000,000

I'm not sure about the speed of this, but it seems like it does the job too.

I also found some pretty cool C bit manipulation information at http://graphics.stanford.edu/~seander/bithacks.html#OperationCounting. It's pretty good site and has some useful information. I actually got asked how to determine if an integer is a power of 2 and how to swap values of 2 integers without using a temporary variable recently, so it might be useful for someone else too.

- Kon