[자료구조] 해시 테이블 (Hash Table)

Hash Table - (key, value) 한 쌍의 형태로 데이터 저장

 

---

 

key와 value가 한 쌍의 형태로 저장되는 자료구조.
각 key에 해시 함수를 적용해 내부 버킷에 값을 저장하여 관리한다.

트리를 이용하면 해당 위치에 맞는 자리를 찾아야 하지만, 해싱은 key 하나로 쉽게 값을 가져올 수 있다.

 

 

특징

• 순서대로 저장되지 않는다.
• 트리나 배열보다 빠른 속도로 데이터에 접근할 수 있다.
• key는 중복된 값을 가질 수 없다.
  value는 중복된 값이 올 수 있다.
  • key는 value를 찾기 위한 열쇠의 역할을 한다. 만약 동일한 키가 여러개 존재한다면, 해당 키로 우리가 찾고자 하는 값을 찾을 수 없다. 해당 컬렉션에서 키는 유일하게 존재해야 한다.

 

 

해시 함수 Hash Function

해시 함수를 통해 key와 value의 주소를 매핑한다.

• 입력 원소가 해시테이블 전체에 골고루 저장되어야 한다.
• 해시 함수는 복잡하게 구현하지 않아도 된다.

 

곱하기, 나누기 등으로 해시 함수를 생성할 수 있다.

h(x) = x mod m

위 방법을 나누기의 가장 대표적인 모습이다.
m은 해시테이블의 크기로, 소수를 선택하는 것이 좋다.

 

 

충돌 Collision

한 주소에 값이 2개 이상 저장되는 경우 해시 충돌이 일어났다고 한다.
키 하나로 값을 찾을 때, 값이 여러개가 있으면 우리가 찾고자 하는 값을 찾을 수 없다.
해시 함수를 수정하거나 연산을 추가하여 충돌을 해결해야 한다.

 

1. 체이닝 Chaining

같은 주소에 있는 것을 연결리스트로 관리한다.

해시 함수를 통해 키에 해당하는 주소에 값이 저장된다.
그 값이 들어갈 공간을 연결리스트로 만들어 한 주소가 하나의 연결리스트 형태로 만들어 관리한다.

 

2. 개방 주소법 Open Addressing

1. 선형 조사 Linear Probing
    - 충돌이 일어난 위치의 바로 다음을 확인
   
   
2. 제곱 조사 Quadratic Probing
    - 충돌 위치의 다음을 확인하되, 보폭을 제곱만큼 넓혀가며 확인
   
   
3. 더블 해싱 Double Hashing
    - 해시 함수 두개를 사용하여 계산
4. 뻐꾸기 해싱 Cuckoo Hashing
    - 기존 원소를 다른 위치로 이동시키고 삽입