Hash에 대해서

2019-10-23

Hash란?

특정한 데이터를 이를 상징하는 더 짧은 길이의 데이터로 변환하는 행위이다.

HashTeble

내부적인 배열을 사용하여 데이터를 저장하는 자료구조로 검색과 저장이 매우 빠르다.

데이터를 검색할 때 key를 통해 고유의 인덱스로 접근하기 때문에 빠르게 진행될 수 있는 것이다. 항상 그런 것은 아니지만 검색과 저장의 평균적인 시간 복잡도는 O(1)이다.

Hash Table(해시 테이블)

해시함수를 이용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 한다.

Hash Function(해시 함수)

해시함수란 데이터의 효율적인 관리를 목적으로 임의의 저장할 데이터를 고유한 숫자 데이터로 매핑하는 함수이다. 매핑 전 원래 데이터 값을 키(key)라 하고, 매핑 후 데이터 값을 해시값(hash value)이라 한다. 이러한 매핑 과정을 해싱(hashing)이라 한다.

하지만 해시함수는 두 개의 서로다른 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생할 수 있다. 그렇게되면 같은 곳에 저장할 수 없게된다.

Collision이 많아질수록 Search에 필요한 시간복잡도가 O(1)에서 O(n)에 가까워진다. 해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서이다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다.

Collision 해결

기본적인 두 방법을 알아보자.

  • Open Address 방식(개방주소법)
    해시 충돌이 일어나면, 다른 해시 버킷(bucket)에 해당 자료를 삽입하는 방식이다. 정해진 해시테이블내에서만 저장되므로 Closed Hashing(폐쇄 해싱)이라고도 한다. 대표적으로 세가지 방식이 있다.
    1. 선형탐색(Linear Probing) : 해시충돌 시 순차적으로 탐색하여 비어있는 버킷에 데이터를 삽입한다.
    2. 제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입한다. Ex)1,4,9,16 …
    3. 이중 해시(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용한다. HashTable
  • Separate Chaining 방식(분리연결법)
    해시 충돌이 일어나면, 주어진 해시테이블 공간외에 새로운 공간을 할당하는 방법이다. Open Hashing(개방해싱)이라고도 한다. 대표적으로 두가지 방식이 있다.
    1. 연결 리스트를 사용하는 방식(Linked List) 각각의 버킷들을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 버킷의 list에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하지만 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담된다.
    2. Tree를 사용하는 방식 (Red-Black Tree) 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할지 트리를 사용할지에 대한 기준은 하나의 버킷에 할당된 key-value 쌍의 개수이다. 데이터 개수가 적다면(6개, 8개) 링크드 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. HashTable

Open Address VS Separate Chaining

Open Address 방식(개방주소법): 연결된 공간에 데이터를 저장하기 때문에 분리연결법에 비해 캐시효율이 높다. 따라서 데이터의 개수가 충분히 적다면 개방주소법 방식이 성능이 더 좋다.

Separate Chaining 방식(분리연결법): 개방주소법은 분리연결법에 비해 버킷을 계속해서 사용한다. 따라서 분리연결법 방식은 테이블의 확장을 보다 늦출 수 있다.

  • 테이블의 확장은 매우 심각한 성능의 저하를 나타낸다. 가급적 확장을 하지 않도록 테이블을 설계하고 제어하는 방법이 필요하다.

출처

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ https://k39335.tistory.com/18 https://preamtree.tistory.com/20 https://galid1.tistory.com/170