"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 8장의 써머리입니다."

08.해시

1) 해시의 개념

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

해시 자세히 알아보기

가장 쉽게 볼 수 있는 해시의 예는 연락처이다.

최종으로 얻고자 하는 정보는 전화번호=값(value), 값을 검색하기 위해 활용하는 정보=키(key)

그 사이에 키를 이용해 해시 값 or 인덱스로 변환하는 해시 함수 있음

⇒ 해시 함수는 키를 일정한 해시값으로 변환 시켜 값을 찾을 수 있게 해줌

해시의 특징

1) 해시는 단방향으로 동작
키를 통해 값 찾기 O, but 값을 통해 키 찾기 X

2) 찾고자 하는 값을 O(1)에서 바로 찾을 수 있음
키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정 필요 X

3) 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 함
해시 함수가 중간에서 값이 있는 위치를 찾는 데 도움을 줌

$\therefore$ 해시를 사용하면, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋음

해시가 활용되는 실제 사례

1) 비밀번호 관리
해시 함수를 활용해 해싱한 비밀번호를 저장, 반대의 경우도 같음

2) 데이터베이스 인덱싱
DB에 저장된 데이터를 효율적으로 검색 시 해시 활용

3) 블록체인
블록체인에서 해시 함수는 핵심 역할을 함
각 블록은 이전 블록의 해시값을 포함, 이를 통해 데이터 무결성 확인 가능

2) 해시 함수

해시 함수를 구현할 때 고려할 내용

1) 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안됨(0 ~ N-1)

2) 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 함

충돌의 의미 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미

자주 사용하는 해시 함수 알아보기

나눗셈법(Division Method)
가장 떠올리기 쉬운 단순한 해시 함수

키를 소수로 나눈 나머지를 활용
⇒ 키를 소수로 나눈 나머지를 인덱스로 사용
⇒ 소수를 사용하는 이유 : 다른 수를 사용할 때보다 충돌이 적기 때문

왜 충돌이 많이 발생할까?

N의 약수 중 하나를 M이라고 한다면, 임의의 수 K에 대해 M * K = N이 되는 수가 반드시 있음

K를 주기로 같은 해시값이 반복됨을 알 수 있음

$\therefore$ K는 1과 자신 빼고는 약수가 없는 수=소수를 사용하는 것이 좋음

곱셈법(Multiplication Method)
나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 X

01) 키에 황금비를 곱함

02) 01 단계에서 구한 값의 모듈러 1을 취함 → 정수 부분은 버리고 소수 부분만 취함(0.xxx 형태의 값)

03) 02 단계에서 구한 값을 가지고 실제 해시 테이블에 맵핑 → 테이블 크기가 m이면 위에서 구한 수에 m을 곱한 후 정수 부분을 취하는 연산을 통해 해시 테이블에 매핑 가능
⇒ 0.xxx * m → 테이블의 인덱스인 0 ~ (m - 1)에 매치 가능

문자열 해싱
키의 자료형이 문자열일 때 사용할 수 있는 해시 함수
문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱

문자열 해싱을 위한 polynomial rolling method
01) 알파벳 a ~ z까지 숫자와 매치한 표와 키

02) “a”는 매치 표를 보면 1 ⇒ $s[0] * p^0$ = 1 * 1 = 1

03) 두 번째 문자열 “p”에 대해 연산 진행. “p” = 16 → $16 * p^1$ = 496

04) 이렇게 곱한 값들을 더하면 최종값 = 4,990,970. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용

문자열 해시 함수 수정하기

덧셈을 전부 한 다음 모듈러 연산을 하는 수식 대신, 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로를 최대한 방지할 수 있음

3) 충돌 처리

충돌(Collision) : 서로 다른 키에 대해서 해시 함수의 결과 값이 같을 경우

체이닝으로 처리하기
해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법

충돌 발생 시 해당 버킷에 링크드리스트로 같은 해시 값을 가지는 데이터를 연결
→ 같은 위치를 가리키므로 데이터를 저장할 때 충돌 발생

