[자료구조 & 알고리즘] 해시 테이블(Hash Table)

오랜만에 자료구조 시간이 돌아왔습니다. ㅎㅎㅎ

영어가 가능하신 분들께서는 해당 포스트 참고하시면 도움이 많이 될 것 같습니다!

학습 자료 & 이미지 (GIF 출처): https://junminlee3.medium.com/hash-tables-animations-that-will-make-you-understand-how-they-work-d1bcc850ba71

Hash Tables — animations that will make you understand how they work

Hello, today we’re going to talk about things like how hash tables work, and about hash functions, collisions etc. After knowing how hash…

junminlee3.medium.com

학습자료:

허니C코디 강사님의 유튜브

https://www.youtube.com/watch?v=mp8U9S57Aps

BaaarkingDog님의 유튜브 및 블로그

https://www.youtube.com/watch?v=1-k-D2AYY0I&t=1083s

해시 테이블(Hash Table):

데이터를 빠르고 효율적으로 탐색하고자 할 때 가장 널리 사용되는 자료구조 중 하나가 바로 **해시 테이블(Hash Table)**입니다. 이번 포스트에서는 해시 테이블의 개념과 기법, 그리고 주요 특징에 대해 알아보겠습니다.

1. 해시 테이블의 정의와 등장 배경

1-1. 해시 테이블의 정의

해시 테이블은 데이터를 키(Key)-값(Value) 형태로 저장하는 자료구조입니다.
특정 데이터를 찾기 위해 매번 처음부터 끝까지 탐색하는 대신, 해시 함수(Hash Function)를 사용하여 키를 해시 값으로 변환하고 이를 배열의 인덱스로 사용해 빠르게 데이터를 조회할 수 있습니다.

1-2. 등장 배경

기존의 자료구조(예: 배열, 연결 리스트)는 데이터가 많아질수록 탐색 시간이 길어지는 문제가 있었습니다. 특히 대용량 데이터의 효율적인 관리가 중요해지면서 평균 O(1)의 탐색 속도를 제공하는 해시 테이블이 등장하게 되었습니다. 하단의 자료를 통해 자세히 설명하겠습니다.

기존 브루트 포스 방법으로 배열에서 "RANDY"라는 이름을 찾기 위해서는 배열의 시작부터 하나씩 배열의 변수와 RANDY를 비교하는 과정이 필요합니다.

하지만 배열이 크기가 크다면 그 만큼 걸리는 시간 오래걸리게 됩니다. 즉 기존의 부르트포스 방법으로 값을 찾고자 한다면 O(N)의 의 탐색 속도를 갖게 되겠지요.

해시 테이블은 O(n)의 시간복잡도를 O(1)으로 해결할 수 있는 효과적인 방법입니다.

해싱(Hashing)이라는 특별한 과정을 거쳐, 키를 고유한 해시 값으로 바꾸어 배열에 저장하게 됩니다.

다시말하면, 우리가 저장해야 하는 키를 변수의 크기, 모듈러 연산 등등 적합한 방법 연산하여 인덱스를 뽑아내어, 해시 배열에 해당 인덱스에 값을 저장하는 방식입니다.

2. 해시 테이블의 주요 개념

2-1. 해싱(Hashing)

해싱은 키를 고유한 해시 값으로 변환하는 과정입니다. 해시 함수는 입력된 키에 따라 특정 범위의 숫자를 반환하며, 이 값이 해시 테이블의 인덱스로 사용됩니다.
예시:

hash("name") → 5

좋은 해시 함수의 조건은 다음과 같습니다.

충돌 최소화: 서로 다른 키들이 같은 해시 값을 갖지 않도록 설계
균등 분포: 해시 값이 특정 범위에 편중되지 않고 고르게 분포될 것
계산 속도: 빠르게 계산이 가능할 것

2-2. 부하율(Load Factor)

