해시테이블(HashTable)

해시테이블은 큰 범위를 가진 각양각색의 데이터들을 해싱을 통해 한정된 범위의 정수값을 가진 해시로 만들고, 해시라는 키에 대응하여 원본 데이터들을 매핑시켜 놓은 테이블입니다.

 

해시 (Hash)

다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값

예시:
"Alice" → 해시함수 → 3
"Bob" → 해시함수 → 7  
"Charlie" → 해시함수 → 1
"David" → 해시함수 → 5

다양한 길이의 문자열 → 고정된 범위의 정수 (0~9)

 

 

해싱 (Hashing)

임의의 데이터를 해시로 바꿔주는 일이며, 해시 함수가 이를 담당합니다.

 

해시 함수 (Hash Function)

임의의 데이터를 입력으로 받아 일정한 길이의 데이터로 바꿔주는 함수

// 간단한 해시 함수 예시
public class SimpleHashFunction
{
    public static int HashString(string input, int tableSize)
    {
        int hash = 0;
        foreach (char c in input)
        {
            hash = (hash + c) % tableSize;
        }
        return hash;
    }
    
    // 사용 예시
    public static void Example()
    {
        int tableSize = 10;
        
        Console.WriteLine($"Alice → {HashString("Alice", tableSize)}");   // 3
        Console.WriteLine($"Bob → {HashString("Bob", tableSize)}");       // 7
        Console.WriteLine($"Charlie → {HashString("Charlie", tableSize)}"); // 1
    }
}

 

 

 

해시테이블 구조

해시테이블 구조:
Index   Data
  0   → [     ]
  1   → [Charlie, 25]
  2   → [     ]
  3   → [Alice, 30]
  4   → [     ]
  5   → [David, 28]
  6   → [     ]
  7   → [Bob, 35]
  8   → [     ]
  9   → [     ]

키 "Alice" → 해시값 3 → 인덱스 3에 저장

 

 

시간복잡도 특성

해시테이블은 최악의 시간복잡도와 평균 시간복잡도 차이가 크며, 이를 고려해서 사용 여부를 결정해야 합니다.

 

평균 시간복잡도

충돌이 적고 해시 함수가 잘 분산될 때

• 참조, 탐색, 삽입, 삭제: O(1)

// 이상적인 경우
var hashTable = new Dictionary<string, int>();

hashTable["Alice"] = 30;      // O(1) 삽입
int age = hashTable["Alice"]; // O(1) 참조
hashTable.Remove("Alice");    // O(1) 삭제

 

 

 

최악의 시간복잡도 

해시테이블에서 충돌이 많이 일어나는 경우

• 참조, 탐색, 삽입, 삭제: O(n)

최악의 경우 (모든 데이터가 같은 해시값):
Index   Data
  0   → [     ]
  1   → [     ]
  2   → [     ]
  3   → [Alice] → [Bob] → [Charlie] → [David] → ...
  4   → [     ]
  ...

모든 요소가 인덱스 3에 몰림 → 탐색 시 전체 체인 순회 필요

 

충돌 문제 해결 방법

해시 충돌은 서로 다른 키가 같은 해시값을 가질 때 발생합니다.

 

1. 체이닝 (Chaining)

 

충돌 시 연결리스트에 할당하고, 충돌 시 연결리스트를 탐색하는 기법

체이닝 구조:
Index   연결리스트
  0   → [     ]
  1   → [     ]
  2   → [     ]
  3   → [Alice, 30] → [Eve, 27] → NULL
  4   → [     ]
  5   → [David, 28] → NULL
  6   → [     ]
  7   → [Bob, 35] → NULL
  ...

Alice와 Eve가 모두 해시값 3을 가짐 → 연결리스트로 연결

 

장점

• 구현이 간단하며 이해하기 쉬움
• 해시테이블에 많은 데이터를 집어넣을 수 있음
• 메모리 사용량 예측 가능

단점

• 연결리스트 기반이라 캐시 성능이 좋지 않음
• **체인이 길어지면 최악의 경우 O(n)**이 될 수 있음

레드-블랙 트리 개선

Java 8의 HashMap에서 적용된 최적화 기법으로, 최악의 경우 O(n)의 시간복잡도를 O(log n)으로 개선합니다.

개선된 체이닝:
체인 길이 < 8: 연결리스트 사용
체인 길이 ≥ 8: 레드-블랙 트리로 변환

장점: 최악의 경우에도 O(log n) 보장

 

 

2. 개방 주소법 (Open Addressing)

 

충돌 시 다른 버킷에 데이터를 삽입하는 기법

기본 개념: 해시 충돌이 발생하면 미리 정해진 규칙에 따라 다른 빈 슬롯을 찾아 데이터를 저장

 

2-1. 선형 탐사 (Linear Probing)

       해시 충돌 시 다음 버킷, 혹은 몇 개를 "선형적으로" 건너뛰어 데이터를 삽입

선형 탐사 예시:
초기 해시테이블:
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

1. "Alice" → 해시값 3 → 인덱스 3에 저장
[0] [1] [2] [Alice] [4] [5] [6] [7] [8] [9]

2. "Bob" → 해시값 3 → 충돌! → 다음 빈 슬롯(4) 찾기
[0] [1] [2] [Alice] [Bob] [5] [6] [7] [8] [9]

3. "Charlie" → 해시값 3 → 충돌! → 다음 빈 슬롯(5) 찾기  
[0] [1] [2] [Alice] [Bob] [Charlie] [6] [7] [8] [9]

 

2-2. 제곱 탐사 (Quadratic Probing)

       해시 충돌 시 1부터 연속적인 수를 제곱한 만큼 건너뛴 버킷에 데이터를 삽입

제곱 탐사 공식: (hash + i²) % table_size

충돌 해결 과정:
1번째 시도: (3 + 1²) % 10 = 4
2번째 시도: (3 + 2²) % 10 = 7  
3번째 시도: (3 + 3²) % 10 = 2
4번째 시도: (3 + 4²) % 10 = 9

 

2-3. 이중 해싱 (Double Hashing)

       해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용해서 데이터를 삽입

이중 해싱 공식: (hash1(key) + i × hash2(key)) % table_size

hash1(key): 기본 해시 함수
hash2(key): 보조 해시 함수 (보통 소수 사용)

 

충돌 해결 방법 비교

 

체이닝 vs 개방 주소법

특성	체이닝	개방 주소법
메모리 사용	추가 포인터 필요	테이블 공간만 사용
캐시 성능	나쁨 (포인터 추적)	좋음 (연속 메모리)
구현 복잡도	간단	중간
부하율 제한	없음 (>1.0 가능)	있음 (<0.7 권장)
삭제 연산	간단	복잡 (tombstone 필요)

 

개방 주소법 탐사 방법 비교

방법	장점	단점
선형 탐사	구현 간단, 캐시 친화적	클러스터링 발생
제곱 탐사	클러스터링 감소	2차 클러스터링
이중 해싱	균등 분포	추가 해시 함수 필요