코딩 테스트 스터디 - 08 해시

해시의 개념

배열로 연락처 구현하면 이름 -> 이름 테이블에 선형 탐색 -> 그 위치에 해당되는 전화번호 테이블 참조
인덱스에 이름 정보를 넣을 수 있게 하려면.

해시 적용하면

해시 함수를 사용해서 변환한 값을 인덱스로. -> 키를 해시 함수로 돌리면 인덱스가 나온다.
O(N) -> O(1)

해시 함수

임이의 키를 해시 테이블의 인덱스로 변경.
-> 테이블 크기가 N이라면 함수는 [0, N-1) 사이 값을 내야 함. 충돌이 적을수록 (동일한 인덱스) 좋은 해시 함수

나눗셈법

h(x) = x mod k (k는 소수!) -> 테이블 크기가 커지면 큰 소수가 필요함 (구하기 어렵다)

곱셈법

h(x) = (((x * A) mod 1) * m
x는 키, A는 황금비. m은 최대 버킷의 갯수

a / b = a / (a + b): 1.618...

0 ~ 0.999 -> 0 ~ m-1.xxxxxxxxx

문자열 해싱

아스키 코드 값으로 해싱.

해시 충돌

다른 키에 대해 해시 함수 결과값이 같은 경우 .. 충돌

• 체이닝
• 개방 주소법

체이닝

충돌 발생 시 해당 버킷에 Linked List로 데이터 연결.
특정 버킷에 데이터가 N가면 원하는 값을 찾는데 O(N)걸릴 수 있음 (그러나 그럴 확률이 적지..)
3 | B:871 - C:742 등... 쭉쭉 이어나감

개방 주소법

• 선형 탐사
  충돌 발생 시 다른 빈 버킷을 찾아 삽입 (기존 해시 테이블의 빈 칸에 삽입!)
  h(k, i) = (h(k) + i) mod m
  i는 충돌 시 이동할 버킷 수.
• 이중 해싱
  해시 함수를 2개 사용
  h(k, i) = (h_1(k) + i * h_2(k)) mod m
  i는 임의의 수이며 2번째 해시 함수에 i를 곱할 수도 있다.

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

• key-value 쌍으로 연관된 데이터의 존재. 해당 값에 대한 접근이 빈번한 경우 (사전, 연락처)
  • 키 -> ( ) -> 인덱스|값. 이 때 키와 값을 잘 정해줘야 함.
• 중복되지 않는 키 (학번, 집 주소)

그냥 map 쓰면 매번 키 순으로 데이터가 정렬됨. 필요 없으면 unordered_map을 쓰자!

해시를 쓰면 안 되는 경우

• 특정 키에 여러 가지 값을 넣어야 할 때

출처 : 코딩 테스트 합격자 되기 - 박경록