[] 해시와 해시 테이블, 해시 충돌

python dictionary를 공부하던 중, 해시와 관련된 개념을 접하게 되었습니다.

어렴풋이 알고 있었지만 유용한 내용을 많이 알게 되어서 정리해볼까 합니다.

 

해시, Hash란

해시는 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값을 말합니다. 방금 설명했듯이 고정된 길이를 가진다는 점 외에도 여러 특징이 있습니다.

해시 함수 h에 대해 x1!=x2 이면 h(x1)!=h(x2)

해시는 임의의 두 값이 다르면 각각에 대한 해시값도 다릅니다. 값이 조금 차이난다고 해서 해시값도 조금 차이나는 것이 아니라 일정한 규칙 없이 큰 차이가 벌어집니다.

물론 이는 완벽하게 성립하지 않고 예외가 존재합니다. 뒤에서 다시 설명하도록 하겠습니다.

그렇기 때문에 무결성을 보장하기 용이합니다.

무결성이란 데이터의 정확성과 일관성을 유지하고 보증하는 것을 말합니다. 우리가 다양한 데이터를 만들었을 경우, 해당 데이터들은 길이도 형태도 제각각입니다. 하지만 이를 해시하게 되면 모두 같은 길이의 데이터가 되죠. 따라서 제각각의 데이터를 확인하며 무결성을 확인하는 것보다 균일화된 해시값을 통해 무결성을 확인하는 것이 훨씬 용이하겠죠.

 

1-wayness

해시함수 h에 대해 x로부터 h(x)를 구하는 것은 쉽고 h(x)값으로 x값을 얻는것은 어렵습니다. 이는 보안적으로도 굉장히 중요한 사안이기 때문에 실제 암호 알고리즘에서 해시를 많이 사용하고 있습니다.

 

비둘기집 원리

위에서 설명했듯이 해시 알고리즘은 고정된 길이의 데이터로 매핑을 합니다. 그렇기 때문에 해시값은 유한합니다. 고정된 길이를 128비트라고 하면 2^128만큼의 경우의 수를 표현할 수 있고 이는 매우 큰 숫자이지만 결국 유한한 숫자입니다. 즉 낮은 확률이겠지만 비둘기집 원리에 의해 두 입력 값의 결과가 달라도 같은 해시값이 나올 수 있습니다. 이를 해시 충돌 이라고 하며 뒤에서 더 자세히 알아보겠습니다.

 

해시 테이블

많은 언어의 자료구조에서 해시 테이블을 사용하고 있습니다. 위에서도 언급했듯이 python 언어의 dictionary 자료구조도 내부적으로 해시테이블을 사용하여 구현이 되어 있습니다.

해시 테이블은 어떤 특징이 있는지 왜 해시테이블을 사용하는지에 대해서 알아봅시다.

해시 테이블

key-value

해시 테이블은 위 그림과 같이 key-value store입니다. 기존의 키가 해시함수를 거쳐 해시값이 되면 이를 해시테이블의 키로 사용하게 됩니다.

 

space-time tradeoff

해시테이블을 사용하면 삭제, 삽입, 수정, 검색 등의 연산을 O(1) 만에 수행할 수 있습니다. 해당 되는 키를 해시함수만 거치게 되면 바로 값에 접근이 가능하죠. 그렇다면 해시테이블을 통해 자료구조를 구현하는 것이 무조건 좋을까요?

그렇지 않습니다. 해시테이블은 시간을 줄인 만큼 많은 메모리를 사용하게 됩니다. python과 같은 경우는 데이터가 들어갈 수 있는 공간의 1/3은 항상 비워두기 위해서 해시테이블의 항목이 많아지면 더 큰 메모리에 할당하여 공간을 확보합니다.

여유공간이 왜 필요한지에 대해서는 뒤에 해시 충돌에서 설명하도록 하겠습니다.

 

해시 충돌

위에서도 언급했듯이 해시는 고정된 길이를 가진 데이터로 매핑을 하고 이는 유한하기 때문에 비둘기 집 원리에 의해서 서로 다른 값도 같은 해시값을 가질 수 있습니다. 이를 해시 충돌이라고 하죠.

해시 충돌이 날 경우에는 어떠한 방식으로 해결을 해야할까요? 기존의 값을 덮어써야할까요?

다행히도 여러 처리 방법이 존재합니다.

Open addressing

Open addressing 방식은 해시 충돌이 난 경우 기존의 해시와 다른 위치에 저장합니다. 다른 위치를 지정하는 방식도 어려 방법이 존재합니다.

• 선형 탐사 : 단순하게 다음 칸을 조사하고 비어있으면 해당 위치에 저장
• 제곱탐사 : i^2 번째 칸을 조사하고 비어있으면 해당 위치에 저장 (i=1부터 비어있는 칸을 찾을 때까지 증가)
• 이중 해시 : 해시 함수 두 개를 사용하여 1번 해시 함수를 주로 사용하다가 해시 충돌 발생 시 2번 해시 함수를 사용하는 방법

python dictionary가 데이터가 들어갈 수 있는 공간의 1/3은 항상 비워두는 이유를 이제 설명할 수 있습니다. 들어갈 수 있는 공간이 얼마 남지 않았다면 해시 충돌이 잦아지고 본인의 해시에 맞지 않는 위치에 들어가는 데이터들이 점점 많아질 것입니다. 이는 더 많은 해시 충돌을 야기하겠죠.

 

Close addressing

Close addressing 방식은 해시 충돌이 발생하더라도 같은 위치에 저장합니다.

• 버켓 : 배열의 한 칸을 다시 배열로 만들어 여러 값을 저장할 수 있게 변경
• 체이닝 : 배열의 한 칸을 linked list로 만들어 여러 값을 저장할 수 있게 변경

 

Open addressing VS Close addressing

그렇다면 두 방법 중 어느 방법이 더 좋을까요?

정답은 없지만 몇 가지 측면에서 비교해봅시다.

	Open addressing	Close addressing
메모리	기존의 해시테이블만을 사용	추가적인 메모리 필요
많은 데이터	해시와 맞지 않는 위치에 데이터가 점점 많아져서 급격한 성능저하	선형적인 성능저하
복잡도	해시 충돌시 어느 위치에 저장해야할 지 적절한 알고리즘 필요	연결리스트 구현 정도의 가벼운 복잡도