Hash 에 대한 이해
해시는 행의 위치를 결정하고 특정 행이 어디에 위치해 있는지를 알아내는 가장 빠른 기법이다. 이 말은 특정한 행이 어디에 위치해 있는지를 특정한 함수를 통해서 알아내는 것을 의미한다.
Hash Value
☞ 해시 값은 데이터를 고유하게 식별하기 위한 고정된 길이의 정수형 값
☞ 해시 값은 대용량 데이터 값을 숫자 값으로 나타내기 때문에 디지털 서명과 함께 사용
☞ 적은 리소스로도 효율적으로 데이터를 관리할 수 있으며, 하드디스크 혹은 클라우드에 존재하는 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑
☞ 해시 값은 데이터의 무결성을 판단하는데 이용
Hash Function
☞ 데이터의 효율적인 관리를 목적으로 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수
위의 그림처럼, 해시함수로 매핑하기 이전의 데이터를 Key 라고 한다. 그리고 해시 함수에 의해서 추출된 값을 해시 값 Value 라고 한다. 그리고 이 전체의 과정을 Hashing 이라고 말한다.
해시함수는 해시값의 개수보다 데이터가 더 많다. (해시 값의 개수 > 데이터의 개수)
따라서, 서로 다른 두 개의 키가 동일한 값이 추출될 수 있으며 이를 해시충돌(collision)이 발생되었다고 말할 수 있다.
현재까지 개발된 거의 모든 해시함수들은 해시충돌이 불가피하다. 사실 해시충돌을 줄이는 것도 의미가 있지만, 해시충돌이 전체 해시값에 균등하게 발생하게끔 하는 것이 더 중요하다.
Hash Table
해시테이블은 효율적인 탐색을 위한 자료구조이며, Key 와 Value 값의 형태를 가지고 있다. 해시충돌이 발생할 수 있음에도 해시테이블을 사용하는 이유는 적은 리소스를 통해 많은 데이터를 효율적으로 관리할 수 있기 때문이다.
☞ 해시함수를 사용하여 Key 를 해시값(Value) 로 매핑하고, 이 해시값(Value)을 Index 혹은 Address 로 삼아 데이터의 값과 Key 를 함께 저장하는 구조를 해시테이블이라고 한다.
☞ 데이터가 저장되는 곳을 버킷(Bucket) 또는 슬록(Slot) 이라고 한다.
해시테이블의 구현에 대해서 간단히 살피면 아래와 같이 말할 수 있다.
(1) 데이터를 가지고 해시코드를 계산한다.
(2) Hash(Key) % array.length 의 값을 구한다. 모듈러 연산을 이용, 특정 정수형 값을 가지고 온다.
(3) (2) 에서 가지고 온 값은 배열의 인덱스를 나타내며, Key 와 Value 로 이루어진 연결리스트가 존재한다. Collision 에 대비하여 반드시 연결리스트를 이용하여야 한다.
Hash Collision
앞서 말했다시피 해시충돌은 불가피하다. 서로 다른 해시값을 가지고 있는 객체가 1/(array.length) 의 확률로 같은 해시버킷/해시슬롯을 사용하게 되기 때문이다. 이러한 충돌이 발생하더라도 Key/Value 값을 잘 저장하고 조회할 수 있는 방식이 두 가지가 있다.
☞ Separate Chaining
☞ Open Addressing
이 두가지 기법을 살펴보자.
Separate Chaining
하나의 버킷에 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써, 모든 자료를 해시테이블에 담는 방식이다. 해당 버킷에 데이터가 이미 존재한다면 하나의 노드를 더 추가하여 연결리스트를 구현, 데이터를 추가한다. 저장되는 데이터는 연결리스트 Head 에 추가된다. 시간복잡도는 추가 시 O(1) 이고, 탐색시 O(n) 이다.
Separate Chaining )
Hash Function : hash(x) = x mod 7
Keys = { 50, 700, 76, 85, 92, 73, 101 }
- Simple to implements,
☞ 쉽게 구현이 가능하다.
- Hash table never fills up, we can always add more elements to chain,
☞ 해시 테이블은 가득차지 않는다. 체이닝을 통해서 더 많은 요소들을 추가할 수 있다.
- Less sensitive to the hash function or load factors,
☞ 해시함수나 로드팩터(부하) 에 덜 민감하다.
- It is mostly used when it is unknown how many and how frequently keys may be inserted or deleted,
☞ 얼마나 자주 키가 삽입/삭제 연산을 수행하는지 모르는 경우, 자주 사용된다.
- Cache performance of chaining is not good as keys are stored using linked list.
☞ 연결리스트를 통해 키를 저장하기 때문에 캐시 성능이 좋지 못하다.
- Wastage of Space.
☞ 공간의 낭비. (메모리적인 측면)
- If the chain becomes long, then search time can become O(n) in worse case.
☞ 체이닝이 길어지면, 데이터 탐색 연산 시 워스트 케이스로 시간복잡도 O(n) 이 된다.
Open Addressing
하나의 버킷에 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다. 해시함수로 얻은 주소뿐만 아니라 다른 주소로도 데이터를 저장할 수 있음을 말한다. 만약에 해시함수로 얻은 주소에 데이터가 들어가있는 경우, 해시충돌이 발생하기 때문에 해당 데이터는 다음 주소 중에서 비어있는 버킷에 데이터가 저장되게 된다.
open addressing 에서 해시충돌을 해결하기 위한 probing(탐사/조사) 방식이 세가지가 존재한다.
(1) Linear Probing
(2) Quadratic Probing
(3) Double Hashing
그리고 위 세가지 방식에 대한 세가지 연산(Insert / Search / Delete) 을 살펴보자.
Open Addressing, Collision 해결 방법 1) Linear Probing
h_i(X) = ( Hash(X) + i ) % HashTableSize
if h_0 = ( Hash(X) + 0 ) % HashTableSize is full, we try for h_1
if h_1 = ( Hash(X) + 1 ) % HashTableSize is full, we try for h_2
if h_2 = ( Hash(X) + 2 ) % HashTableSize is full, we try for h_3
... 이하 생략
최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있다면, 해당 해시값에서 고정폭을 정하여서 해당 버킷으로 이동한 뒤, 액세스 연산을 수행한다. 여기서 옮긴 버킷에도 데이터가 존재하는 경우 버킷을 해시값이 없을 때까지 고정폭만큼 이동시켜 데이터 액세스 연산을 수행한다.
위의 그림은 Linear Probing 의 과정을 설명한다. 충돌이 일어났을때는 고정폭만큼 해당 버킷으로 이동하여 데이터를 삽입하고 있음을 확인할 수 있다.
Open Addressing, Collision 해결 방법 2) Quadratic Probing
이전에 보았던 Linear Probing 이랑 별반 다르지 않다. 고정폭을 (+1) 로 하는 것이 아닌, 제곱승으로 한 것이다. 따라서 위의 Linear Probing 과의 예시처럼 Keys 가 주어지고 해시충돌시 고정폭을 제곱시켜 가며 빈 버킷에 데이터 액세스 연산을 수행하는 것이다.
Open Addressing, Collsion 해결 방법 3) Double Hashing
두 개의 해시함수를 이용하여 해시충돌을 피하는 방식이다. 위의 식과 같이 Hash1(x) 와 Hash2(x) 함수를 이용한다. 두번째 해시함수를 살펴보면 값은 PrimeNumber 소수를 이용하며 해당 값은 해시테이블의 사이즈보다 작아야 한다. 앞선 두 개의 내용 Linear 와 Quadratic 은 고정폭을 이용하는 반면 해당 값은 가변적인 폭을 이용한다.
왜 이중으로 해시함수를 사용하는가.
앞선 두 개의 방식은 해시충돌은 피할 수 있을지라도 해시충돌을 피하기 위해서 값을 할당하는 방식이 고정적이여서 한쪽으로 값이 치우칠 수 밖에 없다.
타 블로그를 본 결과 다들 클러스터링 문제라고 하였다. 앞서 말했다시피 해시충돌은 불가피하기 때문에 이 해시충돌로 생긴 값을 얼마나 균등하게 저장시킬 수 있는지가 관건이기 때문에 이중해시(Double Hashing) 방법을 사용하는 것이다.
'알아두면 쓸모있는 SW 지식' 카테고리의 다른 글
| 20200602 서버리스란. (0) | 2020.06.03 |
|---|---|
| 20190717 API 란 무엇인가? (0) | 2019.07.17 |
| 20181025 대칭키 & 비대칭키 (수정 : 20190309) (0) | 2018.10.25 |
| 20181024 빅엔디안 & 리틀엔디안 (0) | 2018.10.24 |
| 20180112 프로그래밍 언어? (0) | 2018.01.12 |
