Hash
#️⃣ 해시
해시 함수 (Hash Function)
데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
해싱 (Hashing)
- key : 매핑 전 원래 데이터의 값
- value : 매핑 후 데이터의 값
매핑하는 과정 전체를 '해싱'이라고 한다.
해시 충돌 (Collision)
해시 함수는 해시값의 개수보다 대개 많은 키 값을 해시값으로 변환(many to one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 동일한 해시값을 내는 해시충돌이 발생하게 된다.
그래서 충돌을 최소화할 수 있는 해시함수를 사용해야 한다.
Hash가 쓰이는 곳
hashMap 형태로 많은 언어들에서 사용된다. 주로 특정 데이터를 임시 공간에 저장하고 나중에 데이터의 키로 해당 데이터를 빠르게 찾으려고 할 때 사용된다.
대표적으로 캐싱을 할 때 많이 사용되며, key-value store라고 불리는 NoSQL(Redis)가 이러한 해싱 방식을 사용한다.
🪟 Hash table
- 배열과 해시 함수를 사용하여 map을 구현한 자료구조
- hash table에서 해시 함수는 임의의 데이터를 정수로 변환해준다.
- 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다.
- 메모리 절약을 위해 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.
저장/조회할 때 해시 버킷을 계산하는 방법
int index = X.hashCode()%M;
💥Hash Collision (해시 충돌)
- key는 다른데 hash가 같을 때
- key도 hash도 다른데 hash%map_capacity 결과가 같을 때
아까도 설명한바와 같이, 해시함수는 해시값의 개수보다 대게 많은 키값을 해시값으로 변환하기 때문에 줄어든 범위에서 충돌이 발생할 수 밖에 없다. 그렇게 때문에 해시함수의 해시값이 최대한 균등하게 나오게 하는 것이 중요하다.
✔️ 해결 방법
1️⃣ open addressing (개방 주소법)
해당 버킷에 데이터가 이미 있는데 key 값이 다르면 충돌이 발생한다.
open addressing 방식은 비어있는 버킷을 활용하는 방법이다.
즉, open addressing은 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시 테이블이다.
구현 방법은 3가지가 있다.
- Linear Probing(선형 조사법) : 현재 버킷의 index에서 고정폭만큼식 이동하여 비어있는 버킷에 저장
- 이차 조사법 : 현재 버킷의 index에 제곱수만큼식 이동하여 비어있는 버킷에 저장
- 1칸, 2칸, 4칸, 9칸..
선형 조사법과 이차 조사법은 클러스터링 문제가 발생하여 평균 탐색 시간이 증가한다.
(클러스터링 문제 : 충돌이 많이 일어나면 성능 처하 심각)
- 이중 해시 : 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방법
2️⃣ Separate chaining (분리 연결법)
한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는다.
해당 버킷에 데이터가 이미 있는데 key 값이 다르면 충돌이 발생한다. 이 때 연결리스트에 노드를 추가하여 데이터를 저장한다.
장점 : 유연하다.
단점 : 메모리 문제 야기, 데이터 수 많아지면 동일 버킷에 chaining되는 데이터가 많아져 캐시의 효율성이 감소한다.
✔️ Java에서 Hash Collision
Java HashMap에서는 separate chaining 방식으로 충돌을 해결한다.
왜냐하면 open addressing 방식은 데이터 삭제 처리가 효율적이지 않기 때문이다.
📢 면접에 나올만한 질문들
📌 1. Hash란 무엇인가요
Hash는 데이터를 고정된 크기의 값으로 매핑하는 방식입니다.
일반적으로 key를 입력받아 고정된 범위의 인덱스를 생성하고, 이를 통해 데이터를 빠르게 저장하고 조회하는 자료구조입니다.
대표적인 구현체로는 Hash Table 이 있습니다..
📌 2. Hash의 특징과 문제점은?
특징
- 평균적으로 O(1) 시간 복잡도로 검색, 삽입, 삭제가 가능합니다.
- 빠른 조회 성능을 가지고 있습니다.
문제점
- 충돌이 발생할 수 있습니다. 서로 다른 key들이 같은 hash 값을 갖는 문제
- 메모리 사용량이 상대적으로 클 수 있습니다. (버킷을 넉넉히 잡아야 충돌이 줄어들기 때문에)
📌 3. Hash는 어디에 사용되는가?
- 데이터베이스 인덱싱 : 빠른 데이터 조회
- 캐시 : 빠르게 키-값 쌍으로 데이터 저장
📌 4. Hash 함수를 만들 때 고려할 점은?
- 서로 다른 key들이 최대한 골고루 버킷에 배치되어야 한다.
- 같은 입력은 항상 같은 출력을 가져야 한다.
- 서로 다른 key가 같은 hash를 가질 확률을 낮춰야 한다.