[CS] Hash Table

Hash Table 에 대한 개념 정리를 위해 포스팅 한다.

 

1. 정의

- 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value 쌍의 데이터를 입력 받고 Hash Function h에 key 값을 입력으로 넣어 얻은 해시값 h(k)을 위치로 지정하여 key-value 데이터 쌍을 저장

 

2. 특징

- Collision 발생 가능성 존재

  - 서로 다른 key의 해시값이 존재할 때 발생

  - Collision 이 발생하는 경우, Open Addressing 또는 Separate Chaining 등의 방법을 통해 해결

    - Open Addressing (개방 주소 방법)

      - Collision 이 발생하면 미리 정한 규칙에 따라 Hash Table 의 비어 있는 slot 을 찾음, 메모리를 적게 사용

      - Linear Probing(선형 조사)

        - 충돌이 일어난 자리에서 i 에 관한 일차 함수의 보폭으로 점프

        - 테이블의 경계를 넘어갈 경우에는 맨 앞으로 돌아감

      - Quadratic Probing(이차원 조사)

        - 바로 뒷자리를 보는 대신 보폭을 이차 함수로 넓혀가면서 봄

        - 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있음

      - Double Hashing(이중 해시)

        - 두 개의 함수를 사용

        - 하나의 함수는 최초의 해시 값을 얻을 때, 다른 하나의 함수는 해시 충돌이 났을 때 이동할 폭을 얻을 때 사용

        - 두 원소의 첫 번째 해시 값이 같더라도 두 번째 해시 값까지 같을 확률은 극히 작으므로 서로 다른 보폭으로 점프

    - Separate Chaining

      - Collision 이 발생하면 Linked list(또는 Tree)에 노드(slot)을 추가

      - Worst Case 의 경우 n 개의 모든 key 가 동일한 해시 값을 갖게 되면 길이 n 의 linked list 가 생성되고,

         이 때 검색의 시간 복잡도는 O(n)이 됨

- 시간 복잡도와 공간 복잡도

  - 시간 복잡도는 저장, 삭제, 검색 모두 기본적으로 O(1) 이지만, Collision 으로 인하여 최악의 경우 O(n) 이 될 수 있음

  - 공간 복잡도는 떨어짐, 데이터가 저장되기 전에 미리 저장 공간(slot, bucket) 을 확보해야 하기 때문

- 참고) 좋은 Hash Function 의 조건

  - 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 함

 

3. Hash Map 과의 비교

- Hash Map 은 Thread-Safe 하지 않고, Hash Table 은 Thread-Safe 하다

  (따라서 Multi-Thread 환경이 아니라면 Hash Table은 Hash Map보다 성능이 떨어진다)

- Hash Map 은 key 에 null 을 허용하지만, Hash Table 은 허용하지 않는다

- Hash Map 은 보조 해시를 사용하여 Collision 이 발생할 가능성이 적어 성능이 좋다

 

4. 출처

https://www.inflearn.com/course/%EA%B0%9C%EB%B0%9C%EC%9E%90-%EC%A0%84%EA%B3%B5%EB%A9%B4%EC%A0%91-cs-%EC%99%84%EC%A0%84%EC%A0%95%EB%B3%B5