[해시] 이론

zzase·2021년 12월 17일

hash 해시

[블록체인] 기본 이론

목록 보기

2/7

정의

블록체인 개발을 공부하기 앞서 반드시 알아야 할 것 중 하나인 해시함수.

해시함수의 간단한 정의는 "어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 내는 함수"이다.

이 그림은 해시함수를 '깔때기'에 비유한 그림인데 아주 적절한 비유이다. 그 이유를 수학적 정의와 함께 설명하려 한다.

1. 적은 비용
어떤 입력 x에 대하여 hash(x)는 계산하기 쉬어야 한다.

말 그대로 우리는 해시 알고리즘을 이용하여 해시값을 도출하려 할 때 그 과정이 어려우면 안 된다는 말이다.

깨끗한 물을 얻기 위해 깔때기에 불순물이 섞은 물을 집어넣는 것이 어려운 일인가?
단지 부으면 끝나는 일인 것처럼 그 계산도 오래 걸릴지라도 어렵지 않아야 한다는 말이다. ~~(근데 어렵다)~~

2. 단방향성
hash(x)=y 일 때 우리는 y만 가지고 x를 알 수 없어야 한다.
이 말 또한 깔때기에 비유하여 쉽게 이해할 수 있다. 만약 지나가는 누구를 붙잡아서 " 이 깨끗한 물이 원래 무슨 물인지 알 수 있겠나요?"라고 묻는다면 누가 정확한 대답을 할 수 있을까?

그 누구도 깨끗한 물이 원래 어떤 물이었는지 알 수없다.
또한 단방향성을 다르게 해석하면 양방향이 아니다. 즉 역추적이 불가능하단 말이 된다.
마찬가지로 깔때기에 비유하자면 출구 쪽에 물을 넣는다고 해서 다시 다른 물로 돌아가진 않는단 소리다.
이게 바로 해시함수, 해싱의 존재 이유이다.

3. 충돌 저항성
동일한 해시값에 대하여 서로 다른 입력값을 찾는 것은 불가능하다.

해시함수의 특성상 입력값은 무한해도 출력 값에는 그 한계가 존재한다. 따라서 입력값이 달라도 그 출력 값이 같게 나올 수 있다는 말이다.

하지만 출력값이 같더라도 그 구성은 달라야 한다.

"소금물과 설탕물을 깔때기에 넣어도 그 결과는 물이어도 다른 물이어야 된다."라는 것과 같은 이치라고 생각하면 이해하기 편할 것 같다.

그래서 해시함수는 hash(a) = hash(b) 일 때 a와 b를 발견하는 것이 계산적으로 불가능해야 한다.

알고리즘

해시함수의 기본적인 이론이 이해가 됐다면 이제 그 구체적인 과정인 알고리즘을 알아야 한다.
알고리즘을 설명하기 전에 용어에 대한 정리가 필요하다.

깔때기 = 해시 함수
불순물 = 입력값 = 키(key)
정화된 물 = 해시값
전체 과정 = 해싱(Hashing)

그럼 지금부터 우리는 '해싱'이라는 과학실험을 한다고 생각해보자.

학교다닐 때 했던 과학실험을 떠올리며 우리의 실험 결과 보고서를 생각해보면 '실험전','실험과정' '실험 후 결과' 항목이 있었다.

그렇다면 해싱이라는 과학실험의 보고서에서 '실험전'과 '실험 후 결과'는 어디에 해당할까? 바로 키와 해시값에 해당할것이고, '실험과정'은 해시함수에 해당할 것이다. 또 실험을 했으면 그 결과물또한 보관하지 않는가? 이 때 우리는 해싱에서 얻은 결과물(해시값)을 보관하는곳을 버킷(bucket) 또는 슬롯(slot)이라 부른다

이때 버킷에 저장되는 결과물은 index와 실제 data로 저장되는데 index가 바로 해시값이 되며 data는 결과물 그 자체가 된다. (실험전,실험결과물) 라는 한 쌍이 있을 때 우리는 언제든지 실험결과를 쉽게 찾을 수 있게 번호를 매기고 버킷이라는 보관함에 보관한다. 만약 번호가 11번이라면 아래 그림처럼 11번(index)를 열면 결과물(data)를 확인할 수 있다.

그리고 우리는 이 항목들이 적혀있는 실험 보고서와 결과물(버킷)을 함께 선생님께 제출했을텐데 이 전체를 해싱 알고리즘에서는 해시테이블(hash table)이라 부른다.
즉, 해시테이블은 키,해시함수,해시값,저장소로 이루어져있는 것이다.

