Hash에 대해서

Object 클래스의 메서드 중 equals와 hashCode는 해시 기반 자료구조를 사용하였을 때 이점을 가져다준다고 했었다. 해시란 무엇이고, 해시 기반의 자료구조와 equals와 hashCode는 해시 기반 자료구조에서 왜 중요한지 알아보려고 한다.

---

해시 (Hash, Hash Function, Hashing)

Hash Function(해시 함수)은 임의의 길이의 데이터(key)를 고정된 길이의 데이터(hash)로 변경해주는 함수이다.

이 과정을 Hashing(해싱)이라고 하며, 해시 함수에 의해 나온 결과 값이 Hash(해시)이다.

 

해시 함수의 특징

어떠한 입력값에도 항상 고정된 길이의 해시값을 출력한다.

해시 알고리즘의 종류 에 따라 결과값에 대한 길이는 정해져있으며, 다음 사이트에서 해시 알고리즘에 따라 테스트를 진행해볼 수 있다.

https://www.functions-online.com/hash.html

test hash online - cryptographic PHP functions - functions-online

md5 알고리즘 사용하였을 때
input : 안녕하세요.
output : 2892f63d8bb4e7b5b2ecc68556d66cb2

input : 안녕하세요. md5 알고리즘을 사용해봅니다.
output : d6a62e0f223eaec17f7b25b414be83d9

결과 값은 16진수로 표현되며, 입력 값의 길이의 상관 없이 출력 값에 대한 길이가 고정된 것을 확인할 수 있다.

 

동일한 입력값에 대해 항상 동일한 출력값을 출력한다.

해시 함수는 일방향 함수로 설계되어있기 때문에, 해시값을 통해 원래 입력값을 역추적할 수 없다. 이를 불가역성(One-way-Property)라고 한다.

위에서 테스트 한 내용을 기반으로 몇 번 테스트를 진행해보아도 동일한 값을 출력한 것을 확인할 수 있다.

 

서로 다른 입력값에 대해 동일한 출력값을 생성할 수 있다.

이를 해시 충돌(Hash Collision)이라고 하는데 밑에서 설명하도록 한다.

 

해시 충돌 (Hash Collision)

두 개 이상의 서로 다른 입력값이 같은 해시값을 생성하는 상황이다.

해시 함수는 무한한 입력값을 받을 수 있지만, 출력값은 항상 고정된 크기를 갖기 때문에 충돌이 발생할 수 있다.

 

위에서 언급한 해시함수 중 MD5 알고리즘은 결과 값의 크기가 128bit로 고정되어있으며, 2^128개의 고유한 해시 값을 표현할 수 있다. 하지만 입력값은 2^128개를 넘을 수 있기 때문에 충돌이 발생할 수 있다.

비둘기집 원리에 의하면, 제한된 수의 해시값은 무한한 입력값을 저장하려면 적어도 하나의 해시값에 두 개 이상의 입력값이 저장될 수밖에 없다. 즉, 해시 충돌은 항상 발생할 수 있다.

따라서, 해시 충돌을 방지할 수는 없으며 충돌이 발생할 가능성을 최소화하는 해시 함수를 사용하는 것이 좋다.

 

해시 충돌 해결 방법

해시 기반의 자료구조인 HashTable 에 대한 해시 충돌 해결 방법이다.

(HashTable에 대해서는 다음 포스팅에서 설명한다.)

Separate Chaining

충돌이 발생하면, 각 버킷에 LinkedList와 같은 자료구조를 사용하여 저장 공간을 확장하는 방법이다.

이 방법은 해시 충돌이 발생한 경우(같은 해시값을 가지는 키들이 존재할 때), 해당 버킷에 LinkedList를 활용하여 여러 개의 key-value 쌍을 저장할 수 있도록 해준다.

 

위 그림에서 tucson hybrid와 ioniq6는 해시함수의 결과로 해시값 2에 매핑된다.

Separate Chaining 기법에 따르면, 두 입력값은 동일한 해시값에 저장할 수 있다.

tucson hybrid를 먼저 저장한다고 가정해보면, 해시값이 2인 버킷에 대해 LinkedList를 생성되고 첫 번째 노드에 tucson hybrid의 key-value가 저장된다. 버킷은 생성된 LinkedList의 주소 값을 저장하고 있는다.

