(data-structure) Hash Table

호두파파·2021년 3월 18일
0

자료구조

목록 보기
10/14
post-thumbnail

해시테이블을 자료 구조 중 하나로, key와 Value를 저장한다. Key, Hash Function, Hash, Value로 구성된다.

  • 데이터를 저장할 공간을 미리 확보해야하고, 입력된 key 값을 받아 Hash Function을 통해 Hash 값을 얻고, Hash 값을 통해 미리 확보한 공간 어느 위치에 데이터를 저장할지 정하게 된다.
  • key 값의 길이는 모두 달라도, 동일한 길이의 Hash 값이 나온다.

자바스크립트는 High Level Language로, Low Level 메모리를 관리할 수 없다.
따라서 해시테이블을 구현할 땐, 빈객체 / 배열을 사용한다.

John Smith(key)의 전화번호인 521-1234(value)를 저장한다고 하자.

입력된 John Smith(key)Hash function에 적용해서 02(Hash)라는 값을 얻는다.
그러면 "521-1234"(value)는 미리 확보한 공간(0~15번) 중
02(Hash)에 저장하게 된다.

이후 Key 값으로 John Smith를 입력하면, Hash Function을 통해 02라는 위치값을 알게되고, 그 위치에 저장된 521-1234라는 Value값을 얻어낼 수 있다.

구성 요소

키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장이 된다.

  • 키(key) : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
  • 해시함수(hash function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키와 같은 해시가 되는 경우를 해시 충돌(hash collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
  • 해시(hash) : 해시 함수(hash function)의 결과물이며, 저장소에서 값이 매칭되어 저장된다.
  • 값(value) : 저장소에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

Insertion(저장)

해시테이블에서 자료를 저장하기 위해서는 해시 함수(hash function)으로 키(key)를 해시로 변경해야 한다. 위의 사진처럼 해시함수가 input key를 7로 나눈 나머지를 변경해서 출력했을때, 키는 '76', 해시는 '6'이다.

그러면 미리 준비해놓은 0, 1, 2, 3, 4, 5, 6의 저장소 중에 맞는 해시 값을 찾아 해당 값을 저장한다.

해시 함수로 해시를 산출하는 과정에서 서로 다른 key가 같은 hash로 변결되는 문제가 발생할 수 있는데 이는 key와 value가 1:1로 매칭이 되어야 한다는 규칙을 위해한 것으로 이 문제를 해결하면서 저장 되어야 한다.

insertion Big-O

저장 단계의 시간 복잡도는 O(1)이다. 키는 고유하며 해시함수의 결과로 나온 해시와 값을 저장소에 넣으면 되기 때문이다. 이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만 최악의 경우 O(n)이 될 수 있다. 해시 충돌로 인해 모든 저장소의 값들을 찾아봐야 하는 경우도 있기 때문이다.

Deletion(삭제)

저장되어 있는 값을 삭제할때는 저장소에서 해당 key와 매칭되는 값을 찾아서 삭제하면 된다.
( 저장소에는 hash와 값이 함께 저장되어 있으므로 함께 지우면 된다.)

Deletion Big-O

삭제 단계의 시간 복잡도는 O(1)이다. 키는 고유하며 해시함수의 결과로 나온 해시에 매칭되는 값을 삭제하면 되기 때문이다. 이때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만, 최약의 경우 O(n)이 될 수 있다. 해시 충돌로 인해 모든 저장소의 값들을 찾아봐야 하는 경우가 있다.

Search(검색)

키로 값을 찾아내는 과정은 Deletion 과정과 비슷하다.
1) 키로 hash를 구한다.
2) hash로 값을 찾는다.

search Big-O

저장 단계의 시간 복잡도는 O(1)이다. 키는 고유하며 해시함수의 결과로 나온 해시에 매칭되는 값을 찾으면 되기 때문이다. 이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
최악의 경우로 O(n)이 될 수 있다.

Hash Collision(해시 충돌)

해시테이블은 Insertion, Deletion, Search 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있기 때문에 자료구조의 효율성 측면에서 매우 우수하다고 볼 수 있다.

하지만, 해시를 이용한 자료구조 방식에 필욘적으로 다른 key 값이지만, 같은 Hash 값이 나올때가 있다. 이런 현상을 해시 충돌이라 한다.

해시 충돌을 해결하는 방법은 크게 2가지가 있다.

Collision Resolutuon

Seperate Chaining (간추려서 Chaining)

체이닝(Chaining)은 자료 저장 시, 저장소에서 충돌이 일어나면 해당 값을 기존 값과 연결시키는 기법이다.
위 사진에서 Sandra를 저장할 때 충돌이 일어났고, 기존에 있던 John에 연결시켰다. 이때 연결리스트(Linked List) 자려구조를 이용한다. 다음에 저장된 자료를 기존의 자료 다음에 위치시키는 것이다.

