Difference between double hashing and rehashing

So I implemented double hashing here i.e using two hash fun. But what does it mean by rehashing? How would I do it with this same program? Thanks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;
int hashone(int y)
{
	return (y % 13);
}
int hashtwo(int y)
{
	return (7-y%7);
}
void insertion(int size, int *arr, int index, int key)
{
	    int j = 0;
		index = hashone(key) + j*hashtwo(key); 
	    if(arr[index] == 0)
		{

			arr[index] = key; 
		}
		else
		{
			while (arr[index] != 0)
			{
				j++;
				index = hashone(key) + j*hashtwo(key);
			}
			arr[index] = key;
		}
}
int main()
{
	int size, key, elements;
	int count;
	int index;
	cout << "Enter size of array:" << endl;
	cin >> size;
	int *arr = new int[size];
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
	cout << "How many elements you want to enter:" << endl;
	cin >> elements;
	for (int i = 0; i < elements; i++)
	{
		cin >> key;
		insertion(size, arr, index = 0, key);
	}
	for (int i = 0; i < size; i++)
	{
		cout << arr[i] << " ";
	}

	system("pause");
}
I don't know what double hashing means, but rehashing is what happens when you expand the size of your hash table.

In a hash table, not all slots are going to be filled. A good hash function disperses the hashes somewhat evenly throughout the table, with hash collisions being rare. Once too many slots in the table are filled, it increases the chances of collisions happening. Usually, some threshold like 50% is used, and if >50% of the slots in the hash table become filled, the size of the table is expanded, and a rehash occurs to place the objects in new places.

A rehash is an O(n) operation and should be somewhat rare.

An easy-to-implement hash function will modulo whatever properties you combine by a prime number greater than the size of the hash table. (Not saying this is necessarily the best approach, but it's an easy one that works well enough)
Last edited on
https://www.youtube.com/watch?v=uaGWFN6djLw&t=303s
I watched this video. And I have come to the following conclusions!
1)So I have to copy the previous elements in a new array
2)send them to a new hash-function to get new indexes.
3)Make a new array of a particular size and NOW PUT those elements according to their new indexes in the array!

After this process would there be a chance for collision to happen in the new array?
Currently I am doing linear probing.
So I would apply the same process of linear probing in the new array to tackle collision?
Last edited on
1,2,3: yes.

after: yes, there is always a chance for collision. The point of having a larger array is to reduce the chance of collision. But collisions will still happen.

linear probing: yes. The way you handle the arrays does not change. Only the length of the array (and consequently) the hash function change.

Good luck!

[edit]
BTW, “double hashing” is when you have a nested hash table. You hash to find the index in the outer table, then hash again to find the index in the inner table.
Last edited on
Thanks a lot both of you!
Topic archived. No new replies allowed.