Rehashing a hash table with quadratic probing

Hi everyone,

I'm doing an assignment which requires me to create a hash table using quadratic probing as a way to resolve collision. Moreover, the assignment asks me to rehash the table every time the load factor gets above 0.5. The code below is my attempt to do that but I'm not sure with the efficiency of my rehash function since my prof said that it should be O(n) and I believe that what I do is O(n^2). I'd be grateful if someone could give some comments and suggestions about my put and rehash function. Thank you.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class Hashtable{
private:
	int sze; //size: number of values are currently in the hashtable
	int cap; //capacity: the size of the hashtable

	struct HashNode
        {
		string value;
	};

	 HashNode** arr;  //bucket

	//determine whether the number is prime or not
	bool IsPrime(int number)
        {
		if (number == 2 || number == 3)
	        return true;

	    if (number % 2 == 0 || number % 3 == 0)
	        return false;

	    int divisor = 6;
	    while (divisor * divisor - 2 * divisor + 1 <= number)
	    {

	        if (number % (divisor - 1) == 0)
	            return false;

	        if (number % (divisor + 1) == 0)
	            return false;

	        divisor += 6;

	    }

	    return true;

	}

	//find the next prime number that is >= a
	int NextPrime(int a)
        {
		while (!IsPrime(++a)){ }
    	return a;
	}

	int hashing(const string &s) const
        {
		int h = 0;
		for (int i = 0; i < s.size(); i++)
		{
			h += int(s[i]);
		}

		return h;
	}

	void rehashing ()
	{
		int oldCap = cap;
		sze = 0;
		//Doubling the capacity
		cap = NextPrime(cap*2);

		HashNode** oldArr = arr;
		arr = new HashNode*[cap]();

		//moving the values to the new after rehashing
		for (int i = 0; i < oldCap; i++){
			if (oldArr[i] != nullptr){
				for (int j = 0; j < cap; j++){
					int index = (hashing(oldArr[i]->value) + j*j) % cap;
					if (arr[index] == nullptr){
						arr[index] = new HashNode {oldArr[i]->value};
						sze++;
						break;
					} //if
				} //for
				delete oldArr[i];
				oldArr[i] = nullptr;
			} //if
		} //for

		delete[] oldArr;
	}


public:
	// Constructor
	Hashtable(int ini_cap = 101) : sze(0), cap(ini_cap), arr(new HashNode*[cap]){
		for (int i = 0; i < cap; i++)
		{
			arr[i] = nullptr;
		}

	}

	//Destructor
	~Hashtable()
        {
		for (int i = 0; i < cap; i++)
                {
			 if (arr[i] != nullptr){
				delete arr[i];
				arr[i] = nullptr;
			}
		}
		delete[] arr;
	}

	double load_factor() const {return double(sze)/cap;}

	void put(const string& s)
        {
		//Initialize a new node for the new input
		HashNode* temp = new HashNode{s};
		
		//Insert using quadratic probing
		for (int i = 0; i < cap; i++)
                {
			int index = (hashing(s) + i*i) % cap;
			if (arr[index] == nullptr){
				arr[index] = temp;
				sze++;
				break;
			}
		}

		if (load_factor() > 0.5)
                {
	            rehashing();
		} //if 

	} //put
};
Last edited on
Topic archived. No new replies allowed.