해시

해시란?

• 개념: 해시 함수를 사용하여 키를 값에 매핑하는 데이터 구조
• 해시 함수는 빠른 조회를 위해 키를 변환된 값(주로 인덱스)으로 변환하여 데이터를 훨씬 빠르게 검색할 수 있게 해준다.
• 연속 인덱스를 사용하는 기존 배열과 달리 해시는 키를 사용하여 데이터를 탐색

특징

1. 단방향 액세스: 키를 사용하여 값을 찾을 수는 있지만 값에서 키를 찾을 수는 없다.
2. 상수 시간 조회(O(1)): 해시 함수는 키에서 직접 인덱스를 계산하므로 전체 데이터 집합을 검색할 필요 없이 빠르게 검색 가능
3. 변환 필요: 해시함수를 통해 키를 인덱스로 변환해야 값에 효율적으로 액세스할 수 있다.
4. 해시를 사용하지 않으면 항목을 찾기 위해 데이터 전체 검색을 수행해야 하므로 효율성이 훨씬 떨어진다.

 

해시 테이블 또는 버킷

• 해싱에서 '해시 테이블' 또는 '해시 맵'은 키-값 쌍을 저장하는 데이터 구조이며, '버킷'은 이러한 쌍을 저장하는 해시 테이블 내의 개별 슬롯

 

해싱의 활용 분야

• 비밀번호 관리: 해싱은 비밀번호를 쉽게 되돌릴 수 없는 해시 값으로 변환하여 비밀번호를 안전하게 저장하는 데 사용
• 데이터베이스 인덱싱: 해시 함수는 대규모 데이터베이스에서 데이터 검색 속도 증가
• 블록체인: 해시 함수는 블록체인 기술에서 트랜잭션의 무결성과 보안을 보장하는 데 사용

 

해시 함수

• 파이썬에서 딕셔너리는 내부적으로 해싱을 사용하여 O(1) 조회를 허용

 

해시 함수를 설계할 때 고려해야 할 요소

1. 해시 테이블 크기: 해시 함수가 반환하는 값은 해시 테이블의 크기에 맞아야 한다.
2. 충돌 최소화: 좋은 해시 함수는 서로 다른 두 개의 키가 동일한 인덱스에 해시하는 경우(충돌)를 최소화한다. 충돌이 발생하면 반드시 처리해야 한다.(ex) 체인 또는 오픈 주소 지정)

 

일반적인 해시 함수

1. 분할 방법(모듈러스)

• 모듈로 연산을 사용하여 해시를 계산.  ( h(x) = x \ mod m )
• m은 보통 소수로, 충돌을 줄이는 데 도움이 되는데, 소수는 1과 그 자체 외에는 나눗셈이 없기 때문에 두 개의 다른 숫자가 동일한 해시를 생성할 확률을 최소화하여  m이 소수인 경우, 해시 테이블의 키 분포가 더 균일해진다.

2. 곱셈 방법

• 이 방법은 키에 상수(ex) 황금 비율)를 곱하여 테이블 전체에 값을 분산시킨다.
• ( h(x) = \lfloor ((x \cdot A) \mod 1) \cdot m \rfloor \)
  • A는 상수(ex) 황금 비율)
  • m은 버킷의 수

이 방법은 소수를 사용한 직접적인 모듈식 연산을 피하고, 대신 키에 황금비와 같은 상수를 곱하여 균일한 분포

 

3. 문자열 해싱

• 문자열 키는 해시 테이블에서도 흔히 볼 수 있으며 해시 함수는 문자열을 인덱스로 변환해야 한다.
• 문자열 해싱의 일반적인 방법: 문자열을 문자 시퀀스로 취급하고 문자 값의 가중치 합계를 계산

 

해시 테이블 충돌 처리하기

• 해시 테이블에 데이터를 삽입할 때 두 개의 키가 동일한 인덱스(버킷)에 매핑되어 충돌 발생 가능

 

1. 체인 연결(분리 연결)

