TIL 2025 04 11 CS50 / 해시테이블

목차

1. 해시 테이블 (Hash Table)
2. 해시 함수의 개념과 구현 방법
3. 해시 테이블 구조와 작동 원리
4. 해시 충돌과 해결 방법
5. 해시 테이블의 시간 복잡도

 

---

1. 해시 테이블 (Hash Table)

데이터를 해시 함수를 통해 적절한 위치(버킷)에 저장함으로써, 빠른 데이터 검색을 가능하게 하는 자료 구조.

일반적으로 검색, 삽입, 삭제를 평균 O(1)의 시간 복잡도로 처리 가능.

 

 

• 전통적인 배열, 연결 리스트, 트리와 달리 해시 테이블은 key를 통해 직접 접근 가능
  => (다만, 해시 함수의 품질과 충돌 해결 방식에 따라 성능 차이 발생)
  
• 기본 개념은 "해시 함수로 키를 변환 => 배열 인덱스로 사용 => 해당 인덱스에 값을 저장"
• 예를 들어 "apple"이라는 값을 저장한다고 할 때, 이 값을 숫자로 변환하고 특정 크기의 배열의 인덱스로 매핑하여 저장.

 

---

 

2. 해시 함수의 개념과 구현 방법

 

해시 함수(hash function)는 데이터를 일정한 범위 내의 숫자(배열의 인덱스)로 변환하는 함수.

 

2-1. 첫 글자의 ASCII 값 활용

int hash(const char *key) {
    return key[0] % 26; // A~Z에 해당하는 26칸 배열
}

 

2-2. 다항 해싱

int hash(const char *key) {
    int hash_value = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hash_value = (hash_value * 31 + key[i]) % TABLE_SIZE;
    }
    return hash_value;
}

• 다항 해싱은 충돌 확률을 낮추는 데 더 효과적이며, 다양한 키에 대해 고르게 분산된 인덱스를 생성 가능.

 

 

---

 

3. 해시 테이블 구조와 작동 원리

 

해시 테이블은 일반적으로 배열 + 연결 리스트(또는 다른 구조로 구성됨.

• 배열의 각 칸은 버킷(bucket) 또는 슬롯(slot)이라 불림
• 각 버킷에는 해당 인덱스에 충돌한 값을 저장하기 위한 연결 리스트 또는 다른 구조가 연결됨

 

3-1. 저장 흐름

1. "banana" → 해시 함수 → 인덱스 2 도출
2. 배열[2]에 "banana" 연결 리스트에 삽입

 

3-2. 예시

#define SIZE 26

node *table[SIZE]; // A부터 Z까지

int hash(char *name) {
    return toupper(name[0]) - 'A';
}

void insert(char *name) {
    int index = hash(name);
    node *n = malloc(sizeof(node));
    strcpy(n->name, name);
    n->next = table[index];
    table[index] = n;
}

• 이름을 저장한다고 가정할 때, 해시 함수로 이름의 첫 글자의 ASCII 값을 활용한다고 하면 'A'는 65번 버킷, 'B'는 66번 버킷 등으로 분류 가능

 이 코드는 첫 글자를 기준으로 해당 버킷에 연결 리스트로 노드를 추가하여, 중복 없이 빠른 검색 가능.

 

---

 

4. 해시 충돌과 해결 방법

 

충돌(collision): 서로 다른 키가 동일한 해시 값을 가질 때 발생.

 

 

4-1. 충돌 해결 기법

1. 체이닝(Chaining): 같은 해시 값을 갖는 항목들을 연결 리스트로 저장 (가장 많이 사용)
2. 오픈 어드레싱(Open Addressing): 빈 공간을 찾아 다른 위치에 저장 (선형 탐사, 이차 탐사 등)

 

4-2. 체이닝 (Chaining)

// 테이블 내 각 인덱스는 연결 리스트의 시작을 가리킴
node *table[SIZE];

// 각 노드는 다음 노드를 가리키며 연결됨
struct node {
    char name[20];
    struct node *next;
};

• 예: 'Amy'와 'Alan' 모두 같은 해시 값을 가질 경우, 해당 버킷에 연결 리스트 형태로 차례대로 저장
• 검색 시에도 해당 리스트를 순회하며 일치 여부 판단

 

 

---

5. 해시 테이블의 시간 복잡도

 

• 평균적으로 충돌이 적은 이상적인 해시 함수를 사용하면 O(1)에 가까운 성능 기대 가능
• 최악의 경우 모든 키가 한 버킷에 몰리면 연결 리스트 탐색으로 인해 O(n) 소요

 

---

정리

• 해시 테이블은 키 기반 데이터 검색에 매우 효율적인 자료 구조이며, 잘 설계된 해시 함수를 통해 대부분의 연산을 O(1)로 처리 가능
• 충돌 가능성이 존재하지만 체이닝 등의 기법으로 해결 가능
• 해시 함수 설계는 해시 테이블 성능의 핵심이며, 충돌이 적도록 균등하게 분산되도록 구성 필요