해시 개념
해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
- 일반적으로는 인덱스를 통햇 탐색을 빠르게 만들지만 해시는 키를 활용해서 탐색을 빠르게 만듬.
해시의 특징
1. 해시는 단방향으로 동작함
2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있음.
- 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없음.
3. 값을 인덱스로 활용하려면 변관과정이 필요함
해시를 사용하지 않는다면
값의 위치에 대한 어떤 정보도 알 수 없기 때문에 데이터를 찾기 위해 전체 데이터를 확인해야한다. 즉, 탐색 효율이 떨어진다.
반면에 해시를 사용할 경우, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치로 바로 찾을 수 있어 탐색 효율이 좋다.
- 해시 테이블: 키와 대응한 값이 저장되어 있는 공간.
- 버킷: 해시 테이블의 각 데이터
해시의 특성을 활용하는 분야
해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색할 수 있다. 이런 해시의 특성은 데이터를 저장하고 검색하거나, 보안이 필요한 때에 활용된다. 코딩 테스트에서는 특정 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋다.
- 비밀번호 관리 : 사용자의 비밀번호를 그대로 노출해 저장하는 것은 위험하므로, 해시 함수를 활용해 해싱한 비밀번호를 저장한다. 사용자가 입력한 비밀번호를 해싱해 확인한다.
- 데이터베이스 인덱싱 : 데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용
- 블록체인 : 블록체인에서 해시 함수는 핵심 역할을 한다. 각 블록은 이전 블록의 해시값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있다.
해시 함수
해시 함수 구현시 고려할 내용
-
해시 함수가 반환한 값은 인덱스로 활용해야 하므로, 해시 테이블의 크기를 넘으면 안 된다.
- 즉, 해시 함수의 결과는 0 ~ N-1 사이여야 한다.
-
충돌을 최대한 줄여야 한다.
- 충돌: 서로 다른 두 키에 대해 해시 값을 적용했을 때 동일한 결과가 나오는 경우.
자주 사용하는 해시 함수
나눗셈법
키를 소수로 나눈 나머지를 활용
이처럼 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시함
h(x) = x mod k
- 소수가 아니면 특정 패턴의 키에서 충돌이 반복적으로 발생할 수 있음
곱셈법
나눈셈법은 때에 따라 큰 소수를 사용해야 하는데 큰 소수를 구하기가 쉽지 않다는 단점이 존재함. 곱셈법은 나눗셈법과 비슷하게 모듈러 연산을 사용하나, 소수를 사용하지는 않음.
h(k)=(((x*A)mod1)*m)
m: 최대 버킷 갯수
A: 황금비의 소수 부분인 0.618033
- 키에 황금비를 곱함
- 구한 값의 모듈러 1을 취함 -> 정수 부분을 버리고 소수만 취함
- 구한값으로 실제 해시 테이블에 매핑
문자열 해싱
문자열을 수로 바꿔 해시값을 구하는 방식
hash(s) = (s[0]+s[1]* p+s[2]*p²+... + s(n-1]*pⁿ⁻¹) mod m
p는 일반적으로 31 사용 (홀수이며서 메르센소수)
m은 해시 테이블 크기
- 문자열을 숫자(매치 테이블)로 변환
- 변환후 공식적용
- 최종값을 해시 테이블의 크기 m으로 모듈러 연산해 활용
예시)
a:1, p:16, p:16, l:12, e:5
결과: 131⁴ + 1631³ + 1631² + 1231¹ + 5*31⁰ = 4,990,970
충돌 처리
서로 다른 키에 대해서 해시 함수의 결과값이 같을 경우 충돌 이라고 함. 하나의 버킷에 두개의 값을 넣을 수는 없으므로 해시 테이블을 관리 할 때는 반드시 충돌 처리를 해야함.
체이닝으로 처리
충돌이 발생시 해다 버킷에 연결 리스트로 같은 해시값을 가지는 데이터를 연결.
체이닝으로 처리시 단점
- 해시 테이블 공간 활용성이 떨어짐
- 충돌이 길어질 수록 연결리스트가 길어지고 , 다른 해시테이블의 공간을 덜 사용하게 됨
- 검색 성능이 떨어짐
- 충돌이 길어지면 연결리스트 자체의 한계 때문에 검색기능이 떨어짐
개방 주소법으로 처리
체이닝에서 연결 리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입
선형 탐사 방식
- 충돌이 발생하면 다른 빈 버켓을 찾을 때 까지 일정한 간격으로 이동
수식: h(k, i) = (h(k) + i) mod m
m: 수용할 수 있는 최대 버킷
이중 해싱 방식
해시 함수를 2개 사용하여 , 첫 번째 해시 함수로 충돌이 발생하면, 둡너째 해시 함수로 해당 위치를 기준으로 어떻게 위치를 정할지 결정함.
