[자료구조] 해시 테이블 (Hash Table)

해시 테이블 (Hash Table) 란?

• 키-값 쌍을 빠르게 삽입, 조회, 제거하는 데 사용되는 데이터 구조

 

장단점

장점

• 평균적으로 O(1)의 시간에 검색, 삽입, 삭제가 가능해 빠름.
• 큰 데이터를 관리하기에 유리하며, 중복 데이터 방지에 유용.

단점

• 충돌 발생 시 성능이 저하될 수 있음.
• 해시 함수에 따라 성능이 달라질 수 있으며, 메모리 효율성이 떨어질 수 있음.

구현

vector를 사용한 구현

#include <iostream>
#include <vector>
#include <algorithm>

class HashTable
{
private:
	int BUCKET;
	std::vector<std::vector<int> > table;
	
public:
	HashTable(int b) {
		this->BUCKET = b;
		table.resize(BUCKET);
	}
	~HashTable() {};

	// 유일한 인덱스로 매핑하는 역할
	int hashFunction(int x) {
		return (x % BUCKET);
	}

	void insertItem(int key) {
		int index = hashFunction(key);
		table[index].push_back(key); // Chaining 방식
	}

	void deleteItem(int key) {
		int index = hashFunction(key);

		auto it = std::find(table[index].begin(), table[index].end(), key);
		if (it != table[index].end()) {
			table[index].erase(it);
		}
	}

	void displayHashTable() {
		for (int i = 0; i < BUCKET; i++) {
			std::cout << i;
			for (int it : table[i]) {
				std::cout << " --> " << it;
			}
			std::cout << std::endl;
		}
	}
};

int main() {

	std::vector<int> a = {15, 11, 27, 8, 12};

	HashTable h(7);
	for (int key : a)
		h.insertItem(key); // hashTable에 값 저장

	// hashTable에서 12 삭제
	h.deleteItem(12);

	// 전체 출력
	h.displayHashTable();
	return 0;
}

 

output

0
1 --> 15 --> 8
2
3
4 --> 11
5
6 --> 27

• key를 바탕으로 value를 찾을 수 있기때문에 보다 빠르게 O(1) ~ O(n) 정도로 value를 찾는것이 가능하다.

참고자료

https://www.geeksforgeeks.org/hash-table-data-structure/