$\therefore$ 링크드리스트로 충돌한 데이터를 연결하는 방식으로 충돌을 해결

체이닝 장점
1) 충돌을 링크드리스트로 간단히 해결

체이닝 단점
1) 해시 테이블 공간 활용성이 떨어짐
충돌이 많아지면 그만큼 링크드리스트의 길이가 길어짐, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성 ↓

2) 검색 성능이 떨어짐
충돌이 많으면 링크드리스트 자체의 한계 때문에 검색 성능이 떨어짐
→ 링크드리스트로 연결한 값을 찾으려면 링크드리스트의 맨 앞 데이터부터 검색해야 하기 때문

개방 주소법으로 처리하기
개방 주소법(Open Addressing) : 체이닝에서 링크드리스트로 충돌 값을 연결한 것과 다르게 빈 버킷을 찾아 충돌 값을 삽입

→ 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 효율적으로 사용

선형 탐사(Linear Probing) 방식
충돌 발생 시 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동
⇒ 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산 적용

단점 : 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생김 → 클러스터(Cluster)를 형성, 이런 군집이 생기면 해시 값은 겹칠 확률 ↑

이중 해싱 방식
해시 함수를 2개 사용하는 방식, 때에 따라 해시 함수를 N개로 늘리기도 함

두 번째 해시 함수의 역할 은 첫 번째 해시 함수로 충돌 발생 시 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할

4) 몸풀기 문제

문제 18) 두 개의 수로 특정 값 만들기

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True, 없으면 False를 반환하는 함수 작성

def count_sort(arr, k):
  hashtable = [0] * (k + 1)
  
  for num in arr:
    if num <= k:
      hashtable[num] = 1
  return hashtable

def solution(arr, target):
  hashtable = count_sort(arr, target)
  
  for num in arr:
    complement = target - num
    if(
			complement != num
			and complement >= 0
			and complement <= target
			and hashtable[complement] == 1
		):
      return True
  
  return False

문제 19) 문자열 해싱을 이용한 검색 함수 만들기

문자열 리스트 string_list와 쿼리 리스트 query_list가 있을 때 각 쿼리 리스트에 있는 문자열이 string_list의 문자열 리스트에 있는지 여부 확인. 문자열 있으면 True, 없으면 False. 각 문자열에 대해서 문자열의 존재 여부를 리스트 형태로 반환하는 함수 작성

def solution(string_list, query_list):
  lists = []
  res = []
  
  for i in range(len(string_list)):
    lists.append(string_list[i])
    
  for j in range(len(query_list)):
    if query_list[j] in lists:
      res.append(True)
    else:
      res.append(False)
      
  return res

5) 합격자가 되는 모의 테스트

문제 20) 완주하지 못한 선수

마라톤에 참여한 선수들의 이름이 담김 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 있을 때 완주하지 못한 선수의 이름을 반환하는 함수 작성

def solution(participant, completion):
    di = {}
    
    for p in participant:
        if p in di:
            di[p] += 1
        else:
            di[p] = 1
            
    for c in completion:
        di[c] -= 1
        
    for key in di.keys():
        if di[key] > 0:
            return key

문제 23) 베스트 앨범

노래의 장르를 나타내는 문자열 배열 genres와 노래 별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 반환하는 함수 완성

def solution(genres, plays):
    answer = []
    genre = {}
    play = {}
    play_sort = {}
    
    for i in range(len(genres)):
        if genres[i] not in genre:
            genre[genres[i]] = {}
            play[genres[i]] = 0

        genre[genres[i]][i] = plays[i]

        play[genres[i]] += plays[i]
    
    genre_sort = sorted(play.items(), key=lambda x: x[1], reverse=True)
    
    for j in range(len(genre_sort)):
        play_sort[genre_sort[j][0]] = sorted(genre[genre_sort[j][0]].items(), key=lambda item: item[1], reverse=True)[:2]

        answer.extend([idx for idx, _ in play_sort[genre_sort[j][0]]])
        
    return answer