해시테이블 Hashtable

해시테이블 HashTable

 

Concepts

해싱함수(hash function)

• 해싱함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길의의 데이터로 매핑하는 함수.
• 매핑 전 데이터 값을 Key, 매핑 후 데이터 값을 해시값(Hash value), 매핑하는 과정을 Hashing이라고 한다.

• 해시함수는 언제나 동일한 해시값을 리턴

• 해당 index만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있다.

• index는 계산이 간단한 함수(상수시간)로 작동한다.

  —> 데이터 엑세스(삽입,삭제,탐색)시 O(1)을 지향한다.

 

해시테이블(HashTable)

• 해시함수를 사용하며 키를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터를 키와 함께 저장하는 자료구조
• 데이터가 저장 되는 곳을 bucket 또는 slot 이라고한다

• 장점

  • 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
  • ex) 하드디스크나 클라우드에 존재하는 무한에 가까운 key들을 유한한 개수의 hash value로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다.

• Direct-address table : 키의 개수와 동일한 크기의 버킷을 가진 해시테이블

  • 해시 충돌 문제가 발생하지 않는다.
  • 전체 키에 대한 공간을 만들어 놓는다
  • 실제 사용하는 키보다 전체 키가 훨씬 많은 경우 메모리 효율성이 떨어진다.

 

 

Problem

• 해시함수는 해쉬값의 개수보다 대게 많은 키 값을 해쉬값으로 변환(many-to-one)하기 때문에,

• 해시 함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 나타내는 해시충돌(collision)이 발생하게 된다.

  

• 현재까지 개발된 거의 모든 해싱함수는 해시충돌을 일으킨다.

• 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는것이 중요하다.

 

 

Solve

Chaining

• 하나의 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다.
• 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가르키는 방식으로 구현(연결리스트)
• 메모리 문제를 야기할 수 있다.

• 시간복잡도

  hashtable size : m , keys : n

  버킷 하나당 n/m = x개의 데이터 이라 가정.

  • 탐색

    매핑 O(1) + 버킷요소 x 탐색 O(x) => O(1+x)

  • 삽입

    매핑 O(1) + 추가 O(1) => O(1)

  • 삭제

    매핑 O(1) + 탐색 O(x) + 삭제 O(1) => O(1+x)

 

open addessing

• 한 버킷당 들어갈 수 있는 엔트리가 하나쁜인 해시테이블
• 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용
• 메모리 문제는 발생하지 않지만, 해시충돌이 생길 수 있다.
• 특정 해시값에 키가 몰리게 되면 효율성이 크게 떨어진다.

ex) 해시함수가 '키 값을 8로 나눈 나머지' 10, 18, 26 순으로 해시테이블에 삽입해보자.

세 숫자 중 첫번째 값 10 을 제외한 18, 26인 원래 버킷(2) 말고 각각 다음 (3) , (4)에 저장된다.

[2] 10

[3] 18

[4] 26

—선형탐사

 

probing

• open address의 효율성 감소 문제를 해결한다.
• 삽입,삭제,탐색을 수행하기 위해 해시테이블 내 새로운 주소를 찾는 과정

 

• 선형탐사(Linear probing)

  • 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼있으면 해시값에서 고정폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스한다.
  • 여기에 데이터가 있으면 또 고정폭 만큼 옮긴다.
  • 특정 해시값 주면 버킷이 모두 채워져 있는 primary clustering 문제에 최약하다

  

 

• 제곱탐사(Quadratic probing)

  • 이동 폭이 제곱수로 늘어난다.
  • 예를들어, 데이터 엑세스할때 충돌이 일어나면 1^2 칸을 옮긴다. 여기서 또 충돌이 일어나면 2^2 만큼, 그다음엔 3^2 만큼 옮긴다.
  • 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 secondary clustering에 취약하다.

  

• 이중 해싱(double hashing)

  • 탐사할 해시값의 규칙성을 없애서 clustering을 방지한다.
  • 2개의 해시함수를 준비해 하나는 최초의 해시값을 얻을 때, 하나는 해시충돌이 일어났을때 탐사 이동폭을 얻기 위해 사용.