이게 보통 해시테이블의 구조다. 사람이름과 전화번호를 같이 저장하는데

사람이름이 key가 되고 전화번호가 우리가 저장하는 data가 된다.

우리는 그럼 'john smith'의 전화번호를 버켓에 저장하기위해 hash_function("john smith")를 실행하면 2번이라는 해시값, 인덱스를 얻게되고 버켓의 2번인덱스와 함께 '521-1234'라는 전화번호 정보를 저장하는 것이다.

그럼 이제 여기서 왜 2번 인덱스인지 질문할 수 있는데 당연히 규칙이 있고 근거있는 번호다.

위 버켓을 보면 번호가 0~15까지 총 16개의 데이터양을 저장할 수 있는 구조다. 그렇다면 index는 나머지 연산을 활용하여 구하는데 식은 index = hash_function("john smith")%16 가 된다. 이렇게 한번 데이터를 저장하면 우리는 같은 실험에 같은 실험결과를 얻기위해 또 실험할 필요없이 저장된 번호를가지고 실험결과를 찾는 것처럼 index만 가지고 데이터를 안전하게 찾을 수 있는 것이다.

하지만 이러한 저장방식(나머지 연산)때문에 간혹 다른 키값임에도 동일한 인덱스가 나올 수 있다.

이러한 경우를 해시충돌이라 하는데 이런 문제점을 해결하기 위해 다양한 방법이 제시되어 있다.

해시충돌 해결방안

1. Direct-address Table
테이블의 크기와 키의 개수가 동일한 테이블

위 그림처럼 테이블과 키의 개수가 동일하면 충돌은 일어나지 않지만 실제로 사용하는 키는 2,3,5,8 총 4개인데 나머지 사용하지 않는 6개의 키들을 위한 공간을 마련해야 한다는 점에서 메모리 효율성이 떨어진다는 단점이 존재한다.

위의 그림은 예시일 뿐 실제로는 방대한 데이터를 사용하기 때문에 실제로 이 테이블은 거의 사용하지 않는다.

2. Separate Chaining
동일한 버킷에 값이 있으면 Linked List로 해당 value를 뒤에 저장하는 방식

첫번째로 고안해낸 방법은 바로 이 체이닝(chaining)이라는 것인데 아주 간단한 생각에서 비롯됐다.

"인덱스가 동일하여 버킷에 두개가 못들어가니 두개가 들어가도록 늘리면 되지 않나?"라는 생각이다.
이런 생각은 곧 자료구조중 하나인 연걸리스트(linked list)를 사용하여 구현 가능했다.
바로 버킷에 바로 데이터를 저장하는게 아니라 다음 노드를 가리키는 포인트를 넣고 노드에 데이터를 저장하는것.

해시충돌이 일어나서 한 인덱스에 두개의 데이터가 들어가게되면 첫번째 데이터가 들어가있는 노드는 다음 데이터를 저장할 노드를 가리키는 포인터를 생성하고 가리키는 노드에 두번째 데이터를 저장하면 되는것이다.

위 그림처럼 john smith의 번호를 152번 인덱스에 저장했는데 그다음 sandra dee의 번호도 152번에 저장해야될 때,john smith의 데이터가 저장된 노드는 그 다음 노드를 가리키고 그 노드에 sandra dee의 데이터를 저장했다.

이 때 다음 노드를 저장하는 위치가 head일때랑 tail일때랑 그 시간복잡도가 다른데 head일 때의 삽입시간은 O(1), tail에 저장할 경우는 O(n)이다.

이 방법은 매우 훌륭한 방법이지만 이 역시 단점은 존재한다.

바로 linked list의 구조상 추가할 수 있는 데이터의 수에 제약이 있다는 것이다.

실제로 JDK에서도 이 방법을 사용하여 해시충돌을 예방하는데 데이터의 수때문에 linked list가 아닌 tree를 이용함으로써 그 성능을 높였다. 만약 저장하는 데이터가 8개이하면 linked list, 그 이상이면 tree를 사용한다고 한다.

3.Open Addressing
open addressing(개방주소법)은 체이닝기법과 달리 해시충돌이 일어나면 체이닝 처럼 하나의 해시(index)에 여러 데이터를 넣는게 아닌 탐색 기법을 활용하여 충돌이 일어난 곳을 기준으로 가깝고 비어있는 해시에 채워넣는 기법.