해시(Hash)란?
해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수 또는 알고리즘이다.
이 과정을 통해 생성된 고정 크기의 값을 '해시 값'이라고 한다.
해시 관련 용어 정리
해시 (Hash) | 임의의 값을 고정 길이로 변환 |
해시 테이블 (Hash Table) | 키 값의 연산에 의해 직접 접근 가능한 데이터 구조 |
해시 함수 (Hash Function) | Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 |
해시 값 (Hash Value) / 해시 주소(Hash Address) | Key를 해시 함수로 연산해서 해시 값을 알아내고, 이를 기반으로 해시 테이블에서 해당 Key에 대한 데이터를 일관성 있게 찾을 수 있음 |
해시 버킷 (Hash Bucket) / 해시 슬롯 (Hash Slot) | 버킷 : 각 해시에 대응하는 배열 슬롯 : 배열 내 개별 위치 혼용해서 쓰기도 함 |
해시의 특징과 사용 분야
특징
- 고정 길이 출력: 입력 데이터의 크기에 관계없이 항상 고정된 길이의 해시 값을 생성
- 단방향성: 해시 함수는 일방향 함수로, 해시 값에서 원래 데이터로의 복원이 어렵거나 불가능
- 눈사태 효과: 입력 데이터가 조금만 변경되어도 완전히 다른 해시 값을 출력
- 결정성: 같은 입력 값에 대해서는 항상 같은 해시 값을 출력
- 효율성: 대부분의 해시 알고리즘은 고속으로 동작하며, 시스템 자원을 상대적으로 적게 소모함
적합한 상황 / 부적합한 상황
적합한 상황 | 부적합한 상황 |
- 빠른 검색 필요한 경우 - 중복 데이터를 효율적으로 처리해야하는 경우 ㄴ해시 세트를 사용하여 중복 데이터 처리 - key-value 쌍 저장이 필요한 경우 |
- 데이터 정렬이 필요한 경우 ㄴ 해시는 순서 보장 X - 공간 효율성이 중요한 경우 ㄴ key-value를 저장해야 하므로 많은 메모리 공간 필요 |
사용 분야
- 데이터 무결성 검증: 파일이나 메시지의 변조 여부를 확인하는 데 사용
- 비밀번호 저장: 비밀번호를 평문 대신 해시값으로 저장하여 보안 강화
- 디지털 서명: 전자 문서의 인증에 활용
- 데이터 구조: 해시 테이블과 같은 효율적인 데이터 구조의 기반이 됨
- 데이터 검색 및 인덱싱: 대량의 데이터에서 빠른 검색을 가능하게 함
해시의 충돌 현상 (collision)
서로 다른 입력이 동일한 해시값을 생성하는 것을 '충돌 현상' 이라고 한다.
이에 대한 주요 원인은 비둘기집 원리와 생일 역설이 있다.
비둘기집 원리
n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리
해시를 통해 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값(해시값)을 생성한다.
이로 인해 서로 다른 입력이 동일한 해시 값을 생성하는 충돌 현상이 발생할 수 있다.
생일 역설
사람을 임의로 모았을 때 같은 생일자가 있을 확률.
1년은 365일, 많아도 366일이니까 사람이 366명 모여있어야 같은 생일자가 존재할까? X
만약 입력되는 값의 수를 알고 있고, 해시의 출력 공간이 충분하더라도 생일 역설에 의해 같은 해시 값에 할당 될 수 있다.
충돌 해결 기법
동적 재해싱(Dynamic Rehashing)
발생한 충돌을 해결하는 것이 아닌 충돌 감소를 목적으로 하는 기법이다.
해시 테이블이 꽉 차지 않도록 하여, 각 항목이 적절하게 분포되도록 한다.
(1) 해시 테이블이 특정 임계값에 도달하면
(2) 테이블 크기를 동적으로 확장하고
(3) 기존 데이터를 새로운 테이블로 재해싱하는 과정을 거친다.
충돌을 감소시키고, 데이터 양에 대해 유연하게 대응할 수 있다는 장점이 있지만,
재해싱 비용이 들고, 새로운 테이블을 할당하고 기존 데이터를 옮기는 과정에서 일시적으로 두배의 메모리가 필요하다.
그리고 충돌 감소를 위해 다양한 최적화 기법을 써도, 해시의 충돌을 완전히 예방하는 것은 불가능하다.
⭐️⭐️때문에, 충돌이 발생했을 때 적절히 대응할 수 있도록 하는 것이 중요하다. ⭐️⭐️
해시의 충돌 해결 기법은 체이닝, 개방주소법과 같은 방식들이 있다.
체이닝 (Chaining)
해시 테이블의 각 버킷에 연결 리스트를 사용하여 충돌을 해결하는 방식.
특징
- 동일한 해시값을 가진 항목들을 연결 리스트로 연결
- 삽입과 삭제가 간단
- 연결리스트로 인한 추가적인 메모리 사용이 필요
- 최악의 경우 시간 복잡도가 O(n)이 될 수 있음
개방 주소법 (Open Addressing)
충돌 발생 시 다른 버킷을 찾아 데이터를 저장하는 방식.
종류
- 선형 탐색 (Linear Probing) : 정해진 고정 폭만큼 이동하여 순차적으로 다음 버킷을 탐색
- 이차 탐색 / 제곱 탐색(Quadratic Probing) : 정해진 고정폭에 2차함수를 이용하여 다음 버킷을 탐색
특징
- 추가적인 메모리 사용이 없음
- 캐시 효율성이 좋음
- 다른 버킷을 찾아갈 때 메모리 접근 패턴이 비교적 규칙적이고 지역성을 가진다.
- 개방 주소법을 사용하면 데이터가 해시 테이블 내에 밀집되어 저장된다. 한번의 메모리 접근으로 더 많은 데이터를 읽어올 수 있다. - 특정 해시 값이 충돌하여 여러 버킷이 연속적으로 채워지게 되는 클러스터링 문제가 발생할 수 있음 (선형 조사법에서 주로 발생)
❗️암호학적 해시 함수는 다음과 같은 특성으로 인해 충돌을 찾는 것도 어렵다
- 사전 이미지 저항: 주어진 해시값에 대한 원본 입력을 찾기 어려움
- 제2 사전 이미지 저항: 주어진 입력과 동일한 해시값을 생성하는 다른 입력을 찾기 어려움
- 충돌 저항: 동일한 해시값을 생성하는 두 개의 서로 다른 입력을 찾기 어려움
'Computer Science > Data Structure' 카테고리의 다른 글
이진탐색트리(Binary Search Tree, BST) (0) | 2024.11.16 |
---|---|
트리(tree) (0) | 2024.11.15 |
큐(Queue) - Array와 LinkedList로 구현, 원형큐, 덱/데크(Deque) (0) | 2024.11.07 |
스택(Stack) - Array와 LinkedList로 구현 (1) | 2024.11.07 |
배열(Array)과 리스트(List), ArrayList와 Linked List (0) | 2024.11.05 |