[코테 합격자 되기] 08장 해시

# 배열 vs 해시

위처럼 배열을 사용하면

탐색을 하는데 O(N) + 접근을 하는데 O(1)이 걸린다

 

반면,

위처럼 해시를 사용하면

탐색 및 접근이 O(1)이 걸린다

해시 자료구조의 내부 구성은 크게 해시 함수, 버킷, 해시테이블로 구성된다

 

# 해시함수란?

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

해시테이블의 크기가 N이라면, 해시함수는 0 ~ N-1 사이의 값을 가진다

또한, 충돌을 최소화 할수록 좋은 해시함수이다

 

# 해시함수의 내부 방식

대표적으로 나눗셈법, 곱셈법, 문자열 해싱이 있다

- 나눗셈법

키를 %소수를 하는 방식이다

소수가 아닌 경우는 충돌이 많이 발생하기에 소수로 연산을 한다

예를 들어, 소수가 아닌 2인 경우는

짝수는 무조건 0이고 홀수는 무조건 1이니 충돌이 많이 발생한다는 사실을 알 수 있다

물론, 소수여도 한계 및 단점은 존재하고

테이블 크기가 커지면, 큰 소수가 필요하지만 이러한 소수를 찾기란 어렵다

 

- 곱셈법

나눗셋법의 문제를 해결하기 위해

소수를 이용하지 않고 황금비를 곱하는 방식이다 

황금비란?

위 그림처럼 황금비를 곱해서 소수만을 추출해 낸 다면,

0 ~ 0.999999…가 나오고

여기서 m을 곱하면, 0 ~ m-1.xxxxxxxxxx의 경우의 수가 추출되며

그에 맞게 해시테이블 크기가 설정된다

 

- 문자열 해싱

문자열 해싱은

문자를 숫자로 변경해서 위와 같은 연산을 하는 방식이다

참고로, p는 31(홀수이면서 메르센 소수)은 균등하게 분배하기 위한 최적의 수이다

그런데, 해당 공식의 31^n을 연산하는 과정에서 overflow가 발생할 수 있어서 아래의 수정된 공식을 사용한다

 

---

 

# 해시 충돌

- 해시 충돌 개념

서로 다른 키에 대한 해시 함수 결괏값이 같은 경우에 충돌이 발생한다

 

- 해시 충돌 해결법

대표적인 해결 방식은 체이닝, 개방 주소법(선형탐사, N 중 해시)이 있다

1) 체이닝

충돌 발생 시, 해당 버킷에 링크드리스트로 데이터를 연결하는 방식이다

다만, 최악의 경우 탐색이 O(N)이 걸린다

실제 라이브러리에서는 해당 부분에대한 최적화(ex. 선형 + 이진트리)가 더 들어간다

 

2) 개방 주소법(선형 탐사)

충돌 발생 시, 다른 빈 버킷을 찾아 충돌값을 삽입하는 방식이다

최대한 기존 테이블을 활용하자는 방식으로 메모리를 절약할 수 있다

 

3) 개방 주소법(이중 해싱)

key를 해싱한 값 + 한번더 key를 해싱한 값 * i를 통해

여러 번 해싱을 하는 방식이다

---

 

# 언제 해시를 써야 하는가?

1) 키-값 쌍으로 연관된 데이터가 존재하며,

해당 값에 대한 접근이 빈번한 경우에 사용한다

참고로, 해시를 사용하는 경우에

반드시 키와 값을 올바르게 선정하는 것이 중요하다

(ex. 뭐를 통해 어떤 값이 필요한 건지를 파악하고 키와 값 설정)

 

2) 중복되지 않는 키를 사용하는 경우

중복되면 덮어쓰기로 값이 저장되니

반드시 중복 key가 있는 경우에는 해시를 사용하면 안 된다

 

# 예시 1. 점수 한 개

예시 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/managing_stdudent_one_score.cpp

 

추가적으로,

map의 경우는 해시 방식이 아닌 이진탐색트리를 활용한 방식이다

데이터가 삽입/삭제될 때마다 매번 키 순으로 데이터가 정렬되고

삽입/삭제/탐색 모두 O(logN)이 걸리기에 상황에 따라 TLE가 발생할 수도 있다

예를 들어, 2중 반복문 안에 map을 사용하는 경우에는

O(N^2 * log N)이 걸리며 TLE가 발생할 가능성이 크다

이처럼 map과 unordered_map은 서로 전혀 다르다는 사실을 알아야 한다

 

# 예시 2. 점수 두 개

예시 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/managing_stdudent_multi_score.cpp

 

# 예시 3. 문자열 내 문자 빈도수

문제:

문자열이 입력됩니다

문자열의 각 문자의 개수를 확인하고 싶습니다

 

예시 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Example/frequency_word.cpp