그 후 ionicq6를 저장할 때, 이 역시 해시값이 2인 버킷에 저장하려고 한다. 하지만 해당 버킷에 대한 LinkedList는 존재하므로 두 번째 노드에 추가된다.

 

Open Addressing

충돌이 발생하면, 버킷 내에서 데이터를 사용되지 않는 배열의 위치로 이동시키는 방법이다.

배열의 빈 공간을 사용하기 때문에, LinkedList와 같은 추가적인 메모리 공간을 사용하는 Separate Chaining에 비해 메모리 측면에서 효율적이다.

 

Linear probing (선형 탐사)

현재의 버킷으로부터 고정된 간격만큼 가장 가까운 다음 버킷을 찾아 데이터를 저장한다.

기본 간격은 1로 설정된다.

위 그림에서 tucson hybrid와 ioniq6는 해시함수의 결과로 해시값 2에 매핑된다.

tucson hybrid를 먼저 저장한다고 가정해보면, 해시값이 2인 버킷에는 tucson hybrid의 데이터가 저장된다.

그 후 ionicq6를 저장할 때, 이미 해시값이 2에 데이터가 존재하므로 때문에(충돌 발생) 해당 다음 버킷인 해시값 3을 확인한다. 해시값이 3인 버킷이 비어있으므로 3번 버킷에 데이터를 저장한다.

충돌이 발생하면, 다른 버킷을 고정된 간격으로 다른 버킷을 탐색하여 비어있다면 데이터를 저장한다.

단점; 클러스터링 문제

 

Quadratic probing (제곱 탐사)

현재의 버킷으로부터 n² 형태로 탐색 간격을 증가시킨다.

탐색 간격은 H+1², H+2², H+3², ... , H + k² 으로 계산된다. (H는 hash를 의미한다.)

https://stackoverflow.com/questions/27742285/what-is-primary-and-secondary-clustering-in-hash

 

해시값이 7인 버킷에서 충돌이 발생했다면, 위 수식에 의해서 인덱스 계산을 하여 탐색을 진행한다.

첫 번째로 8(7+1²)가 되고 두 번째로 11(7+2²), 세 번째로는 16(7+3²)이 되는 것처럼 말이다.

단점; 특정 패턴이 반복되면 비효율적

 

Double hashing (이중 해싱)

두 개의 해시 함수를 사용하여, 첫 번째 해시 함수에서 충돌이 발생하면 두 번째 해시 함수로 새로운 인덱스를 계산한다.

 

해시를 사용하는 기술

 

 

자료구조에서 Hash를 왜 사용하는 것일까?

데이터를 빠르고 효율적으로 관리하기 위해 사용한다.

해시함수를 통해 나온 해시(인덱스)를 사용하면 데이터에 대해 검색, 삽입, 삭제 기능에 대하여 빠른 속도로 처리할 수 있기 때문이다.

해시를 사용하는 자료구조인 HashTable과 다른 자료구조들의 시간 복잡도를 확인해보면 이해가 간다.

https://www.reddit.com/r/csharp/comments/tzrw17/is_there_a_time_complexity_data_structure_cheat/?rdt=47405

HashTable 자료구조의 평균 시간복잡도가 해시를 사용하지 않은 자료구조에 비해 빠르다는 것을 알 수 있다. 하지만 이는 평균적인 상황에 대한 것으로, 해시를 사용하였을 때 최악인 경우에는 O(n)의 속도가 걸린다. (해시 충돌로 인한 이슈)

 

---

해시를 사용하는 기술 중 데이터베이스에서 해시는 어떻게 동작하는지 알아봐야겠다.

이어서, 해시 기반 자료구조에 대한 포스팅이다.

2024.11.09 - [Language/Java] - 자바의 Hash 기반 자료구조

자바의 Hash 기반 자료구조

 

TODO. 해시 충돌 발생하였을 때 코드 구현해보기

---

참고

https://en.wikipedia.org/wiki/Hash_table

Hash table - Wikipedia

 

https://en.wikipedia.org/wiki/Open_addressing

Open addressing - Wikipedia