개발 etc
해시(hash) 넌 누구냐?
묠니르묘묘
2023. 1. 2. 14:29
최근 CS 학습을 하다보니 해시가 많이 보였습니다.
- DB 조인 알고리즘에서의 해시 조인(Hash Join)
- Java의 HashMap
- Java의 hashcode()
- 자료구조의 해시 테이블(Hash Table)
- C++에서 정렬을 보장하지 않고 해시 테이블을 구현할 때 쓰는 unordered_map
- 암호화 해시 함수
- ...
🤔 도대체 해시는 어떤 것이길래 이렇게 많이 보이는 걸까요?
🚀 해시 넌 누구냐?
- 해시 함수(Hash Function)라고도 불림
- 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수
- 즉, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수
- 단방향 함수이기에 출력된 값을 통해 입력값을 알 수 없음
- 입력된 값이 조금만 변해도 결과가 크게 달라지는 특성을 가짐 (눈사태 효과)
- 서로 다른 입력값에도 동일한 값이 출력되는 경우가 있음 (해시 충돌, Hash Collision)
- 왜냐하면 큰 범위의 입력에 비해 출력의 범위가 작으므로
- 비둘기집 원리이기도 함
- 이 경우는 매우 희박하지만 충돌이 없는 해시는 없음
- 위 그림처럼 임의의 입력값인 키를 넣어서 해시 함수를 돌리면 고정된 길이의 해시 값이 나옴
- 조금만 입력이 달라져도 출력은 달라짐
- 서로 다른 입력값에도 동일한 값이 출력되는 해시 충돌 현상도 볼 수 있음
🚀 해시 충돌은 어떻게 방지해야 할까?
해시가 어떤 녀석인지는 알게 되었지만, 해시 충돌이라는 문제점이 커보입니다. 하지만 해시 충돌을 없앨 수는 없으니 해시 충돌이 적은 함수가 좋은 해시함수가 됩니다. 이 해시 충돌을 어떻게 해야할까요?
- Separate Chaining : 해시 테이블의 크기를 유연하게 만든다
- Open Addressing : 해시 테이블의 크기는 고정하면서 저장할 위치를 찾는다
위 2가지 방법으로 해시 충돌을 방지하게 됩니다.
🚀 Separate Chaining
- 해시 테이블의 기본 방식으로, 흔히 해시 테이블이라고 하면 이 방식을 말함
- 충돌 발생 시 연결 리스트로 연결(link)하는 방식
- 위 그림에서 충돌이 발생한 윤아와 서현은 윤아의 다음 아이템이 서현인 형태로 서로 연결 리스트로 연결되었음
- Open Addressing에 비해 삽입과 삭제 작업이 간단함
- 사용하지 않는 공간(slot) 발생 가능
- 한 slot에 저장된다면(쏠린다면) 체인이 길어져서 최악의 경우 O(n)
- 링크 주소를 저장하기 위한 추가 메모리 공간 필요
🚀 Open Addressing
- 충돌 발생 시 탐색(Probing)을 통해 빈 공간을 찾아나서는 방식
- Separate Chaining과 달리 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장 X
- 무한정 저장할 수 있는 Chaining 방식과 달리 전체 슬롯의 개수 이상은 저장할 수 없음
- 위 그림은 가장 간단한 방식인 선형 탐색(Linear Probing) 방식
- 충돌 발생 시 해당 위치부터 순차적으로 탐색을 하나씩 진행하여 특정 위치가 선점되어 있으면 그 다음 위치를 확인하는 방식
- 이렇게 탐색을 진행하다가 비어 있는 공간이 발견되면 삽입하게 됨
- 윤아와 서현의 해시값이 동일한 2로 충돌이 발생했고, 다음번 빈 위치를 탐색하며 그 다음 위치인 3에 서현이 들어감
- 이처럼 선형 탐색 방식은 구현 방법이 간단하면서도 의외로 전체적인 성능이 좋은 편
참고로 데이터 공간은 버킷(bucket)이라고도 합니다. 키(key)에 해당하는 해시값의 데이터 저장소(value)를 버킷 또는 슬롯이라고 합니다. (key-value 자료구조)
🚀 각 언어별 해시 테이블의 구현 방식
🚀 해시를 사용하는 자료구조
위에서 해시를 어떻게 쓰는지 그림을 통해 보았는데 그것이 해시를 사용하는 자료구조인 해시테이블입니다. 해시 테이블은 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인 또는 주소 삼아 데이터를 키와 함께 저장하는 자료구조입니다. (key-value 자료구조)
- 색인(index)에 해시값을 사용하는 자료 구조
- 정렬을 하지 않고도 빠른 검색과 삽입, 삭제 가능하며 평균적으로 O(1), 최악은 O(n)
- 해시는 충분히 큰 공간을 할당 받은 후, 해시 함수를 이용하여 고유 색인을 생성하고 이 고유 색인과 맞는 위치에 데이터를 저장
참고