Hash Table

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.9 kB
4
Indexable
Never
#include<iostream>
#include<list>
using namespace std;
 
int hashGroup = 13;  // slot in hashTable

/* Cau truc Hash Table */
struct Hash {
	int slot;
	// Pointer to an array containing slots
	list<int>* table;
};
/* Ham Khoi Tao Hash Table */
void create_Hash(Hash& h, int b);
/* Ham Hashing */
int hash_func(Hash h, int x);
/* Them Item vao HTable */
void insertItem(Hash& h, int key);
/* Xoa 1 Item */
void deleteItem(Hash h, int key);
// Display hash table
void display_hash(Hash h);
// Kiem tra bang bam
bool isEmpty(Hash h);
void menu();

int main() {
	menu(); 
	return 0;
}

void create_Hash(Hash& h, int b) {
	h.slot = b;
	h.table = new list<int>[h.slot];
}

int hash_func(Hash h, int x) {
	return x % h.slot;
}

bool findValue(list<int> l, int key) {
	if (l.size() == 0) return false;
	for (int x : l) {
		if (x == key) {
			return true;
		}
	}
	return false;
}

void insertItem(Hash& h, int key) {
	int hashValue = hash_func(h, key);
	list<int> l = h.table[hashValue];
	bool isKeyExist = findValue(l, key);
	if (isKeyExist) {
		cout << "** Key "<< key<<" has already existed, insert canceled **" << endl;
		return;
	}
	else {
		h.table[hashValue].emplace_back(key);
		cout << "** "<<key <<" Is inserted successful **" << endl;
	}
}

void deleteItem(Hash h, int key) {
	if (isEmpty(h)) {
		cout << "Hash table trong" << endl;
		return;
	}
	int hashValue = hash_func(h, key);
	bool isExistKey = findValue(h.table[hashValue], key);
	if (isExistKey == true) {
		h.table[hashValue].remove(key);
		cout << "Removed key " << key << endl;
		return;
	}
	else {
		cout << key << " is not exist in Hash table" << endl;
		return;
	}
}

void display_hash(Hash h) {
	if (isEmpty(h)) {
		cout << "Hash table trong" << endl;
		return;
	}
	else {
		for (int i = 0; i < h.slot; i++) {
			cout << "Hash Value: " << i << endl;
			cout << "Hash list:  ";
			if (h.table[i].size() == 0) {
				cout << "Empty";
			}
			else {
				for (int x : h.table[i]) cout << x << "  ";
			}
			cout << endl << "-----" << endl;
		}
	}
	
}
bool isEmpty(Hash h) {
	int sum = 0; 
	for (int i = 0; i < h.slot; i++) {
		sum += h.table[i].size();
	}
	return sum == 0;
}

void menu() {
	Hash h;
	create_Hash(h, hashGroup);
	while (1) {
		cout << "======================== MENU =======================" << endl;
		cout << "1. Insert item" << endl;
		cout << "2. Delete item" << endl;
		cout << "3. Display list" << endl;
		cout << "4. Exit" << endl;
		cout << "======================== END =======================" << endl;
		cout << "Lua chon cua ban la: ";
		int choose;
		do {
			cin >> choose;
			if (choose < 1 || choose >4)
			{
				cout << "Nhap lai: ";
			}
		} while (choose < 1 || choose > 4);
		switch (choose)
		{
		case 1: {
			int n;
			cout << "Nhap so luong phan tu can them vao Hash Table: ";
			do {
				cin >> n;
				if (n < 0) { 
					if (n < 0) cout << "So luong phan tu khong hop le. Nhap lai: ";
				}
			} while (n < 0);
			for (int id = 0; id < n; id++) {
				cout << "Nhap gia tri can them: ";
				int key; cin >> key;
				insertItem(h, key);
			}
			break;
		}
		case 2: {
			int n2;
			cout << "Nhap so luong phan tu can xoa trong Hash Table: ";
			do {
				cin >> n2;
				if (n2 < 0) {
					if (n2 < 0) cout << "So luong phan tu khong hop le. Nhap lai: ";
				}
			} while (n2 < 0);
			for (int id = 0; id < n2; id++) {
				cout << "Nhap gia tri can xoa: ";
				int key; cin >> key;
				deleteItem(h, key);
			}
			cout << "================ Sau khi xoa: =================" << endl;
			display_hash(h);
			break;
		}
		case 3: {
			cout << "================ HASH TABLE =================" << endl;
			display_hash(h);
			break;
		}
		case 4: {
			system("cls");
			return;
		}
		}
	} 
}