해시의 개념
홍길동의 이름 테이블이 어디 위치에 저장되어 있는지 모르기 때문에 선형 탐색을 사용해야 한다
해시함수를 통해서 인덱스를 찾을수 있다
예시
이름 -> 연락처
홍길동 -> 그 위치에 해당되는 전화 테이블을 참조
이름을 통해서 인덱스를 찾을 수 있다
해시 함수를 통해 배열 인덱스를 찾아간다
해시를 적용한 연락처
해시 함수 예시
임이의 키를 해시테이블의 인덱스로 변경해주는 함수
해시 테이블의 크기가 N이라면 해시 함수는 0~(N-1) 사이 값을 내야 함
충돌을 최소화 할수록 좋은 해시함수
해시함수 나눗셈은 h(x) = x mod k (x는 키, k는 소수) 라고 했을때
k로 나눈 나머지는 0~k-1이므로 해시 테이블의 크기는 k
k가 소수인 이유는 충돌을 줄이기 위함 (소수가 아니면 k주기로 해시값 반복된)
나눗셈법은 k가 소수여야 하므로 테이블 크기가 커지면 큰 소수가 필요
곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식
h(x) =((x*A)mod1)*m) x는 키, A는 황금 비 , m은 최대 버킷의 갯수
a/b=a /(a+b) = 황금비
황금비는 대략 1.6180339887 -> 곱셈법의 A
h(x) = (((x * A)mod1) * m)
-x는 키, A는 황금 비, m은 최대 버킷의 갯수
해시함수 (문자열 해싱)
문자열의 아스키 코드 값을 활용한 해싱
hash(s) = (s[0]) + s[1] * p + s[2] *p2+ ... + s[n-1 *p n-1) mod m
해시함수 (문자열 해싱 해시함수 설명)
해시함수 (문자열 해싱, 해시함수 설명)
해시 충돌이란?
서로 다른키에 대해 해시 함수 결괏값이 같은 경우 "충돌"이 발생함
체이닝 개방 주소법이 충돌을 처리하는 대표적인 방법
해시충돌처리(체이닝)
충돌 발생 시, 해당 버킷에 링크드리스트로 데이터를 연결함.
특정 버킷에 데이터가 N개인 경우, 원하는 값을 찾는데 O(N)이 걸릴수 있음
해시충돌처리 (개방 주소법 - 선형탐사)
충돌 발생 시 , 다른 빈 버킷을 찾아 충돌값을 삽입
최대한 기존 테이블을 사용하는자는 방식 (메모리를 아낄수 있음)
h(k,i) = (h(k)+i)mod m
k는 키 i는 충돌시 이동할 버킷 수 m은 버킷 사이즈
해시충돌처리 (개방 주소법 - 이중해싱)
용어 그대로 해싱 함수를 2개 사용 (경우에 따라 N개 까지 확장)
기존에 i를 더했던 선형탐사오 다르게 2번째 해시함수에 i를 곱하는 방식도 가능
이 떄 클러스터를 줄이기 위해 m을 제곱수나 소수로 함
h(k,i) = (h1, (k) + i * h2 (k))mod m
k는 키 i는 임의의 수, h1은 첫번쨰 해시함수, h2는 두번쨰 해시함수, m은 테이블크기
언제 해시를 활용해서 문제를 풀어야 하나?
키 값 쌍으로 연관된 데이터가 존재하며 해당 값에 대한 접근이 빈번한 경우
예를 들어 사전(단어를 검색해서 뜻을 찾음) 이나 연락처(이름을 검색해서 번호를 찾음)
중복되지 않는 키를 사용하는 경우
예를 들어 학번이나 집주소 (중복되지 않음)
참고자료