Xoá một phần tử trong Hash table bị lỗi

[ThuyHienHien (Hiền Đỗ)]

Em đang làm bài về tạo Hash table nhưng khi xóa muốn xóa một phần tử sau đó in lại bảng thì xảy ra lỗi. Mong mọi người giúp em với ạ. Em cảm ơn.

class HashMap
{
private:
	Item** htable;
public:
	HashMap()
	{
		htable = new Item*[TABLE_SIZE];
		for (int i = 0; i < TABLE_SIZE; i++)
			htable[i] = NULL;
	}
	~HashMap()
	{
		for (int i = 0; i < TABLE_SIZE; ++i)
		{
			Item* entry = htable[i];
			while (entry != NULL)
			{
				Item* prev = entry;
				entry = entry->next;
				delete prev;
			}
		}
		delete[] htable;
	}
	/*
	 * Hash Function
	 */
	int HashFunc(int key)
	{
		return key % TABLE_SIZE;
	}

	/*
	 * Insert Element at a key
	 */
	int Insert(int key, char *info)
	{
		int hash_val = HashFunc(key);
		Item* prev = NULL;
		Item* entry = htable[hash_val];
		while (entry != NULL)
		{
			prev = entry;
			entry = entry->next;
		}
		if (entry == NULL)
		{
			entry = new Item(key, info);
			if (prev == NULL)
			{
				htable[hash_val] = entry;
			}
			else
			{
				prev->next = entry;
			}
		}
		else
		{
			entry->info = info;
		}
		return 1;
	}
	/*
	 * Remove Element at a key
	 */
	int Remove(int key)
	{
		int hash_val = HashFunc(key);
		Item* entry = htable[hash_val];
		Item* prev = NULL;
		if (entry == NULL || entry->key != key)
		{
			cout << "No Element found at key " << key << endl;
			return 1;
		}

		while (entry->next != NULL)
		{
			prev = entry;
			entry = entry->next;
		}
		if (prev != NULL)
		{
			prev->next = entry->next;
		}
		delete entry;
		cout << "Element Deleted" << endl;
		return 1;
	}
	/*
	 * Search Element at a key
	 */
	int Search(int key)
	{
		bool flag = false;
		int hash_val = HashFunc(key);
		Item* entry = htable[hash_val];
		while (entry != NULL)
		{
			if (entry->key == key)
			{
				cout << entry->info << " ";
				flag = true;
			}
			entry = entry->next;
		}
		if (!flag)
			return -1;
	}
	int output(int key, char *info) {
		int i;
		Item *entry = NULL;
		Item *next;
		cout << "Slot\tKey\tInfo" << endl;
		for (i = 0; i < TABLE_SIZE; i++)
		{
			entry = htable[i];
			while (entry != NULL) {
				cout << " " << i << "\t" << entry->key << "\t" << entry->info << endl;
				entry = entry->next;
			}
		}
		return 1;
	}
};

[hungaya (Hung)]

Giả sử Hash Table có 2 entries, entry 0 chứa linked list gồm 1 node X, entry 1 chưa có gì.

+---+    +-----+
| 0 | -->|  X  |--> NULL
|   |    +-----+
+---+
| 1 | --> NULL
|   |
+---+

Khi gọi remove(X) để xoá Node X, lúc này các biến có giá trị:

• key = X
• hash_val = 0
• prev = NULL
• entry = Node X
• entry->next = NULL

Vậy nên:

• if (entry == NULL...) không thực hiện
• while (entry->next != NULL) bị fail từ vòng lặp đầu tiên, không chạy while luôn.
• if(prev != NULL) cũng không thực hiện.

Lệnh delete entry chạy, xoá đi bộ nhớ của Node X, nhưng em quên đặt giá trị htable[0] = NULL. Nên Hash Table thành ra thế này:

+---+    +---------+
| 0 | -->|  Trash  |
|   |    +---------+
+---+
| 1 | --> NULL
|   |
+---+

Lúc em chạy ouput(), em duyệt trên entry 0, truy cập vào trash, OS báo lỗi.

---

Cách sửa: thêm else

if (prev != NULL)
{
	prev->next = entry->next;
}
else
{
	htable[hash_val] = NULL;
}

[ThuyHienHien (Hiền Đỗ)]

Vâng cuối cùng e cũng hiểu r. Em cảm ơn a nhiều.