Hash Table

📖Hash Function

임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수

📎로드 팩터(Load Factor)

해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것 $loadfactor=n/k$

• 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지, 해시 테이블의 크기를 조정해야 할지를 결정
• 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소

📎해싱

해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것

• 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 기법
• 최적의 검색이 필요한 분야에서 주로 사용

📖Hash Table

해시 함수를 통해서 얻은 해시(key)를 index로 사용하고 해당 index에 value를 저장하는 자료구조

• 파이썬의 dictionary가 hash table로 구현되어 있음

📎특징

• key를 value에 매핑할 수 있음
• 삽입, 검색, 삭제의 기본 연산이 가능
• 속도가 빠름

📎속도

Algorithm	Average	Worst
space	O(n)	O(n)
insert	O(1)	O(n)
search	O(1)	O(n)
delete	O(1)	O(n)

• key-value가 1:1 매핑되어 있기 때문에 삽입, 검색, 삭제 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가짐

📖충돌

해시 함수를 통해 해싱한 해시 값이 중복인 경우

📎해결방법

1. Separate Chaining(개별 체이닝)

충돌 발생 시 연결리스트로 연결하는 방식

• 최악의 경우, 탐색의 시간이 O(n)이 됨

Separate Chaining은 어떤 원리인가요?

1. 키의 해시 값을 계산
2. 해시 값을 이용해 배열의 인덱스를 구함
3. 같은 인덱스가 있다면 연결 리스트로 연결

2. Open Addressing(오픈 어드레싱)

충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식

• 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없음
• 버킷 사이즈보다 큰 경우에는 삽입 불가
• 파이썬의 dictionary가 사용하는 방식

Open Addressing의 탐사 방식은?

선형 탐사 주로 사용

1. 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행
2. 특정 위치가 선점되어 있으면 바로 그다음 위치를 확인
3. 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입

📖코딩 테스트에서의 Hash Table

브루트 포스(완전 탐색)으로는 시간초과에 빠지게 되는 문제에서 주로 사용