[자료구조] Hash

Hash란?

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.
- wikipidia

해시 테이블 토는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다.
- 팀스파르타 알고리즘 강의

• 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.
• Hash의 용도 중 하나는 Hash table이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 사용된다.

Hash는 잘게 다진 고기라는 뜻의 유래로서, 간단하게 설명하면

해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조이다. 단순하게 key - value로 이루어진 자료구조라고 생각하면 된다.
핵심은 고유값인 Key를 준다는 것이다.

Hash function

• Hash Function은 key를 고정된 길이의 Hash로 변경해주는 역할을 하며, 이 과정을 hashing이라고 한다. key를 hash function에 input으로 넣어서 Output으로 나오는 것이 Hash라고 생각하면 되고, 이 Hash가 저장 위치가 된다고 생각하면 된다.
• Load Factor : 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다. 즉, 방이 얼마 차있냐..
• Load factor = n / k
• 로드 팩터 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야할 지를 결정한다. 자바 10 에서는 해시맵의 디폴트 로드 팩터를 0.75로 정했으며, ‘시간과 공간 비용의 적절한 절충안’이라고 얘기한다.
• 일반적으로 로드 팩터가 증가할 수록 해시 테이블 성능은 점점 감소하게 된다.

Hash Table의 구성

• key
  • 고유한 값, hash function의 Input이 된다.
  • key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야한 공간도 따로 마련해야 하기 때문에(key의 길이가 제각각 일수 있다.), 고정된 길이의 해시로 변경한다.
• hash function
  • key를 고정된 길이의 hash로 변경해주는 역할을 한다.
  • 서로 다른 key가 hashing 후 같은 hash값이 나오는 경우가 있다. 이를 해시충돌이라고 부른다. 해시 충돌 발생확률이 적을 수록 좋다.
  • 해시충돌이 균등하게 발생하도록 하는것도 중요하다. 모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해져서 좋지 않다.
• value
  • 저장소(버킷,슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어진다.
• hash table
  • 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.
  • 데이터가 저장되는 곳을 버킷, 슬롯이라고 한다.

해시는 색인 또는 인덱스, hash function은 key->hash로 만들어 주는 함수, 해시테이블은 hash를 주소로 삼아 데이터를 저장하는 자료구조이다.

Hash의 시간 복잡도

• 평균 시간복잡도
  • 해당 키를 기반으로 배열에서 인덱스로 접근하듯이 접근할 수 있어서 평균적으로 O(1)의 시간 복잡도를 갖는다.
  • 참조 : O(1)
  • 탐색 : O(1)
  • 삽입 / 삭제 : O(1)
• 최악의 시간복잡도
  • 만약 해시테이블에서 충돌이 많이 일어난다면 해당 해시값이 같은 모든 요소들을 탐색해야 하므로 O(n)의 시간복잡도가 걸린다.
  • 참조 : O(n)
  • 탐색 : O(n)
  • 삽입 / 삭제 : O(n)

Hash collision(해시 충돌)

• 만약 A, B 두가지 key가 있는데, hash 값을 얻으니 hash가 2로 똑같이 나오는 경우, 이런 현상을 hash Collision이라고 한다.
• 해시 함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1로 매핑되어야 하는 해시 테이블의 특성에 위배된다. 해시 충돌은 필연적으로 나타날 수 밖에 없다.

Birthday paradox

• 해시 테이블의 충돌 문제는 “거의 무조건” 일어난다.
• 아주 아주 큰 테이블을 형성한다 해도 birthday paradox에 의해 충돌이 발생될 확률은 높습니다. 예를 들어 같은 방에 생일(총 365일 중에 한개겠죠?)이 같은 사람이 두 명 이상 있을 확률이 50%가 되려면 방에 23명밖에 없어도 됩니다.

1. Chaining

체이닝은 저장소(Bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다.

• 장점
  • 미리 충돌을 대비해서 공간을 많이 잡아놓을 필요가 없다. 출돌이 나면 그때 공간을 만들어서 연결만 해주면 된다.
• 단점
  • 같은 hash에 자료들이 많이 연결되면 검색시 효율이 낮아진다.
• Java 8 이상에서는 요소의 수가 특정 임계값을 초과하면 연결리스트가 아닌 레드 블랙트리를 HashMap에 사용한다고 알려져 있다
• 이를 통해 O(n) → O(log n)으로 시간복잡도를 개선했다고 한다.

2. Open Addressing(개방주소법)

개방 주소법은 충돌이 일어나면 비어있는 hash에 데이터를 저장하는 방법이다. 개방주소법의 해시 테이블은 hash와 value가 1:1관계를 유지한다.

• 위의 그림에서 John과 sandra의 hash가 동일해 충돌이 일어난다. 이때 Sandra는 바로 그 다음 비어있던 153 hash에 값을 저장한다. 그 다음 Ted가 Table에 저장을 하려 했으나, 본인의 hash에 이미 Sandra로 채워져 있어 Ted도 Sandra처럼 바로 다음 비어 있던 154 hash에 값을 저장한다.

→ 이런 식으로 충돌이 발생할 경우 비어있는 hash를 찾아 저장하는 방법이 개방주소법이다. 이때, 비어있는 hash를 찾아가는 방법은 여러가지가 있다.

3. Hash 함수 Mapping 개선

특정 값에 치우치지 않고 해시 값을 고르게 만들어내는 해시 함수가 좋은 해시함수라고 할 수 있다.

• division method
  • 가장 기본적인 해시 함수이다. 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 변환한다. 간단하면서도 빠른 연산이 가능한 것이 장점이다.
  • 해시의 중복을 방지하기 위해 테이블의 크기 m은 소수로 지정해서 사용하는것이 좋다. 하지만 남는 공간이 발생해 메모리상으로 비효율적이다.
• multiplication method
  • 숫자 키 k, A는 0<A<1 사이의 실수 일때 `h(k) = (ka mod 1)*m 으로 계산한다.
  • 2진수 연산에 최적화된 컴퓨터구조를 고려한 해시함수이다.
• univeral hasing
  • 여러개의 해시함수를 만들고, 이 해사함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법.
  • 서로 다른 해시함수가 서로 다른 해시값을 만들어내기 때문에 같은 공간에 매핑할 확률을 줄이는 것이 목적

Python의 딕셔너리도 Hash형 자료구조인데, 오픈 어드레싱을 사용했다.

로드 팩터가 0.8 넘어가지 않는 선에서는, 선형 탐색의 성능이 더 좋기 때문

참고

스파르타코딩클럽 알고리즘 강의

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

https://go-coding.tistory.com/30