자료구조 - 해시테이블

해시테이블

---

해시테이블 이란?

• Key, Value의 쌍으로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다.

• 내부적으로 배열을 사용하여 데이터를 저장하고, 각각의 key값에 해시 함수를 적용해 배열의 유일한 인덱스를 생성한다. 이 인덱스를 활용해 값을 저장하거나 검색하게 된다.

 

해시 함수

• 저장할 데이터의 key를 고유한 인덱스로 변환하여 해시 테이블에 저장하기 위해 사용되는 함수. 
• 대표적 해시 함수로는 아래 4가지가 있다.
  1. Division Method: 입력값을 테이블의 크기로 나누어 계산한다. 
  2. Digit Fording: key의 문자열을 아스키 코드로 바꾸고 값을 합한 데이터를 주소로 사용한다.
  3. Multiplication Method: 특정한 값을 사용해 연산을 하여 주소로 사용한다.
  4. Universal Hashing: 다수의 해시 함수를 만들고, 무작위로 해시함수를 선택해 해시값을 만든다.

 

해시 충돌

• 해시 함수로 나온 결과 값이 동일하다면 충돌이 발생한다. 

• 분리 연결법, 개방 주소법을 사용하여 충돌에 의한 문제를 해결할 수 있다.

1. 분리 연결법
   • 해시 충돌이 발생하면 연결 리스트로 데이터들을 연결한다. 
   • 해시 값으로 나온 값을 그대로 주소값으로 사용한다.
2. 개방 주소법

   • 해시 충돌이 발생하면 다른 주소에 데이터를 저장한다.

   • 아래와 같은 3가지 방법이 있다.

     1. 선형 탐색: 현재 인덱스로 부터 고정폭 만큼 이동하여 차례대로 검색해 비어있는 인덱스에 데이터를 저장한다.

     2. 제곱 탐색: 해시의 저장 순서 폭을 제곱으로 늘이면서 저장한다. 처음 충돌이 발생하면 1만큼 이동하고, 그 다음 충돌이 발생하면 2^2, 3^2 칸씩 이동하며 저장한다.

     3. 이중 해시: 해시 값을 한번 더 해싱한다. 

 

해시테이블 시간복잡도

• 해시 함수에 의해 고유한 인덱스로 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도를 가진다.
• 데이터 충돌이 발생한 경우 분리 연결법에서 연결된 리스트까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.

 

HashMap VS HashTable

• HashMap은 동기화를 지원하지 않는다.
• HashTable은 동기화를 지원한다.

 

reference

mangkyu.tistory.com/102

preamtree.tistory.com/20