Hash Map & Hash Table
해시 맵(Hash Map)과 해시 테이블(Hash Table)은 모두 키-값(key-value) 쌍을 저장하는 자료구조로, 데이터를 빠르게 검색, 삽입, 삭제하기 위해 설계된 자료구조입니다. 아래에서는 각각의 정의, 구현, 예시 코드, 장단점을 설명하고, 활용 및 충돌 해결 방법을 통합적으로 정리합니다.
1. 정의
Hash Map
해시 맵은 동기화(Synchronization)를 지원하지 않으며, 멀티스레드 환경에서 동기화 작업이 필요합니다. 현대 프로그래밍 언어(JavaScript, Python, Java 등)에서 일반적으로 사용되며, 단일 스레드 환경에서 매우 빠른 속도를 제공합니다.
Hash Table
해시 테이블은 동기화(Synchronization)를 지원하므로 멀티스레드 환경에서 안전하게 사용할 수 있습니다. 초기 자료구조 설계 및 저수준 언어(C, C++)에서 많이 사용되며, 동기화를 지원하기 때문에 성능은 해시 맵에 비해 다소 느릴 수 있습니다.
2. 구현
Hash Map
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
typedef struct HashNode {
char* key;
int value;
struct HashNode* next;
} HashNode;
typedef struct {
HashNode* table[TABLE_SIZE];
} HashMap;
unsigned int hash(char* key) {
unsigned int hash = 0;
while (*key) {
hash = (hash << 5) + *key++;
}
return hash % TABLE_SIZE;
}
HashMap* createHashMap() {
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
for (int i = 0; i < TABLE_SIZE; i++) {
map->table[i] = NULL;
}
return map;
}
void insert(HashMap* map, char* key, int value) {
unsigned int index = hash(key);
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = strdup(key);
newNode->value = value;
newNode->next = map->table[index];
map->table[index] = newNode;
}
int search(HashMap* map, char* key) {
unsigned int index = hash(key);
HashNode* node = map->table[index];
while (node != NULL) {
if (strcmp(node->key, key) == 0) {
return node->value;
}
node = node->next;
}
return -1;
}
void freeHashMap(HashMap* map) {
for (int i = 0; i < TABLE_SIZE; i++) {
HashNode* node = map->table[i];
while (node) {
HashNode* temp = node;
node = node->next;
free(temp->key);
free(temp);
}
}
free(map);
}Hash Table
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
// 해시 테이블의 노드 구조체 정의
typedef struct HashNode {
char* key; // 키
int value; // 값
struct HashNode* next; // 다음 노드 (체이닝을 위한 연결 리스트)
} HashNode;
// 해시 테이블 구조체 정의
typedef struct {
HashNode* table[TABLE_SIZE]; // 노드 배열
} HashTable;
// 해시 함수
unsigned int hash(const char* key) {
unsigned int hash = 0;
while (*key) {
hash = (hash << 5) + *key++; // 해시 값 계산
}
return hash % TABLE_SIZE;
}
// 해시 테이블 초기화
HashTable* createHashTable() {
HashTable* table = (HashTable*)malloc(sizeof(HashTable));
for (int i = 0; i < TABLE_SIZE; i++) {
table->table[i] = NULL; // 모든 인덱스를 NULL로 초기화
}
return table;
}
// 해시 테이블에 데이터 삽입
void insert(HashTable* table, const char* key, int value) {
unsigned int index = hash(key); // 해시 함수로 인덱스 계산
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = strdup(key); // 키 복사
newNode->value = value; // 값 저장
newNode->next = table->table[index]; // 체이닝 연결
table->table[index] = newNode; // 새로운 노드를 리스트의 첫 번째에 삽입
}
// 해시 테이블에서 데이터 검색
int search(HashTable* table, const char* key) {
unsigned int index = hash(key); // 해시 함수로 인덱스 계산
HashNode* node = table->table[index]; // 해당 인덱스의 노드 가져오기
while (node != NULL) {
if (strcmp(node->key, key) == 0) {
return node->value; // 키가 일치하면 값 반환
}
node = node->next; // 다음 노드로 이동
}
return -1; // 키를 찾지 못한 경우
}
// 해시 테이블에서 노드 삭제
void delete(HashTable* table, const char* key) {
unsigned int index = hash(key); // 해시 함수로 인덱스 계산
HashNode* node = table->table[index];
HashNode* prev = NULL;
while (node != NULL && strcmp(node->key, key) != 0) {
prev = node;
node = node->next;
}
if (node == NULL) {
printf("Key not found: %s\n", key);
return;
}
if (prev == NULL) {
table->table[index] = node->next; // 첫 번째 노드를 삭제
} else {
prev->next = node->next; // 중간 노드를 삭제
}
free(node->key); // 메모리 해제
free(node);
printf("Key deleted: %s\n", key);
}
// 해시 테이블 메모리 해제
void freeHashTable(HashTable* table) {
for (int i = 0; i < TABLE_SIZE; i++) {
HashNode* node = table->table[i];
while (node != NULL) {
HashNode* temp = node;
node = node->next;
free(temp->key);
free(temp);
}
}
free(table);
}
// 메인 함수
int main() {
HashTable* table = createHashTable();
// 데이터 삽입
insert(table, "apple", 1);
insert(table, "banana", 2);
insert(table, "grape", 3);
// 데이터 검색
printf("Search apple: %d\n", search(table, "apple"));
printf("Search banana: %d\n", search(table, "banana"));
printf("Search orange: %d\n", search(table, "orange")); // 없는 키 검색
// 데이터 삭제
delete(table, "banana");
printf("Search banana after deletion: %d\n", search(table, "banana"));
// 해시 테이블 메모리 해제
freeHashTable(table);
return 0;
}3. 장단점
| 특징 | Hash Map | Hash Table |
|---|---|---|
| 동기화 | 지원하지 않음(Thread-safe X) | 지원(Thread-safe O) |
| 멀티스레드환경 | 멀티스레드 환경에서 별도의 동기화 필요. | 멀티스레드 환경에서 바로 사용 가능. |
| 사용환경 | 현대 프로그래밍 언어에서 일반적으로 사용됨. | 초기 자료구조 설계에서 많이 사용됨. |
| 성능 | 동기화가 없어서 단일 스레드 환경에서 더 빠름. | 동기화로 인해 약간 느릴 수 있음. |
해시 맵과 해시 테이블의 공통점
-
키-값 기반 저장:
두 자료구조 모두 키-값 쌍을 저장하며, 키를 사용하여 값을 빠르게 검색할 수 있습니다. -
충돌 처리 필요:
동일한 해시 값을 가진 키가 있을 경우 충돌이 발생하며, 이를 해결하기 위해 체이닝(Chaining) 또는 오픈 어드레싱(Open Addressing)을 사용합니다. -
빠른 데이터 접근:
평균적으로 의 검색, 삽입, 삭제 속도를 제공합니다.
해시 맵과 해시 테이블의 차이점
-
용어적 차이:
해시 맵(Hash Map)은 보통 언어 구현에서 특정 용어로 사용됩니다(Java의 HashMap, Python의 dict). 반면, 해시 테이블은 자료구조의 일반적인 개념을 뜻합니다. -
메모리 사용 방식:
해시 맵은 동적으로 크기를 조정하면서 데이터를 관리하는 경향이 있지만, 해시 테이블은 고정된 크기(TABLE_SIZE)의 배열 기반으로 구현되기도 합니다. -
언어별 구현 차이:
예를 들어, JavaScript에서는 객체가 사실상 해시 테이블로 동작합니다. 반면, Java의 HashMap은 체이닝을 이용하여 충돌을 처리합니다.
4. 활용
- 비밀번호 저장 및 인증
해시 테이블과 해시 맵은 비밀번호 저장 및 인증 시스템에서 널리 사용됩니다. 비밀번호를 저장할 때 원본 비밀번호를 직접 저장하지 않고, 해시 함수를 사용하여 암호화된 형태로 저장합니다. 이를 통해 보안성을 강화할 수 있습니다.
-
과정:
- 사용자가 비밀번호를 설정하면, 이를 해시 함수에 입력하여 해시 값을 생성합니다.
- 생성된 해시 값을 데이터베이스에 저장합니다.
- 사용자가 비밀번호를 입력하면 동일한 해시 함수로 해시 값을 생성하여 데이터베이스의 값과 비교합니다.
- 해시 값이 일치하면 인증이 완료됩니다.
-
추가적인 보안 기술:
- 솔트(Salt): 해시 함수에 고유 값을 추가하여 동일한 비밀번호라도 서로 다른 해시 값을 생성하도록 합니다. 이는 무차별 대입 공격(Brute Force) 및 무작위 공격(Rainbow Table Attack)을 방지합니다.
- 키 스트레칭(Key Stretching): 계산 복잡도를 늘려 공격자가 해시 값을 역추적하는 데 더 많은 시간이 걸리도록 합니다. 예: PBKDF2, bcrypt, Argon2 등.
-
데이터베이스 인덱싱
키를 통해 데이터를 빠르게 검색할 수 있는 환경에서 사용됩니다. -
캐싱 시스템
자주 조회되는 데이터를 저장하고 빠르게 접근할 수 있도록 하는 캐시 시스템에 적합합니다. -
집합 연산
중복 없는 데이터 저장, 유일한 키-값 쌍 관리 등에서 활용됩니다. -
네트워크 라우팅
라우터에서 패킷을 목적지 IP 주소로 라우팅할 때, 해시 테이블을 사용하여 경로 정보를 저장하고 검색합니다. 이를 통해 패킷 전달의 효율성을 높입니다. -
이미지 및 데이터 무결성 검증
파일이나 이미지가 전송 중 변조되지 않았는지 확인하는 데 해시 함수가 사용됩니다. 원본 데이터의 해시 값을 생성하고, 이후 데이터를 전송받아 동일한 해시 값을 다시 계산하여 무결성을 검증합니다.
5. 충돌 해결 방법
1. 체이닝 (Chaining)
충돌이 발생한 인덱스에 연결 리스트를 사용하여 데이터를 저장합니다.
연결 리스트를 이용하므로, 충돌이 발생해도 데이터를 계속 삽입할 수 있습니다.
장점: 구현이 간단하며, 충돌 발생 시에도 메모리 사용량만 늘어납니다.
단점: 충돌이 많아질 경우 검색 시간이 O(n)으로 증가할 수 있습니다.
2. 개방 주소법 (Open Addressing)
충돌이 발생하면 다른 빈 공간을 찾아 데이터를 삽입합니다.
빈 공간 탐색 방법에는 선형 탐사, 제곱 탐사, 이중 해싱 등이 있습니다.
-
선형 탐사: 충돌 발생 시 인덱스를 하나씩 증가시키며 빈 공간을 찾습니다.
- (충돌이 발생한 여러 데이터가 몰려 저장되는 데이터 군집화(clustering) 현상이 나타날 수 있습니다.)
-
제곱 탐사: 충돌 발생 시 증가폭을 제곱수로 하여 빈 공간을 찾습니다.
-
이중 해싱: 두 번째 해시 함수를 사용하여 충돌을 해결합니다.
장점: 연결 리스트를 사용하지 않아 메모리 사용량이 적습니다.
단점: 충돌이 많아질 경우 검색 성능이 저하될 수 있습니다.
