2

I am having some understanding problem with Hashing concept as follows:

Suppose, I have implemented hash table(1-D array, say A[100]) having keys as numbers. I have one simple hash function H(Key) % Table_Size, which will return target index into the hash table(while accessing value associated with this particular key).

Suppose, I want to store 0(key) into the table. When I pass this key to H(hash function), it returns random index, say 25.

There are 2 possibilities for this location in array A(having index 25):

  1. A[25] contains some key other than 0, as already been stored(previously)
  2. A[25] contains 0

First possibility has collision and it is easily identifiable(because current key:0 and already stored key:k are different), so no problem in first one.

But, for second one, how would I know weather there is a collision or not ?

As long as I know, hash table or array would be part of main memory. Suppose A[25] is stored into memory location 500.

How would I know weather this location(500) is actually empty or has been already filled by some other key ?

What status or value of memory cells represents EMPTY or NULL or UNUSED location ?

And, what if I want to store 0 as a key into this location doing collision check ?

I am currently assuming that if any memory location is EMPTY or NULL or UNUSED, then it would be in RESET state(all cells are 0's). Is this true ?

It may be silly question but I am wondering how to check collision in such cases.

--

Thanks in advance!! (Hitein, Hyderabad)

Hitein
  • 21
  • 3

3 Answers3

2

The idea here is that you must find a representation for empty cells. Usually there are three:

The first one is: Choose a value, typically 0 or -1, that you know that will never be at the table to represent an empty cell. Then if the value is there, you know that you have a free space and you can put something there.

The second is: Use an array of pointers: int *array[100], for example. Initialize the pointers as NULL. If they are NULL you can allocate an integer and set the position to point there.

The third is: Use a secondary array to tell if the position i is a valid position. Initialize all of then as empty. Whenever you put someone in array[i], you set to valid the valid[i] position.

MasterID
  • 1,510
  • 1
  • 11
  • 15
0

Either fill your Hash table with a number that you know is never going to show up, obviously not 0, maybe -1 or use pointers to int and set them to null for empty.

asbumste
  • 451
  • 3
  • 12
0

Here is a suggestion that will conserve memory and allows all values of an integer key.

Partition your hash table in two, use a bit from your key that has about equal probability of being 0 or 1 and use it to select which half of the hash table to search. Remove that bit from the key... if your key is 32 bits now you have a 31-bit tag that you search in the hash table. Use one bit in the hash table entry to indicate empty (0) or valid (1), initially all are 0. When you add an entry you set the tag (the key minus the bit used to select which half) and you set the valid bit.

amdn
  • 11,314
  • 33
  • 45