[데이터 구조와 활용] 해시 테이블

1. 해시테이블

(1)  정의

- 키를 사용하여 데이터를 빠르게 검색하고 저장하는 데이터 구조

- 일반적으로 데이터 검색, 삽입, 삭제가 매우 빠르게 평균적으로 O(1) 이루어짐

- 일반적은 배열이나 리스트의 선형 탐색 O(n)보다 매우 빠름

- 해쉬 함수를 사용해 키를 해시(배열 인덱스)로 변환해 데이터를 저장, 검색함

- 해시값은 특정 키를 고정된 길이의 값으로 변환한 결과를 의미함

(2) 핵심 원리 : 해시 함수

- 해시테이블에서 데이터를 저장하고 찾기 위해서는 키를 인덱스로 변환하는 과정이 필요함

- 이 때 사용하는 함수가 해시 함수임

(3) 해시 함수의 조건

- 같은 키를 넣으면 항상 같은 해시 값을 반환함

- 가능한 한 충돌을 최소화하며, 해시 값이 균등하게 분포되어야 함

- 서로 다른 키도 때로는 같은 해시 값을 가질 수 있으며, 이를 충돌이라 함

- 계산 속도가 빠르고 효율적이어야 함

(4) 해시 함수 vs 암호학적 해시 함수의 비교

- 두 함수는 기본 목적(데이터 변환)은 유사하나 세부 목적과 요구조건(속도 vs 보안)이 매우 다름

- 암호학적 해시 함수는 충돌 방지와 보안이 최우선이므로 설계가 매우 복잡하고 상대적으로 느림

- 암호학적 해시 함수 예시 : SHA-256, SHA-3 등

(5) 해시 충돌

- 서로 다른 두 개 이상의 키가 같은 해시 값을 갖게 되는 현상

- 충돌이 발생하면 키가 저장될 위치가 중복되어 문제가 발생함

- 같은 위치에 두 개의 키를 저장할 수 없으므로 충돌이 발생함, 충돌이 발생하면 키를 찾을 때 추가적인 탐색 과정이 필요함

(6) 충돌 해결 방법 1 : 체이닝 방식

- 체이닝 방식은 각 배열 인덱스 위치에 여러 키들을 연결 리스트 형태로 저장

- 충돌이 발생해도 같은 인덱스에 키를 이어 붙이는 방식이므로 구현이 단순함

- 많은 언어에서 체이닝을 기본으로 사용(파이썬은 아님)

- 충돌 발생 시 리스트에서 키를 하나씩 비교하며 탐색(선형 탐색)

- 해시 값이 같은 위치에서 실제 키가 존재하는지 확인해야 함

def hash_func(key) :     return key % 5 hash_table = [[]for i in range(5)] keys = [1,6,11] for key in keys :     index = hash_func(key)     hash_table[index].append(key) print(hash_table)

(7) 충돌 해결 방법 2 : 오픈 어드레싱 방식

- 충돌이 발생하면 해시 테이블 내에서 다음 번 슬롯을 찾아 키를 저장함

- 별도의 연결 리스트를 사용하지 않으므로, 메모리 사용량이 적음

- 파이썬 dist, set 데이터 구조는 오픈 어드레싱 방식을 사용해 충돌을 처리함

- 충돌 발생 시 해시 테이블 내부의 다른 빈 슬롯을 찾아 키를 저장함

- 가장 간단한 방식인 선형 탐사를 기반으로 설명함

- 실제 파이썬의 dict와 set은 이보다 더 복잡한 perturbation 기반 방식 사용

def hash_func(key) :     return key % 5 hash_table = [None]*5 keys = [1,6,11] for key in keys :     index = hash_func(key)     while hash_table[index] is not None :         index = (index+1)%5     hash_table[index] = key print(hash_table)

(8) 체이닝 방식 vs 오픈 어드레싱 방식

방식	체이닝 방식	오픈 어드레싱 방식
충돌 시 저장 방식	같은 인덱스에 리스트로 저장	해시 테이블 내 다른 빈 슬롯에 저장
구조	인덱스별 연결 리스트	전체 테이블 분산 저장
탐색	연결 리스트 선형 탐색	슬롯 이동하며 탐색

(9) 충돌 시 탐색과 시간 복잡도

- 평균적으로는 매우 빠르며, 탐색/삽입/삭제 모두 평균적으로 O(1)의 시간 복잡도를 가짐

- 하지만 충돌이 많이 발생하면, 탐색 경로가 길어지고 최악의 경우 O(n) 시간 복잡도로 성능이 떨어질 수 있음

- 체이닝 방식 : 많은 키가 동일한 해시 값을 가질 경우

- 오픈 어드레스 방식 : 테이블이 거의 가득 찬 상태에서 충돌이 많은 경우