부하율은 해시 테이블이 얼마나 채워져 있는지를 나타내는 지표로, 다음과 같이 계산합니다.

부하율 = (저장된 요소 개수) / (해시 테이블의 크기)

부하율이 높아지면 충돌이 증가하여 탐색 성능이 저하될 수 있습니다. 일반적으로 부하율이 0.7을 넘지 않도록 관리하며, 이를 초과할 경우 테이블의 크기를 늘리는 리해싱(Rehashing) 작업을 수행합니다.

3. 해시 히트(Hash Hit)와 해시 미스(Hash Miss)

3.1. 해시 히트(Hash Hit)란?

해시 히트는 해시 테이블에서 탐색하려는 키가 테이블에 존재하여, 해시 함수가 반환한 인덱스에서 곧바로 값을 찾는 경우를 의미합니다.
즉, 키에 대한 값이 성공적으로 발견될 때 발생하는 이벤트입니다.
탐색 시간 복잡도: 평균적으로 O(1)

예시 코드:

unsigned int hash(const char* key);
char* search(const char* key) {
    unsigned int index = hash(key);
    Node* current = hash_table[index];

    // Hash Hit: 찾으려는 키가 존재하는 경우
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;  // Hash Hit 발생
        }
        current = current->next;
    }
    return NULL;  // Hash Miss 발생
}

3.2. 해시 미스(Hash Miss)란?

해시 미스는 탐색하려는 키가 해시 테이블에 존재하지 않는 경우를 말합니다.
해시 함수가 반환한 인덱스를 탐색했지만, 해당 인덱스에 키가 없거나 다른 키만 있을 때 발생합니다.

3.3. 해시 히트율(Hash Hit Rate)

해시 히트율은 전체 탐색 시도 중에서 해시 히트가 발생한 비율을 의미합니다.
공식: Hit Rate=Hash Hit 발생 횟수전체 탐색 시도 횟수\text{Hit Rate} = \frac{\text{Hash Hit 발생 횟수}}{\text{전체 탐색 시도 횟수}}

해시 히트율이 높을수록 해시 테이블의 효율성이 좋다고 할 수 있습니다. 일반적으로 해시 히트율은 해시 함수의 성능과 테이블 크기, 부하율(Load Factor)에 영향을 받습니다.

3.4. 해시 히트의 중요성

빠른 데이터 접근: 해시 테이블의 주요 장점은 평균적으로 **O(1)**의 시간 복잡도로 데이터에 접근하는 것입니다.
충돌 해결 기법의 영향: 충돌이 많이 발생하면 해시 히트율이 감소하고 탐색 시간이 길어질 수 있습니다. 따라서, 적절한 충돌 해결 방법을 선택하는 것이 중요합니다.

3.5. 해시 히트와 캐시(Cache)

해시 히트와 비슷한 개념이 캐시(Cache)**에서의 캐시 히트(Cache Hit)입니다.

캐시에서도 필요한 데이터가 캐시에 존재할 때 캐시 히트가 발생하며, 캐시 효율을 측정하는 중요한 지표가 됩니다.
캐시 히트율 = 캐시에서 성공적으로 데이터를 찾은 비율입니다.

4. 해시 충돌(Hash Collision)

해시 충돌은 **두 개 이상의 서로 다른 키가 동일한 해시 값(Hash Value)**을 반환하는 현상을 말합니다. 해시 함수가 고유한 해시 값을 반환하지 못할 때 발생하며, 이는 해시 테이블의 성능에 큰 영향을 미칠 수 있습니다.

4.1. 해시 충돌의 원인

유한한 해시 테이블 크기
- 해시 테이블의 크기는 제한적이므로, 여러 키가 같은 인덱스로 매핑될 가능성이 있습니다.
해시 함수의 품질
- 해시 함수가 고르게 분포하지 못하면 특정 인덱스에 데이터가 몰리게 됩니다.
데이터 양 증가
- 테이블이 가득 차거나 부하율(Load Factor)이 높아지면 충돌 발생 확률이 높아집니다.