• 작동 방식
  • 충돌이 발생하면(두 개의 키가 동일한 버킷에 매핑되는 경우) 해당 버킷에 연결된 목록 생성
  • 충돌하는 새 값은 같은 버킷의 연결된 목록에 추가된다.
• 장점
  • 구현이 간단
  • 해시 테이블은 키의 개수에 제한 없이 저장 가능
• 단점
  • 충돌이 빈번한 경우 링크된 목록을 순회하면 시간 복잡성이 증가하므로 검색 및 삽입의 효율성이 떨어진다.
  • 연결된 목록에서 추가 포인터를 유지해야 하는 오버헤드로 인해 공간 활용도가 떨어진다.

 

2. 오픈 어드레싱

• 오픈 어드레싱은 테이블에서 새 값에 대한 다른 빈 버킷을 찾아 충돌을 해결
• 오픈 어드레싱의 메서드
• a. 선형 프로빙
  • 작동 방식: 충돌이 발생하면 알고리즘은 빈 버킷이 발견될 때까지 테이블의 다음 버킷을 확인
  • 장점
    • 구현이 간단
    • 전체 해시 테이블을 사용하므로 공간을 효율적으로 사용가능
  • 단점
    • 기본 클러스터링: 해시 인덱스가 가까운 값은 클러스터를 형성하는 경향이 있어 향후 더 많은 충돌발생 가능하여 성능이 저하될 수 있다. 
    • 테이블이 가득 차면 빈 버킷을 검색하는 속도 감소
• b. 이차 프로빙
  • 작동 방식: 선형 프로빙에서처럼 바로 다음 버킷으로 이동하는 대신 충돌 지점에서 빈 버킷이 발견될 때까지 이차 단계로 이동
  • 장점:
    • 선형 프로빙에 비해 클러스터링이 줄어든다
    • 테이블 전체에 값을 더 잘 분산시킨다
  • 단점
    • 2차 클러스터링: 1차 클러스터링을 줄이지만, 동일한 인덱스에 해시하는 키는 동일한 이차 프로빙 패턴을 따르기 때문에 키 간에 충돌이 발생 가능
• c. 이중 해싱
  • 작동 원리: 두 개의 해시 함수를 사용하여 프로브 시퀀스를 결정 -> 충돌이 발생하면 두 번째 해시 함수가 빈 버킷을 찾기 위해 얼마나 멀리 이동할지 결정
  • 장점
    • 기본 및 보조 클러스터링을 모두 최소화
    • 선형 또는 이차 프로브보다 해시 테이블 전체에 더 나은 분포를 제공
  • 단점
    • 구현하기가 더 복잡

 

추가

set

• 해시 테이블로 구현되어 있다. 
• 그래서 set에서 in 연산을 할 때는 해당 값이 저장된 위치를 바로 찾아가서 검색하는데, 이 과정이  O(1)의 시간 복잡도를 가진다.
• 즉, set은 내부적으로 해시 테이블을 이용해 값을 저장하고 탐색하기 때문에, 값이 어느 위치에 있는지를 즉시 알 수 있기에 검색시간이 O(1)이다.

 

 

문제

'''
arr = [1,2,3,4,8] target=6 return=True
arr = [2,3,4,9] target=10 return=False

'''

def solution(arr, target):
    # 중복 없이 숫자 쌍을 찾아야 하므로, arr를 집합으로
    seen = set()

    for num in arr:
        # 현재 숫자로부터 필요한 다른 숫자를 계산
        complement = target - num

        # complement가 seen에 있고, num이 complement와 다를 때만 True를 반환
        if complement in seen:
            return True

        seen.add(num)

    return False


print(solution([1,2,3,4,8],6))
print(solution([2,3,4,9],10))
print(solution([1,5,2,4],2))

 

def solution(string_list, query_list):
    string_set = set(string_list)  # string_list를 set으로 변환, O(n)
    
    result = []
    for query in query_list:  # query_list에 대해 순차적으로 확인, O(m)
        if query in string_set:  # O(1) (해시 테이블을 이용한 탐색)
            result.append(True)
        else:
            result.append(False)
    
    return result

 