- 적절한 테이블 크기와 해시 함수의 분산 성능이 중요함

(10) 해시값과 실제값 존재 여부 판단 방법

- 해시 테이블에서 키 존재 여부를 판단할 때는 2단계를 거침

ⓐ 해시 값 계산 (충돌 있을 시 ⓑ 진행)

ⓑ 실제 키 비교 - 체이닝/오픈 어드레스

- 해시값은 빠르게 위치를 찾아줄 뿐이며, 실제 값 존재 여부는 반드시 키 비교를 통해서만 판단함

- 실제로 키가 없는데 있는 것으로 잘못 판단하는 경우는 절대 발생하지 않음

- 해시값만 보고 바로 키가 있다고 판단하지 않고, 반드시 실제 키를 다시 비교하기 때문에 오판 가능성은 없음

- 그러나 실제로 키가 있는데 빠르게 찾지 못하고 시간이 오래 걸릴 수 있음

- 충돌이 많으면 탐색 시간이 증가하여 성능이 저하될 수 있음

- 키가 있는데 없다고 판단하는 경우는 없고, 다만 탐색 시간이 늘어날 수 있음

(11) 해시 함수의 성능

- 해시 함수는 빠르고 균등하게 분포된 해시값을 생성해야 하며, 잘못된 해시 함수의 선택은 성능이 크게 떨어질 수 있음

(12) 활용 사례 

- 해시 테이블은 특정 문제를 해결할 때 필수적인 데이터 구조임

- 회원 관리 시스템에서 회원 ID, PW 정보 등

- 데이터 베이스에서 빠른 검색

- 검색 엔진

- 캐시 등

2. 파이썬의 해시 테이블

(1) 파이썬 내장 해시 테이블 기반 데이터 구조

- dict : 키-값의 쌍으로 이루어짐 (빠른 데이터 검색 및 관리)

- set : key만으로 이루어짐 (빠른 데이터 존재 여부 확인)

(2) 파이썬 set에서의 key

- 파이썬에서 set은 내부적으로 dict과 유사한 방식으로 동작하지만, 값은 없어 키만 저장하는 구조로 구현되어있음

- set에서는 데이터가 곧 키역할을 함

- dict, set 모두 hash('apple')을 사용해 같은 방식으로 탐색 수행

구조	예시
dict	{'apple':100} -> key = 'apple', value = 100
set	{'apple'} -> key = 'apple', value = 없음 또는 더미

(3) 파이썬 dict에서의 value는 어디에 저장될까?

- 해시 테이블의 각 슬롯에는 키와 값이 쌍으로 저장되어있음

- 슬롯마다 키-값 쌍이 함께 저장되고, 탐색은 키를 중심으로 진행되며, 값은 따라오는 구조임

(4) 파이썬 dict 기본 문법 및 주요 메서드

- dict은 키를 통해 데이터를 저장하고, O(1)의 빠른 탐색 속도를 제공함

- 다양한 메서드를 통해 dict을 효율적으로 활용할 수 있음

(5) 파이썬 set 기본 문법 및 주요 메서드

- set은 키로만 구성된 데이터를 저장하고 존재 여부 체크가 O(1) 성능임

- 수학적 집합 연산 수행 가능

(6) dict과 set 리스트의 성능 비교

- dict, set 평균 O(1)의 빠른 탐색 성능 제공

- list 탐색 시 O(n)의 느린 성능 제공

- 실제 데이터가 많아질수록 성능 차이는 매우 커짐

(7) 파이썬의 collections.defaultdict

- 기존은 dict보다 유용하게 활용되는 확장된 형태의 dict임

- 일반적인 dict은 키가 없을 때 key error가 발생함

- collection.defaultdict은 키가 없으면 자동으로 기본값을 생성하여 반환함

- collection.defaultdict (int) == 키가 없을 때 int() 호출 -> 0으로 초기화됨

(8) dict과 set의 주의사항

- dict과 set의 키는 반드시 변경 불가능한(immutable) 데이터 타입만 가능

- 가능 : 수, 문자열, 튜플

- 불가능 : 리스트, 딕셔너리 등

(9) 시간 복잡도

- 평균 O(1), 최악의 경우 O(n)

3. 해시 테이블 활용하기

(1) BOJ 15829

l = int(input()) s = input().rstrip() h = 0 for i, v in enumerate(s) :     a = ord(v) - ord('a')     h += a * (31**i)     h %= 1234567891      print(h)

5 abcde 3785410

(2) BOJ 7785

n = int(input())    s = set() for i in range(n) :     x, y = input().split()     if y == 'enter' :         s.add(x)     else :         s.remove(x) a = list(s) a.sort(reverse = True) print(*a, sep = '\n')

4 baha enter askar enter baha leave artem enter askar artem