4.2. 해시 충돌의 예시

예를 들어, RANDY와 ERIC이 해싱 과정을 거쳐 같은 인덱스 값 4를 같게 된다면, 해시 배열 인덱스 4에는 RANDY와 ERIC이 둘다 들어가야하는 해시 충돌이 발생하게 됩니다. 하단은 C 코드 예시 입니다.

#include <stdio.h>
#include <string.h>

#define TABLE_SIZE 5

unsigned int simple_hash(const char* key) {
    return key[0] % TABLE_SIZE;  // 키의 첫 번째 문자를 기반으로 해시 값 생성
}

int main() {
    printf("Hash('apple'): %d\n", simple_hash("apple"));
    printf("Hash('ant'): %d\n", simple_hash("ant"));  // 충돌 발생!
    return 0;
}

출력:

Hash('apple'): 2  
Hash('ant'): 2  → 충돌 발생

두 키 'apple'과 'ant'가 동일한 해시 값 2를 반환하며 충돌이 발생합니다.

5. 해시 충돌 해결 방법 (체이닝, 오픈 주소)

해시 충돌을 해결할 때 크게 두 가지 방법이 있습니다. 체이닝과(Seperate Chaing)과 개방 주소(Open Addressing) 방법이 있는데, 상황에 따라 적합한 방법을 선택해야합니다.

5.1 체이닝(Separate Chaining)

설명: 충돌이 발생한 경우, 같은 인덱스에 연결 리스트(Linked List) 형태로 여러 데이터를 저장하는 방법입니다.
장점: 충돌이 많아도 쉽게 관리 가능
단점: 연결리스트로 인한 메모리 사용량 증가

체이닝 구현 예시 (C 코드):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

typedef struct Node {
    char key[50];
    char value[50];
    struct Node* next;
} Node;

Node* hash_table[TABLE_SIZE];

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

void insert(const char* key, const char* value) {
    unsigned int index = hash(key);
    Node* new_node = (Node*)malloc(sizeof(Node));
    strcpy(new_node->key, key);
    strcpy(new_node->value, value);
    new_node->next = hash_table[index];
    hash_table[index] = new_node;
}

char* search(const char* key) {
    unsigned int index = hash(key);
    Node* current = hash_table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return NULL;
}

int main() {
    insert("name", "DaeHyun Kim");
    insert("age", "25");

    printf("name: %s\n", search("name"));
    printf("age: %s\n", search("age"));

    return 0;
}

5.2 개방 주소법(Open Addressing)

설명: 충돌이 발생하면 빈 공간을 탐색하여 데이터를 저장하는 방법입니다.
장점: 메모리 사용이 효율적
단점: 클러스터링 발생 증가, 탐색 시간 증가

> 클러스터링이란 충돌이 발생하여 데이터가 특정 인덱스 근처에 밀집되는 현상을 의미합니다.

빈 공간을 탐색하는 것을 프로브(Probe)한다고 표현하며, 대표적으로 3개지 방법이 있습니다.

1. 선형 탐사 (Linear Probing)

충돌 발생 시 인덱스를 1씩 증가시키며 빈 공간을 탐색합니다.
예: (index + 1) % TABLE_SIZE

2. 이차 탐사 (Quadratic Probing)

충돌 발생 시 제곱 단위로 증가하며 탐색합니다.
예: (index + i²) % TABLE_SIZE

3. 이중 해싱 (Double Hashing)

두 개의 해시 함수를 사용하여 인덱스를 탐색합니다.예: index = (hash1(key) + i * hash2(key)) % TABLE_SIZE

즉 해싱 함수로 계산된 인덱스에 이미 값이 존재 한다면 바로 옆이든, 제곱 수 이후던, 빈 공간을 찾아 저장을 해놓는 방법입니다.