완주하지 못한 선수

 

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

def solution(participant, completion):
    hashtable= {}
    for i in participant:
        if i not in hashtable:
            hashtable[i]=1
        else:
            hashtable[i]+=1
    for i in completion:
        if i in hashtable:
            hashtable[i]-=1
    for k,v in hashtable.items():
        if v == 1:
            return k


print(solution(["leo", "kiki", "eden"],["eden", "kiki"]	))

 

할인 행사

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

def solution(want, number, discount):
    hashtable = {}

    for i in range(len(want)):
        hashtable[want[i]] = number[i]

    cnt=0
    for i in range(len(discount)-9):
        hashtable2 = {}
        for j in range(i,i+10):
            if discount[j] not in hashtable2:
                hashtable2[discount[j]] = 1
            else:
                hashtable2[discount[j]] += 1
        if hashtable == hashtable2:
            cnt+=1

    return cnt

print(solution(["banana", "apple", "rice", "pork", "pot"],[3, 2, 2, 2, 1], ["chicken", "apple", "apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana"]	))
print(solution(["a", "b"], [1, 9], ["b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "a"]))
print(solution(["banana", "apple", "rice", "pork", "pot"],[3, 2, 2, 2, 1], ["apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana", "chicken", "apple"]))

 

오픈채팅방

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

초반 수도코드

def solution(record):
    answer = []
    dict = {}
    for i in record:
        if i의 첫 단어가 'Enter':
            dict[i의 두번째 단어] = i의 세번째 단어
            print(i의 세번째 단어님이 들어왔습니다)
        elif i의 첫 단어가 'Leave':
            print(i의  dict[i의 두번째 단어]에 value 이 나갔습니다)

        elif i의 첫 단어가 'Change':
            dict[i의 두번째 단어] = i의 세번째 단어로 변경

    return answer

print(solution(["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"]))
#결과: ["Prodo님이 들어왔습니다.", "Ryan님이 들어왔습니다.", "Prodo님이 나갔습니다.", "Prodo님이 들어왔습니다."]

변경 답

def solution(record):
    answer = []
    dict = {}
    for i in record:
        parts = i.split()
        action = parts[0]
        uid = parts[1]

        if action == "Enter" or action == "Change":
            nickname = parts[2]
            dict[uid] = nickname

    for i in record:
        parts = i.split()
        action = parts[0]
        uid = parts[1]
        if action == "Enter":
            answer.append(f"{dict[uid]}님이 들어왔습니다.")
        elif action == "Leave":
            answer.append(f"{dict[uid]}님이 나갔습니다.")

    return answer

 

베스트앨범

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

from pydoc import plain


def solution(genres, plays):
    answer = []
    dict = {}
    for i in range(len(genres)):
        if genres[i] not in dict:
            dict[genres[i]] = plays[i]
        else:
            dict[genres[i]] += plays[i]
    dict2 = {}
    for i in range(len(genres)):
        if genres[i] not in dict2:
            dict2[genres[i]] = [(i, plays[i])]
        else:
            dict2[genres[i]].append((i, plays[i]))

    sorted_genres = sorted(dict.items(), key=lambda x: x[1], reverse=True)

    for genres,k in sorted_genres:
        sorted_songs = sorted(dict2[genres],  key = lambda x: (-x[1], x[0]))

        answer.extend([song[0] for song in sorted_songs[:2]])

    return answer

 

신고 결과 받기

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

def solution(id_list, report, k):
    answer = []

    reporter_dict = {user: set() for user in id_list}
    reported_dict = {user: 0 for user in id_list}

    for i in report:
        parts = i.split()
        reporter = parts[0]
        reported = parts[1]

        if reported not in reporter_dict[reporter]:
            reporter_dict[reporter].add(reported)
            reported_dict[reported] += 1
  
    blocked_users = {user for user, count in reported_dict.items() if count >= k}


    for reporter in id_list:
        count = sum(1 for user in reporter_dict[reporter] if user in blocked_users)
        answer.append(count)
    return answer