💻 [코테03] 8장 해시

8장. 해시

08-1. 해시의 개념

1) 해시

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

2) 특징

• 단방향으로 동작
• 찾고자 하는 값을 O(1)에서 바로 찾기 가능

3) 해시의 특성을 활용하는 분야

• 비밀번호 관리 : 해싱한 비밀번호를 저장
• 데이터베이스 인덱싱 : 효율적으로 검색
• 블록체인 : 이전 블록의 해시값 포함하여 데이터 무결성 확인 가능

  💡 [코딩 테스트] 해시를 고려해야 하는 경우
  -특정 데이터를 탐색하는 횟수가 많을 경우
  -특정 정보와 매핑하는 값의 관계를 확인해야 하는 작업이 있는 경우

08-2. 해시 함수

• 파이썬의 딕셔너리 자료형은 해시와 거의 동일하게 동작

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

• 해시 함수가 변환한 값은 해시 테이블의 크기를 넘으면 안된다
• 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다

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

• 나눗셈법 : 키를 소수로 나눈 나머지 활용하는 방법(모듈러 연산)
• 곱셈법 : 황금비를 활용하는 방법
• 문자열 해싱 : 키의 자료형이 문자열인 경우, 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환하여 해싱하는 방법
  

08-3. 충돌 처리

1) 체이닝으로 처리하기

• 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결하는 방법
• 해시 테이블 공간 활용성 감소
• 검색 성능 감소

2) 개방 주소법으로 처리하기

• 충돌이 발생하면 빈 버킷을 찾아 충돌값을 삽입하는 방법
• 체이닝 보다 메모리를 더 효율적으로 사용
• 선형 탐사 방식 : 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동하는 방법
• 이중 해싱 방식 : 2개의 해시 함수를 사용하는 방법
  - 두 번째 해시함수는 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할
  

08-4. 몸풀기 문제

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

'''
1. arr가 들어온다.
2. arr 중 요소 더해서 target이 되는 것이 있는지 확인
3. 있으면 True, 없으면 False
'''

def solution(arr, target):
    dic_arr = dict()
    for key in arr:
        dic_arr[key] = 0
    for key in dic_arr:
        condition = (target - key) != key
        if ((target - key) in dic_arr) and condition:
            return True
    return False

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

'''
1. query_list에 있는 원소가 string_list에 있는지 확인한다
2. 있으면 True, 없으면 False 값을 정답 리스트에 넣는다
'''
def solution(string_list, query_list):
    answer = []
    string_dict = {}
    for string in string_list:
        string_dict[string] = 1
    for query in query_list:
        if query in string_dict:
            answer.append(True)
        else:
            answer.append(False)
    return answer

08-5. 합격자가 되는 모의 테스트

• 문제20_완주하지 못한 선수
• 문제21_할인 행사
• 문제22_오픈 채팅방