Displaying hash table problem

Hello everyone, I just wanted some input on this program I'm working on for class.
For some reason, my hash table seems to get deleted when I try to display it a second time. The first try is fine, but when I call the class function to display it again, it is suddenly empty.

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

#ifndef hashMap_h
#define hashMap_h

#include <string>
#include <iostream>

using namespace std;

class HashEntry {
public:
	int key;
	string stringKey;
	string value;
	HashEntry *next;


	HashEntry(int key, string stringKey, string value) 
	{
		this->key = key;
		this->stringKey = stringKey;
		this->value = value;
		this->next = nullptr;
	}


};
//============================================
const int TABLE_SIZE = 11;

class HashMap {
private:
	HashEntry **table;
public:
	HashMap() {
		table = new HashEntry*[TABLE_SIZE];
		for (int i = 0; i < TABLE_SIZE; i++)
			table[i] = NULL;
	}

	bool find(string key, string& value) {
		// return value associated with key
		// return -1 if not found
		int indexHash = 0;

		indexHash = key.length();

		int hash = (indexHash % TABLE_SIZE);

		while (table[hash] != nullptr && table[hash]->key != indexHash)
			hash = (hash + 1) % TABLE_SIZE; //linear probe

		if (table[hash] == nullptr)
			return false;  // not found

		else //table[hash]->key != key
		{
			value = table[hash]->value;
			return true;
		}
	}

	void insert(string key, string value) 
	{
		/*Modified so that the key is a string that is converted to
		an integer that becomes the proper key type.*/

		int indexHash = 0;

		indexHash = key.length();

		int hash = (indexHash % TABLE_SIZE);

		if (table[hash] == NULL)
			table[hash] = new HashEntry(indexHash, key, value);
		else if (indexHash > 10) 
			/*Not sure if this is necessary, as a remainder would never go above 
			a divisor in most cases, but i'll leave this here just in case */
			cout << "Illegal key entry for " << key << " " << value << " please try again with a different key" << endl;
		else
			{
			HashEntry *input = table[hash];
			while (input->next != nullptr)
				input = input->next;
				input->next = new HashEntry(indexHash, key, value);
			}

		
	}

	

	void display() const {
		// used for debugging purpose only to inspect what's in the map
		

		for (int i = 0; i < TABLE_SIZE; ++i)
			if (table[i] == nullptr)
				cout << "[" << i << ", Nil, Nil" << "]" << endl;
			else
			{
				while (table[i] != nullptr)
				{
					cout << "[" << i << ", " << table[i]->stringKey << ", " << table[i]->value << "]" << endl;
					table[i] = table[i]->next;
				}

			}

		cout << endl;
	}


	

	~HashMap() {
		for (int i = 0; i < TABLE_SIZE; i++)
			if (table[i] != NULL)
				delete table[i];
		delete[] table;
	}



Much of the code is largely provided by my professor, we are just supposed to modify it to meet certain specifications.

On a side note, can anyone tell me how to delete specific nodes properly from a bucket? I can delete a bucket by itself just fine, but the whole thing goes haywire otherwise.
Last edited on
do yourself a favor and encapsulate your list instead of working with raw nodes
1
2
3
4
5
				while (table[i] != nullptr)
				{
					cout << "[" << i << ", " << table[i]->stringKey << ", " << table[i]->value << "]" << endl;
					table[i] = table[i]->next;
				}
when that loop ends table[i] will be null
so the second time that you call the display() function, all table[i] entries are null

solution: don't touch the head of the list
Shouldn't it just reset after I call it again? Why does it suddenly change up my entries when I never explicitly wanted it to? I have had similar print outs that work the same way, but this is my first time making a hash table.
Last edited on
say that you have a deck of cards in your hand
you draw them one by one, show to your audience and put them on a table
now you are wondering why you don't have any cards in your hand.

> Shouldn't it just reset after I call it again?
no, ¿why would it? when you modify a variable, its value changes.

> Why does it suddenly change up my entries when I never explicitly wanted it to?
¿what do you think you are doing here table[i] = table[i]->next;?
you are changing table[i]

> but this is my first time making a hash table.
¿do you realise that you have an array of linked lists?
table[i] is a linked list, and you would make everything clearer if you treat it as such
1
2
3
4
void insert(string key, string value){
   index = hash_function(key);
   table[index].push_back( entry(key, value ) );
}


Now look at your display() function and notice that you are moving the head of the list
Shouldn't it just reset after I call it again?
Variables don't get reset unless you cause that to happen, either by assigning to them, or instantiating them again (as with local variables).

Why does it suddenly change up my entries when I never explicitly wanted it to?
Because what you wanted, and what you actually did, are different:
1
2
3
4
5
while (table[i] != nullptr)
{
	cout << "[" << i << ", " << table[i]->stringKey << ", " << table[i]->value << "]" << endl;
	table[i] = table[i]->next;
}

At line 4 you explicitly change table[i]. At line 1 you explicitly keep looping until table[i] is nullptr. It won't change back by itself.

To fix this, use a separate variable to walk through the list. I like to use a for() loop for this. It separates the "loopy" code from the "do it for each entry" code.
1
2
3
for (HashEntry *p = table[i]; p; p = p->next) {
	cout << "[" << i << ", " << p->stringKey << ", " << p->value << "]" << endl;
}

There's also a bug in find(). It assumes that there is at most 1 item in a bucket and if you get a hash collision, you move forward to find an empty bucket. That isn't how insert() works. Since HashEntry has a next pointer, I assume that insert() does what you want.
Oh God, I really shouldn't do this during a sugar rush. I get what ya'll are saying now. I feel so dumb right now. Thanks for the help everyone.

I have literally spent the whole day thinking that the damn display function would not overwrite my table when I called it! I knew that! Why did I forget that!
Last edited on
Don't be hard on yourself. This stuff is complex and takes time. The best thing you can do is seek help earlier when you get stuck. As a rule of thumb, if you get stuck for more than an hour on the same thing, seek help.
Registered users can post here. Sign in or register to post.