Direct-address Table

이미지 출처: https://baeharam.netlify.app/posts/data%20structure/hash-table

• 직접 주소화 테이블)이란, key 값으로 k를 갖는 원소는 index k에 저장하는 방식
• 단점
  • 불필요한 공간 낭비
  • key가 다양한 자료형을 담을 수 없게 됨

해시 테이블

이미지 출처: https://mangkyu.tistory.com/102

• 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다.
• hash function $h$에 key값을 입력으로 넣어 얻은 해시값 $h(k)$를 위치로 지정하여 key- value 데이터 쌍을 저장합니다. 즉, $h(k)$는 키 $k$의 해시값이다

HashTable 구성

• key는 무조건 존재해야 하며, 중복되는 key가 있어서는 안됩니다.
• hash table을 구성하고 있는, (key, value)데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 합니다.
• hash function은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않도록 잘 설계해야 한다.

Collision

• 서로 다른 key의 해시값이 똑같을 때를 말합니다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이 때 collision이 발생했다고 합니다.

해결방법

open addressing

• collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다.

• 빈 slot을 찾는 방법에 따라 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉩니다.

• 추가적인 메모리를 사용하지 않으므로 linked list 또는 tree자료구조를 통해 추가로 메모리 할당을 하는 separate chaining방식에 비해 메모리를 적게 사용합니다.

• Linear Probing(선형 조사법)& Quadratic Probing(이차 조사법)
  
  이미지 출처: https://mangkyu.tistory.com/102

• 종류

  • Linear Probing(선형 조사법)
    • 충돌이 발생한 해시값으로 부터 일정한 값만큼$(+1, +2, +3, ...)$ 건너 뛰어, 비어 있는 slot에 데이터를 저장
  • Quadratic Probing(이차 조사법)
    • 이차 조사법은 제곱수($+1^2, +2^2, +3^2, ...$)로 건너 뛰어, 비어 있는 slot을 찾습니다.
  • 단점
    • 충돌이 여러번 발생하면 여러번 건너 뛰어 빈 slot을 찾습니다.
    • 선형 조사법과 이차 조사법의 경우 충돌 횟수가 많아지면 탐사이동폭이 같기 때문에 특정 영역에 데이터가 집중적으로 몰리는 클러스터링(clustering)현상이 발생하는 단점이 있습니다.

• Double Hashing(이중해시, 중복해시)

  • 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식
  • 하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용합니다.

separete chaining

이미지 출처: https://mangkyu.tistory.com/102

• collision이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장합니다.
• 서로 다른 두 key가 같은 해시값을 갖게 되면 linked list에 node를 추가하여 (key, value) 데이터 쌍을 저장합니다. 삽입의 시간복잡도는 $O(1)$입니다.
• 검색: 기본적으로 $O(1)$의 시간복잡도 이지만 최악의 경우 $O(n)$의 시간복잡도를 갖습니다.
• 삭제: 삭제를 하기 위해선 검색을 먼저 해야하므로 검색의 시간복잡도와 동일합니다. 기본적으로 $O(1)$이지만 최악의 경우 $O(n)$의 시간복잡도를 갖습니다.
• worst case의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되게 됩니다. 이 때, 검색의 시간복잡도가 $O(n)$이 됩니다.

  seperate chaining은 기본적으로 linked list를 이용하여 데이터를 저장하지만, collision이 많이 발생하여 linked list의 길이가 길어지면 Binary Search Tree(BST)자료구조를 이용하여 데이터를 저장하기도 합니다. BST를 사용함으로써 검색의 worst case 시간복잡도를 $O(n)$ 에서 $O(logn)$으로 낮출 수 있습니다.

시간복잡도와 공간효율

• 시간복잡도는 저장, 삭제, 검색 모두 기본적으로 $O(1)$이지만, collision으로 인하여 최악의 경우 $O(n)$이 될 수 있습니다.
• 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문에, 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 생길 수 있습니다. → 공간효율성은 떨어진다.