0

I'm doing a hash table and have implemented the following hash function 

int linesn=8;
int hash(char *str, int table_size)
{
int sum;

// Make sure a valid string passed in
if (str==NULL) return -1;

// Sum up all the characters in the string
for( ; *str; str++) sum += *str;

// Return the sum mod the table size
return sum % table_size;
}

char *str="Carlos";
int hashv=hash(str,linesn);
printf("\nThe hash value is: %d",hashv);

As in any hash function collisions exist , how could implement a rehashing function to prevent these collisions , I read on Google but examples are complex for me, anyone could give me an idea please.

Thanks in advance

Brock Adams
  • 90,639
  • 22
  • 233
  • 295
Eduardo Robles
  • 19
  • 6

1 Answers1

2

Hashing is quite a interesting topic. I would suggest you to read Cormen. It explains clearly.

I will give you the idea of a simple method--

Here simply take a counter and whenever a element is inserted then increase it. Now if 75% of the table is filled then you just double the size of the array. Allocate twice an array. Now you just again rehash everything using new table size. That's how you do it.

To avoid collision you may use a better hash function.

Another thing incase you have collision just move to the next unfilled one. As <75% is filled in worst case you will get an empty slot. Try this. It is not that good but it works.

user2736738
  • 30,591
  • 5
  • 42
  • 56
  • @RestlessC0bra.: Yes this method mentioned yield better result. This is on of the method. Otherwise simply increasing slots won't achieve anything. There might be some modified method discussed in some research paper or something but yes basic idea of ananlysis is similar I would say.(if you find any). – user2736738 May 11 '17 at 02:44