개방 주소법 구현 예시 (C 코드):

#include <stdio.h>
#include <string.h>

#define TABLE_SIZE 10

typedef struct {
    char key[50];
    char value[50];
    int is_occupied;
} Entry;

Entry hash_table[TABLE_SIZE];

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

void insert(const char* key, const char* value) {
    unsigned int index = hash(key);
    while (hash_table[index].is_occupied) {
        index = (index + 1) % TABLE_SIZE;
    }
    strcpy(hash_table[index].key, key);
    strcpy(hash_table[index].value, value);
    hash_table[index].is_occupied = 1;
}

char* search(const char* key) {
    unsigned int index = hash(key);
    unsigned int start_index = index;

    while (hash_table[index].is_occupied) {
        if (strcmp(hash_table[index].key, key) == 0) {
            return hash_table[index].value;
        }
        index = (index + 1) % TABLE_SIZE;
        if (index == start_index) break;
    }
    return NULL;
}

int main() {
    insert("name", "DaeHyun Kim");
    insert("age", "25");

    printf("name: %s\n", search("name"));
    printf("age: %s\n", search("age"));

    return 0;
}

5.3 체이닝과 개방 주소법 비교 (O 표기법)

체이닝 시간 복잡도

연산 평균 시간 복잡도 최악의 시간 복잡도

탐색(Search)	O(1)	O(n)
삽입(Insert)	O(1)	O(n)
삭제(Delete)	O(1)	O(n)

평균 경우:
- 해시 함수가 데이터를 균등하게 분포시키면, 각 인덱스에 저장된 리스트 길이가 짧아 탐색이 빠릅니다. (평균적으로 O(1))
- 부하율(Load Factor, α = 저장된 항목 수 / 해시 테이블 크기)이 클수록 시간 복잡도가 증가합니다.
최악의 경우:
- 모든 키가 동일한 해시 값을 가질 경우, 하나의 인덱스에 데이터가 모두 몰리게 되어 O(n)의 탐색 시간이 걸립니다.

체이닝 공간 복잡도

공간 복잡도: O(n + m)
- n: 저장된 요소의 수
- m: 해시 테이블의 크기
- 연결 리스트에 추가적인 노드가 필요하므로, 메모리 사용량이 증가합니다. (각 노드에 추가 포인터 필요)

개방 주소법 시간 복잡도

연산 평균 시간 복잡도 최악의 시간 복잡도

탐색(Search)	O(1)	O(n)
삽입(Insert)	O(1)	O(n)
삭제(Delete)	O(1)	O(n)

평균 경우:
- 데이터가 테이블에 균등하게 분포되면, 평균적으로 O(1)의 탐색 시간이 소요됩니다.
- 부하율(Load Factor)이 커질수록 충돌이 많아지고 탐사 횟수가 증가하여 성능이 저하될 수 있습니다.
최악의 경우:
- 빈 공간을 찾기 위해 테이블 전체를 탐색해야 할 수 있습니다. 특히 클러스터링(Clustering) 문제가 발생하면 O(n)까지 시간 복잡도가 증가합니다.

개방 주소법 공간 복잡도

공간 복잡도: O(m)
- m: 해시 테이블의 크기
- 추가 메모리 없이 해시 테이블 내의 빈 공간을 활용하므로, 메모리 사용이 효율적입니다.

체이닝과 개방 주소법 비교 요약 (시간/공간 복잡도)

기법 시간 복잡도 (평균) 시간 복잡도 (최악) 공간 복잡도 장점 단점

체이닝	O(1)	O(n)	O(n + m)	충돌이 많아도 관리가 용이	연결 리스트로 인한 메모리 추가 필요
개방 주소법	O(1)	O(n)	O(m)	메모리 사용이 효율적	클러스터링 발생 가능, 탐색 시간 증가

