[알고리즘 특강] 7. Hash

1. 해시의 정의와 필요성

1.1 해시란?

• 정의: 검색과 저장이 아주 빠르게 진행되는 데이터를 다루는 기법
• 특징:
  • Key -> Value를 이용한 빠른 탐색
  • key와 value가 한 쌍으로 존재
  • key값이 배열(해쉬테이블)의 인덱스로 변환
  • 검색과 저장의 평균적 시간 복잡도가 O(1)

1.2 해시의 주요 구성 요소

1. Key: 검색할 때 사용하는 인풋
2. Value: 검색해서 찾아내는 아웃풋
3. Hash function: 탐색할 data를 해시값으로 변환하는 함수
4. Hash Table: 해시 함수에 의해 반환된 주소의 위치에 항목을 저장한 자료 구조

2. 해시 구현

2.1 Hash Key

• 구현 방식:
  • 고유한 값으로 해시 함수에 입력 값으로 사용
  • 키 값 그대로 최종 저장소에 저장되면 다양한 길이의 저장소를 미리 구성해야 함
  • 해쉬 함수로 값을 바꿔 저장

2.2 Hash Value

• 구현 방식:
  • 최종 저장소 (aka bucket, slot)에 hash와 매칭되어 저장

2.3 Hash Collision

• 정의: 서로 다른 Key인데, 해시 값이 같게 나오는 경우
• 해결 방법:
  1. Chaining:
     • 충돌나는 값을 기존 값과 연결시켜 저장
     • key:value 매칭이 1:N
     • 연결 시키는 방법: Linked List
     • 검색 효율이 떨어질 수 있지만, 저장소를 효율적으로 사용하여 메모리를 적게 쓰는 장점
  2. Open Addressing:
     • 충돌이 발생하면 다른 비어있는 자리에 저장
     • key:value 매칭을 1:1로 유지
     • 비어있는 자리 찾는 방법:
       • 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)을 건너뛰어 빈자리 찾기
       • 제곱 탐색 (Qudratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장
       • 이중 해시(Double Hasing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장

3. 해시 테이블 크기

3.1 크기 선택 기준

• 권장 크기:
  • 보통 소수 (prime number)나 2^N 사이즈를 사용
  • 흔히 쓰이는 소수: 10007, 20011, 30011, 40009, 100003, 200003
  • C++의 Unordered Associative Containers는 소수를 사용

3.2 크기 선택 시 고려사항

• 소수 사용의 장점:
  • 해시 함수가 아주 고르게 분포하는 값들을 출력해주면 테이블 크기가 소수가 아니어도 괜찮음
  • 특정 자리(예 5의 배수)에 몰리는 상황도 발생할 수 있음
  • 가장 이상적인 테이블의 크기는 자신을 제외한 모든 수와 서로소인 소수
• 2의 거듭제곱 사용의 단점:
  • bit masking을 통해 나머지를 빠르게 계산할 수 있음
  • m개의 하위 bit를 그대로 사용하기 때문에 해쉬 함수가 하위 bit을 고르게 분포 시키지 못하면 많은 충돌이 발생

3.3 생일 문제와 해시 테이블 크기

• 생일 문제 예시:
  • 366명 이상의 사람이 모이면 생일이 같은 사람이 반드시 한 쌍 이상 나옴
  • 생일이 같은 쌍이 존재할 확률이 50%가 되기 위해서는 23명이 필요
  • 23개의 데이터를 삽입했을 때 충돌이 일어날 확률을 50%로 유지하는데만 해도 365개 크기의 테이블이 필요
  • 충돌 방지를 위해 단순 테이블 크기를 늘리는 것은 좋은 방법이 아님

4. 해시 구현 예시

4.1 Java 구현

// 기본
HashMap<String, Integer> testMap = new HashMap<String, Integer>();
testMap.put("s",2);
testMap.put("s",1); // 중복이라 덮어씌움
testMap.put("s1",2);
testMap.putIfAbsent("s1",3);  // 중복 key가 입력되었을 때 업데이트 x
System.out.println(testMap.get("s")); // 1
System.out.println(testMap);   // {s=1, s1=2}

// 기타 해쉬 메서드
remove()
clear()
replace(K key, V new_value)
size()
contains()
getOrDefault(Object k, V defaultValue)