📖 영상 1 , 영상 2

🔷 8. 해시⭐⭐⭐

8-1 개념

1) 해시 함수를 사용

• 변환한 값을 인덱스 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료 구조
• 키와 데이터는 일대일 대응
• 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수

2) 해시의 특징

• 단방향: 키를 통해 값을 찾을 수 있다.(반대x). 네트워크 보안에서 많이 활용됨.
• $O(1)$: 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋다.
• hash table: 키와 대응한 값이 저장되어 있는 공간
• bucket: 해시 테이블의 각 데이터

3) 활용

• 비밀번호 관리
• 데이터베이스 인덱싱
• 블록체인: 각 블록은 이전 블록의 해시값을 포함. 이를 통해 데이터 무결성을 확인
  - data integrity: 데이터의 정확성, 일관성, 유효성이 유지되는 것. 정보에 결점이 없도록 유지하는 성질.

➕ 참조:
https://en.wikipedia.org/wiki/Hash_table
https://en.wikipedia.org/wiki/Hash_function
https://ko.wikipedia.org/wiki/생일_문제
https://en.wikipedia.org/wiki/Birthday_problem
https://en.wikipedia.org/wiki/Four_color_theorem

8-2 해시 함수

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

1) 해시 함수가 변환한 값을 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.
2) 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 함(충돌이 많이 발생할 수록 성능이 떨어짐)

• 해시 테이블을 크게 만든다.(메모리 문제)
• 해시 함수가 다양한 값을 반환하게 만든다.

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

• 나눗셈법: 구현이 매우 쉽지만, 큰 소수 찾기가 어렵다.
• 곱셈법: 구현이 나눗셈법과 비교했을 때 복잡해진다.
• 문자열 해싱: 키의 자료형이 문자열인 경우.
  - (a+b)%c=((a%c)+(b%c))%c -> 중간마다 mod를 취하면서 오버플로우 방지
  

8-3 충돌처리

• 충돌: 서로 다른 키에 대해서 해시 함수의 결과값이 같은 경우
• 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야
  함

해결

1) 체이닝

• 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결
• 체이닝의 단점
  • 해시 테이블 공간 활용성이 떨어짐
  • 검색 성능이 떨어짐

2) 개방 주소법

• 선형 탐사 방식

  • $hi​(k)=(h(k)+i)mod$ $m$
  • 충돌 시 인덱스를 1씩 늘려가며 빈 공간을 찾음.

• 이중 해싱 방식

  • $hi​(k)=(h1​(k)+i⋅h2​(k))mod$ $m$
  • 두 개의 다른 해시 함수를 사용해서 탐색 간격을 정함.

코딩테스트에서는 해시를 구현할 일은 없다

• 키가 될 수 있는 것: immutable, 고유한 이름.
• tuple은 키가 될 수 있지만 list는 키가 될 수 없다. 이름을 활용해서 찾고 싶은 값.
• 코딩테스트에서 해시를 주로 사용하는 경우
  1) 뭔가를 카운팅: dictionary, count
  2) 존재 여부 확인: 참가자 명은 key로
  3) 정보를 짝지어 저장 (mapping)

문제

1. 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

def solution(participant, completion):
    table = {}
    for i in participant:
        if i not in table:
            table[i] = 1
        else:
            table[i] += 1
            
    for j in completion:
        table[j] -= 1
    
    # 꺼내는 게 문제..
    for key in table.keys():
        if table[key] > 0:
            return key

참고) https://velog.io/@erdosnumber0/leetcode-771.Jewels-and-Stoneseasy

# counter 활용하기
import collections


def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

개인적으로 왜 [0]이 있는걸까 의아했는데,
[0]이 없다면, ['미완주자'] 가 되었을 것이다.
list가 없었다면 dict_keys['미완주자']였을 것이고.

⌛시간 복잡도: 참가자 이름(N개)을 해시 테이블에 추가 $O(N)$,
완주 참가자 이름(N-1개:문제 안에 1명을 제외하고 모두 완주한다는 얘기가 있으므로) 해시테이블에서 제외하는 $O(N-1)$

고로, $O(N+N-1)$ → $O(N)$이지 않을까??? ❓❓❓❓

• 아, 책 오타 $O(N+N-1)$의 괄호 표기가 오타인 듯 하다.
  괄호 없이 $O(2*N-1)$

2. 할인행사

https://school.programmers.co.kr/learn/courses/30/lessons/131127

3. 오픈채팅방

https://school.programmers.co.kr/learn/courses/30/lessons/42888

4. 베스트앨범

https://school.programmers.co.kr/learn/courses/30/lessons/42579

5. 메뉴리뉴얼

https://school.programmers.co.kr/learn/courses/30/lessons/72411

추천 문제1

https://school.programmers.co.kr/learn/courses/30/lessons/42578

추천 문제2

https://school.programmers.co.kr/learn/courses/30/lessons/17684