[TIL] 102. [자료구조] 해시테이블

키워드

• 해시
• 해시함수
• 해시테이블
• 해시충돌(체이닝, 오픈 어드레싱)

해시테이블

• 키(key)를 활용하여 값(value)에 직접 접근이 가능한 구조
• 해싱의 주된 목적은 검색
• 데이터의 양과 상관없이 성능이 빠르다.(키를 통해 바로 값을 검색하기때문)
• 파이썬의 딕셔너리는 내부적으로 해시테이블 구조

해시함수

• 해시함수를 통해 키를 해시테이블 내의 버킷(=hashes)로 매핑
• 해시함수의 입력값 형태는 다양하지만, 출력값의 형태는 숫자
• 입력값과 출력값이 일대일 대응이 되어야 한다.
• 실제로는 완벽한 일대일 대응은 어려우며, 다른 입력값에 대해 같은 출력이 나오는 경우를 해시충돌이라고 한다.
• 일반적으로 해시함수는 문자열 입력값을 정수형 출력값으로 반환

해시성능

• O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다.(해시충돌로 인해 O(1)보다 큰 시간복잡도를 갖기도 함)

해시충돌

• 입력된 키가 들어갈 자리(버킷)이 없는 경우 발생
• 실제로 모든 데이터를 알고 있지 않다면, 완벽한 해시 함수를 작성하는 것은 불가능
• 가능한 충돌이 적은 해시함수를 만드는 것이 해시테이블의 가장 중요한 목적

[해시충돌 방지] Chaining(체이닝)

• 개념 자체는 간단하다. 버킷이 있으면 각 버킷에 충돌이 일어났을 때(키값이 여러개 들어왔을 때)
  순서대로 연결리스트 형태로 저장한다.

[해시충돌 방지] Open Addressing(오픈 어드레싱)

• 다른 로직의 함수를 활용하기에 붙여진 이름
• 해시값이 이미 존재한다면, 다양한 로직을 적용하여 비어있는 슬롯이 있을 때까지 해당 로직을 반복하여 자리를 잡는다.
• 충돌이 일어나는 경우, 탐사(Probing)을 진행하면서 빈 공간을 찾아 해결
• 체이닝은 한정된 배열 내에서 계속 연결리스트 형태로 저장 가능한 반면, 저장공간이 정해져있다.

로드팩터(Load Factor ; 적재율)

• 로드 팩터 = (해시 테이블 내의 아이템의 수) / (배열 슬롯의 총 개수)
• 시간복잡도 Big O와 같이 절대적인 수치가 아닌, 상대적인 해시테이블의 포화된 정도를 비교하는 지표
• 로드 팩터값을 기준으로 해시함수 재작성 여부, 해시테이블 크기 조정 여부 등이 결정