[코딩 테스트 합격자 되기] 해시

[인프런] 코딩 테스트 합격자 되기 C++

강의 링크 : https://www.youtube.com/watch?v=KsfmSyIYX3g&t=3s

<Hash>

배열의 경우 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색 해야 함 O(n)

contents 자체를 가지고 위치 (index)를 알 수 있는 것이 해시

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

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

* 충돌 : 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환하는 것

[해시함수 종류]

나눗셈법 : h(x) = xmodk (x는 키, k는 소수)
- k가 소수여야 함 -> 테이블 크기가 커지면 큰 소수 필요 (큰 소수 구하기 어려움)
곱셈법 : h(x) = (((x * A) mod 1) * m), (x는 키, A는 황금 비, m은 최대 버킷의 개수)
- 황금비(A=1.6180339887)를 곱하는 방식
- mod 1 : 소수 부분만 취함 => 0 ~ 0.999999
- 위 결과에 m을 곱하면 0 ~ m-1.xxxx
문자열 해싱 : h(s) = (s[0] + s[1]*p + s[2]*p^2 + ... + s[n-1] * p^(n-1)) mod m
- 문자열의 아스키 코드 값을 활용한 해싱
- p는 31 (홀수이면서 메르센 소수 - 값을 균등하게 퍼트리기 위함), m은 테이블 크기
- a = 1, b = 2, ... z = 26로 숫자를 매칭해서 사용
- 숫자가 금방커지므로 구현시 overflow가 발생할 수 있음 -> 수정된 공식 사용
- (a+b)%c = (a%c + b%c) %c
- => h(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은 버킷 사이즈)
- 충돌 발생 시, 다른 빈 버킷을 찾아 충돌값을 삽입
- 최대한 기존 테이블을 사용하자는 방식 (메모리 save)
개방 주소법 - 이중해싱 : h(k,i) = (h1(k) + i*h2(k)) mod m
- 해시 함수를 2개 사용 (경우에 따라 N개까지 확장0
- 2번째 해시함수에 i를 곱하는 방식, 이 때 클러스터를 줄이기 위해 m을 제곱수나 소수로 함

[해시를 사용하는 경우]

예시)

학생 정보 관리 시스템 - 점수 한개, 점수 여러개

[풀어볼 만한 문제]

C++ 예시 코드를 보는데 간단한 구현 부분도 문법들이 너무 낯설게 느껴짐

계속 보면서 익힐 필요

준비하고 있는 시험이 있어서 문제는 추후 풀어볼 예정

cod