체이닝의 장단점

  • 장점
    1) 한정된 저장소를 효율적으로 사용할 수 있다.
    2) 해시 함수를 선택하는 중요성이 상대적으로 적다
    3) 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.
  • 단점
    1) 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
    2) 외부 저장 공간을 사용한다.
    3) 외부 저장 공간 작업을 추가로 해야 한다.

Chaining 시간복잡도(Big-O)

복잡도를 계산하기 전, 한 가지를 추가하자면 해시 테이블의 저장소의 길이를 'n', 키의 수를 'm'이라고 가정했을 때, 평균적으로 저장소에서 1개의 해시당 (m/n)개의 키가 들어있다. 이를 'α'라고 정의한다.

m/n = α (1개의 Hash당 평균적으로 α개의 키가 들어있다.)

Open Addressing


개방주소법은 데이터의 해시가 변경되지 않았던 chaining과는 달리 비어있는 해시를 찾아 데이터를 저장하는 기법이다. 따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값이 매칭되어 있는 형태로 유지된다.
비어있는 해시를 찾는 과정은 동일해야 한다.(일정한 규칙을 따라 찾아가야 한다.)
Open Addressing 방법에는 3가지가 있다.

  • Liner Probing(선형 탐색)
    해시충돌이 일어나면, 그 다음 Hash값 혹은 몇 개를 건너뛰어 데이터를 저장한다.
    즉, 충돌이 일어나지 않을때까지 위치를 이동하여 저장한다.
    단, Hash값 충돌로 원래 위치의 다음 위치, 그 다음 위치 순으로 입력되다 보니
    데이터가 군집는 현상인 Clustering 문제가 있다.
  • Quadratic Pribing(제곱 탐색)
    해시 충돌이 일어나면 제곱만큼 위치를 건너뛰어 저장한다.
  • Double Hashing(이중 해시)
    해시 충돌이 일어나면 다른 hash 함수를 적용한 결과를 이용한다.

Open Addressing

장점
1) 또다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
2) 또 다른 저장공간에서의 추가적인 작업이 없다.
단점
1) 해시 함수의 성능에 전체 헤시테이블의 성능이 좌지우지된다.
2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해두어야 한다.

Open Addressing 시간 복잡도(Big-O)

chaining에서 정의한 'α'를 Open Addresing에서도 정의하자면, 해시 테이블의 저장소의 길이를 'n', 키의 수를 'm'이라고 가정했을때, 'α'는 1보다 작거나 같다. 저장소 1개 버킷당 1개의 값만 가지기 때문이다.

Insertion & Deletion & Search :
삽입, 삭제, 검색 모두 대상이 되는 Hash를 찾아가는 과정에 따라 시간복잡도가 계산이 된다. 해시함수를 통해 얻은 Hash가 비어있지 않으면 다음 버킷을 찾아가야 한다. 이 찾아가는 횟수가 많아지면 많아질 수록 시간복잡도가 증가한다. 최상의 경우 O(1) ~ 최악의 경우 (O(n)).

따라서 Open Addressing에서는 비어있는 공간을 확보하는 것(= 저장소가 어느 정도 채워졌을 때 저장소의 사이즈를 늘려주는 것)이 필요하다.

최악의 경우 저장소를 모두 살펴보아야 하는 경우가 생길 수 있다.(O(n))

Hash Table 제한점

  • 순서가 있는 데이터에는 적합하지 않다. 상하관계가 있거나, 순서가 중요한 데이터의 경우 Hash Table은 어울리지 않다. 순서와 상관없이 key만을 가지고 hash를 찾아 저장하기 때문이다.
  • 공간효율성이 떨어진다. 데이터가 저장되기 전에 미리 데이터를 저장할 공간을 확보하고 있어야 한다. 공간이 부족하거나 아예 채워지지 않은 경우가 생길 가능성이 있다.
  • Hash Function의 의존도가 높다. 평균 데이터 처리의 시간 복잡도는 O(1)이지만, 이는 해시 함수의 연산을 고려하지 않은 결과이다. 해시함수가 매우 복잡하다면 해시테이블의 모든 연산의 시간 효율성은 증가할 것이다.

좋은 Hash 함수란?

  • 멱등법칙(idempotent) 성질이 있어야 한다.

    멱등 법칙이란? 연산을 여러 번 적용하더라도 결과가 달라지지 않는 성질

  • Value를 저장되는 공간에서 고르게 분포할 수 있어야 한다.
    미리 확보한 공간을 효율적으로 사용할 수 있도록 Hash 충돌이 적어야 한다
  • 성능이 좋아야 한다.
  • Hash값을 보고 hash 함수의 내용이 예측되어서는 안된다.

정리

해시 테이블은 키를 가지고 빠르게 값에 접근하고 조작할 수 있는 장점이 있어서 많이 사용된다. 예를 들어 주소록 저장형태의 경우 이름 - 전화 번호의 매칭을 이용해 데이터를 처리한다.


출처

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

profile
안녕하세요 주니어 프론트엔드 개발자 양윤성입니다.

0개의 댓글