상황에 따라 충돌 회피 기법을 적절하게 사용할 수 있어야하는데 메모리가 충분하거나 충돌이 자주 발생할 것으로 예상될 경우 체이닝을 선택해야하며, 메모리를 절약해야하거나 부하율이 낮고, 데이터가 균등하게 분포할 것으로 예상될 경우에는 개방 주소법을 사용하면 됩니다.

체이닝을 선택할 때

추가 메모리 사용이 가능하고, 부하율이 높아질 가능성이 있는 경우
충돌이 자주 발생할 것으로 예상되는 경우

개방 주소법을 선택할 때

메모리를 절약하고자 하는 경우
부하율이 낮고, 데이터가 균등하게 분포할 것으로 예상되는 경우

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.

'Computer Science > 자료구조 & 알고리즘' 카테고리의 다른 글

[자료구조 & 알고리즘] 이분 탐색 (Binary Search) (0)	2025.02.03
[자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm) (0)	2025.02.02
[자료구조 & 알고리즘] DP 추천 문제 및 유형 분류 (feat. 백준) (1)	2025.01.30
[자료구조 & 알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 이해하기 (0)	2025.01.14
[알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성) (0)	2025.01.09

rnasterofmysea

[자료구조 & 알고리즘] 해시 테이블(Hash Table)

해시 테이블(Hash Table):

1. 해시 테이블의 정의와 등장 배경

1-1. 해시 테이블의 정의

1-2. 등장 배경

2. 해시 테이블의 주요 개념

2-1. 해싱(Hashing)

2-2. 부하율(Load Factor)

3. 해시 히트(Hash Hit)와 해시 미스(Hash Miss)

3.1. 해시 히트(Hash Hit)란?

3.2. 해시 미스(Hash Miss)란?

3.3. 해시 히트율(Hash Hit Rate)

3.4. 해시 히트의 중요성

3.5. 해시 히트와 캐시(Cache)

4. 해시 충돌(Hash Collision)

4.1. 해시 충돌의 원인

4.2. 해시 충돌의 예시

5. 해시 충돌 해결 방법 (체이닝, 오픈 주소)

5.1 체이닝(Separate Chaining)

5.2 개방 주소법(Open Addressing)

5.3 체이닝과 개방 주소법 비교 (O 표기법)

체이닝 시간 복잡도

체이닝 공간 복잡도

개방 주소법 시간 복잡도

개방 주소법 공간 복잡도

체이닝과 개방 주소법 비교 요약 (시간/공간 복잡도)

'Computer Science > 자료구조 & 알고리즘' 카테고리의 다른 글

티스토리툴바

[자료구조 & 알고리즘] 해시 테이블(Hash Table)

해시 테이블(Hash Table):

1. 해시 테이블의 정의와 등장 배경

1-1. 해시 테이블의 정의

1-2. 등장 배경

2. 해시 테이블의 주요 개념

2-1. 해싱(Hashing)

2-2. 부하율(Load Factor)

3. 해시 히트(Hash Hit)와 해시 미스(Hash Miss)

3.1. 해시 히트(Hash Hit)란?

3.2. 해시 미스(Hash Miss)란?

3.3. 해시 히트율(Hash Hit Rate)

3.4. 해시 히트의 중요성

3.5. 해시 히트와 캐시(Cache)

4. 해시 충돌(Hash Collision)

4.1. 해시 충돌의 원인

4.2. 해시 충돌의 예시

5. 해시 충돌 해결 방법 (체이닝, 오픈 주소)

5.1 체이닝(Separate Chaining)

5.2 개방 주소법(Open Addressing)

5.3 체이닝과 개방 주소법 비교 (O 표기법)

체이닝 시간 복잡도

체이닝 공간 복잡도

개방 주소법 시간 복잡도

개방 주소법 공간 복잡도

체이닝과 개방 주소법 비교 요약 (시간/공간 복잡도)

'Computer Science > 자료구조 & 알고리즘' 카테고리의 다른 글

관련글

티스토리툴바