코딩 테스트 합격자 되기 스터디 3주차 - 해시

https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

코딩테스트 합격자 되기 스터디 3주차

해시

• 해시의 개념
• 해시 함수
• 충돌 처리

해시

해시 함수를 사용해서 변환한 값을 인덱스 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

(키를 해시함수에 넣으면 인덱스가 나오도록)

키만으로 값의 인덱스를 구할 수 있으므로 빠른 탐색 가능.

배열로 탐색 시 O(N)이지만 해시 함수와 함께라면 O(1)이 된다!

해시함수의 개념

임의의 키를 해시테이블의 인덱스로 변경해주는 함수

→ 해시 테이블의 크기가 N이라면 해시함수는 0~(N-1)사이 값을 내야 함

→ 충돌을 최소화할수록 좋은 해시함수.

• 서로 다른 키에 대해 해시 함수가 동일 인덱스 반환할 경우 충돌 발생.

해시함수

나눗셈 법

h(x) = x mod k (x는 키, k는 소수)

• k로 나눈 나머지는 0~(k-1)이므로 해시 테이블의 크기는 k
• k가 소수인 이유는 충돌을 줄이기 위함(소수가 아니면 k주기로 해시값 반복)

곱셈법

• 나눗셈법은 k가 소수여야 하므로, 테이블 크기가 커지면 큰 소수가 필요.
• 곱셈법은 소수 활용하지 않고 황금비를 곱하는 방식
• h(x) = (((x*A) mod 1))*m x는 키, A는 황금비, m은 최대 버킷 개수

황금비란?
a/b = a/(a+b) = 황금비
대략 1.6180339887…. → 이게 곱셈법의 A

문자열 해싱

• 문자열의 아스키 코드 값을 활용한 해싱
• hash(s) = (s[0] + s[1]*p + s[2]*p^2 + … + s[n-1]*p^(n-1)) mod m
• p는 31(홀수이면서 메르센 소수), m이 테이블 크기
• 숫자가 금방 커지므로 구현 시 overflow 발생 가능
• 수정된 공식 사용
• a = 1, b = 2, c = 3 … z = 26으로 숫자를 매칭하여 사용

(a+b)%c = (a%c + b%c)%c를 활용해서 아래와 같이 구현

• hash(s) = (s[0] + s[1]*p + s[2]*p^2 + … + s[n-1]*p^(n-1)) mod m

hash(s) = (s[0]%m+s[1]*p%m+s[2]*p^2%m … s[n-1]*p^(n-1)%m)%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은 테이블 크기

언제 해시를 활용해서 문제를 풀어야 하나?

• 키-값 상으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우
• 예를 들어 사전(단어 검색해서 뜻 찾음)이나, 연락처(이름 검색으로 번호 찾음)
• 중복되지 않는 키를 사용하는 경우
• 예를 들어 학번이나 집주소

어떤 걸 통해 데이터에 접근할지 고민해봐야함(번호로 이름을 찾으면 의미가 없듯..)