해시 자료구조(Hash Data Structure)는 데이터 검색, 삽입, 삭제 작업을 빠르게 수행할 수 있는 매우 효율적인 자료구조입니다. 많은 프로그램과 애플리케이션에서 사용되며, 특히 키-값(key-value) 쌍 데이터를 저장하고 빠르게 접근해야 하는 경우에 유용합니다. 또한 값 추가, 삭제, 조회의 시간복잡도가 O(1)이라서 코딩테스트 문제에도 많이 활용되고 있습니다.
1. 해시의 개념
해시는 키(key)와 값(value)의 쌍으로 데이터를 저장합니다. 각 키는 고유하며, 해시 함수(hash function)를 사용하여 특정 키가 저장될 위치를 결정합니다. 이 과정은 다음과 같습니다:
- 키를 입력값으로 해시 함수를 호출됩니다.
- 해시 함수는 키를 고유한 해시 값(hash value)으로 변환합니다.
- 이 해시 값을 기반으로 데이터가 저장될 인덱스(버킷)를 결정합니다.
이 방식으로 데이터를 저장하면, 키를 이용해 데이터를 빠르게 검색할 수 있습니다.
2. 해시의 원리
해시 자료구조의 주요 원리는 해시 함수와 충돌 처리입니다.
해시 함수 (Hash Function)
해시 함수는 입력 데이터를 고정된 크기의 해시 값으로 변환합니다. 해시 함수는 다음과 같은 특성을 가져야 합니다:
- 결정적: 같은 입력값은 항상 같은 해시 값을 반환해야 합니다.
- 균등 분포: 해시 값이 가능한 한 균등하게 분포되어야 합니다.
- 빠른 계산: 해시 값 계산 속도가 빨라야 합니다.
충돌 처리 (Collision Handling)
서로 다른 키가 같은 해시 값을 가질 수 있는 경우를 충돌(collision)이라고 합니다. 충돌된 경우 체이닝 또는 오픈 주소법으로 충돌을 해결합니다.
- 체이닝(Chaining): 같은 해시 값에 여러 개의 키-값 쌍을 연결 리스트로 저장합니다.
- 오픈 주소법(Open Addressing): 충돌 시 다른 빈 슬롯(배열의 다음 인덱스)을 찾아 데이터를 저장합니다.
3. 예시코드
C 언어에서의 해시 구현 예제
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
typedef struct Node {
char* key;
char* value;
struct Node* next;
} Node;
Node* hashTable[TABLE_SIZE];
unsigned int hashFunction(const char* key) {
unsigned int hash = 0;
while (*key) {
hash = (hash << 5) + *key++;
}
return hash % TABLE_SIZE;
}
void insert(const char* key, const char* value) {
unsigned int index = hashFunction(key);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = strdup(key);
newNode->value = strdup(value);
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
char* search(const char* key) {
unsigned int index = hashFunction(key);
Node* node = hashTable[index];
while (node) {
if (strcmp(node->key, key) == 0) {
return node->value;
}
node = node->next;
}
return NULL;
}
int main() {
insert("name", "Alice");
insert("age", "25");
printf("name: %s\n", search("name"));
printf("age: %s\n", search("age"));
return 0;
}C언어 STL 해시 구현 예제
#include <stdio.h>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, string> hashTable;
<em>// 데이터 삽입</em>
hashTable["name"] = "Alice";
hashTable["age"] = "25";
<em>// 데이터 검색</em>
printf("name: %s\n", hashTable["name"].c_str());
printf("age: %s\n", hashTable["age"].c_str());
return 0;
}Java에서의 해시 구현 예제
import java.util.HashMap;
public class HashExample {
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap<>();
<em>// 데이터 삽입</em>
hashMap.put("name", "Alice");
hashMap.put("age", "25");
<em>// 데이터 검색</em>
System.out.println("name: " + hashMap.get("name"));
System.out.println("age: " + hashMap.get("age"));
}
}Python에서의 해시 구현 예제
<em># Python의 dictionary 사용</em>
hash_table = {}
<em># 데이터 삽입</em>
hash_table["name"] = "Alice"
hash_table["age"] = "25"
<em># 데이터 검색</em>
print(f"name: {hash_table['name']}")
print(f"age: {hash_table['age']}")4. 해시 자료구조의 장단점
장점
- 빠른 데이터 접근: 평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있습니다.
- 다양한 응용: 캐싱, 데이터베이스 색인, 세션 관리 등 다양한 분야에서 활용됩니다.
단점
- 충돌 문제: 충돌이 발생하면 성능이 저하될 수 있습니다.
- 메모리 사용: 해시 테이블은 사전에 충분한 메모리를 할당해야 하므로 메모리 낭비가 발생할 수 있습니다.
- 정렬 불가: 데이터가 정렬되지 않은 상태로 저장되므로, 순차적인 접근이 어렵습니다.
