자료구조 Hash Table - mapc-team/document GitHub Wiki

Hash Table

  • hash는 내부적으로 배열을 사용하여 저장하기 때문에 빠른 검색속도를 가짐. (Search할 때 고유 인덱스로 접근하므로 O(1)이지만 collision이 일어나므로 항상 O(1)은 아니다.)
  • 인덱스로 저장되는 key값이 불규칙 -> 데이터과 연관된 고유한 숫자를 만들어 인덱스로 사용

Hash Function

  • '고유한 인덱스 값을 설정하는 알고리즘'을 hash method 또는 해시 함수(hash function)라고 하고 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 한다. 저장되는 값들의 key 값을 hash function을 통해서 작은 범위의 값들로 바꿔준다.
  • Collision : 서로 다른 두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)되면 같은 곳에 저장할 수 없게 된다.

좋은 Hash Function이란?

  • 일반적으로 좋은 hash function은 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 냄
  • Hash function을 무조건 1:1로 만드는 것보다 Collision을 최소화 하는 방향으로 설계 및 collision을 어떻게 대응할 것인가가 더 중요
  • Collision이 많아질수록 Search에 필요한 Time Complexity가 O(1)에서 O(n)에 가까워짐. -> hashing된 인덱스에 이미 다른 값들이 들어있다면 세 데이터를 저장할 다른 위치를 찾은 후에 저장.

Resolve Conflict

1. Open Address 방식(개방 주소법)

  • 해시 충돌이 발생하면 다른 해시버킷에 해당 자료를 삽입하는 방식
  1. Linear Probing : 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행
  2. Quadratic Probing: 2차 함수를 이용해 탐색할 위치를 찾는다.
  3. Double Hashing Probing: 하나의 해쉬함수에서 충돌이 발생하면 2차 해쉬함수를 이용해 새로운 주소를 할당한다. (위 두가지 방법에 비해 연산량이 많음)

2. Separate Chaining 방식(분리 연결법)

  • 일반적으로 Open Addressing 은 Separate Chaining 보다 느리다. Open Addressing 의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다.

연결리스트를 사용하는 방식(Linked List)

  • 각각의 버킷을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 bucket의 list에 추가하는 방식
  • 연결리스트의 장단점 그대로 삽입, 삭제가 간단하지만 작은 데이터들을 저장할 때 오버헤드가 크다.
  • 버킷을 계속해서 사용하는 Open Address에 비해 테이블의 확장을 늦출 수 있다.

Tree를 사용하는 방식(Red-Black Tree)

  • 기본적인 알고리즘은 Separate Chaining과 동일. 연결리스트 대신 트리를 사용
  • 데이터가 많은 경우 Tree 사용, 적은 경우 연결리스트 사용. 데이터 갯수가 적을 때 worst case의 경우 성능 차이는 별로 없다. 그러나 트리는 기본 메모리 사용량이 많기 때문에 데이터가 적은 경우 연결리스트 사용

데이터가 적다는 기준?

  • key-value 쌍의 갯수가 6개, 8개 기준이다.
  • 각각 자료구조로 넘어가는 기준이 1이면 Switching 비용이 너무 크다. ex)
  • 6 -> 7: 연결리스트
  • 7 -> 8: 연결리스트 -> 트리
  • 8 -> 7: 트리
  • 7 -> 6: 트리 -> 연결리스트

Open Address VS Separate Chaining

  • 둘다 Worst Case에서 O(n)
  • Open Address방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높음. -> 데이터 갯수가 적으면 Open Address가 성능이 더 좋다.
  • Separate Chaining보다 Open Address은 버킷을 계속해서 사용 -> Separate Chaining방식은 테이블 확장을 늦출 수 있음

보조 해시 함수(Supplement Hash Function)

  • key의 해시 값을 변형하여 해시 충돌 가능성을 줄임
  • Separate Chaining방식을 사용할 때 함께 사용
  • Worst Case에 가까워지는 경우를 줄임

해시 버킷 동적 확장(Resize)

  • 해시 버킷 갯수가 적으면 메모리를 아낄 수 있지만 해시 충돌로 인해 성능적으로 좋지 않다.
  • key-value쌍 데이터가 일정 갯수 이상이 되면 버킷 갯수를 두배로 늘림
  • 일정 갯수 : 현재 데이터 갯수가 해시 버킷의 갯수의 75%가 될때. 0.75라는 숫자는 load factor라고 불린다.