🐍[파이썬] Hash, Hash Map, Hash Set

1. 해시(Hash)란?

해시는 데이터를 빠르게 검색할 수 있도록 특정 값을 고유한 정수값(해시값)으로 변환하는 과정임. 이 과정은 일방향 함수로, 입력값을 해시값으로 변환하지만 해시값에서 입력값을 복원할 수 없음.

2. 해시맵(Hash Map)

• 해시맵은 키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료 구조임.
• 파이썬에서는 딕셔너리(Dictionary) 가 해시맵에 해당함. 키는 해시값으로 변환되어 빠른 조회가 가능함.

사용 이유

• 빠른 조회: 해시맵은 평균적으로 O(1)의 시간 복잡도로 데이터를 조회할 수 있음.
• 중복을 허용하지 않음: 키가 중복되지 않기 때문에 유일한 데이터를 저장할 수 있음.
• 효율성: 데이터를 저장하고 관리하는데 매우 효율적임.

관련 함수 및 메서드

• dict.get(key, default=None): 키에 해당하는 값을 반환. 키가 없으면 default 값을 반환.
• dict[key]: 키에 해당하는 값을 반환. 키가 없으면 KeyError 발생.
• dict.update(other_dict): 다른 딕셔너리의 항목을 현재 딕셔너리에 추가함.
• dict.items(): 딕셔너리의 모든 (key, value) 쌍을 반환함.
• dict.keys(): 딕셔너리의 모든 키를 반환함.
• dict.values(): 딕셔너리의 모든 값을 반환함.

3. 해시셋(Hash Set)

• 해시셋은 중복되지 않는 데이터를 저장하는 자료 구조로, 집합(Set)의 특성을 갖음.
• 파이썬에서는 set 자료형이 해시셋에 해당함.

사용 이유

• 중복 데이터 제거: 해시셋은 중복을 허용하지 않기 때문에 고유한 데이터를 저장함.
• 빠른 검색: 집합의 원소를 O(1) 시간 복잡도로 확인할 수 있음.

관련 함수 및 메서드

• set.add(elem): 원소를 셋에 추가함.
• set.remove(elem): 셋에서 원소를 제거함. 원소가 없으면 KeyError 발생.
• set.discard(elem): 원소를 셋에서 제거함. 원소가 없어도 오류 발생하지 않음.
• set.pop(): 셋에서 임의의 원소를 제거하고 반환함.
• set.union(other_set): 두 셋의 합집합을 반환함.
• set.intersection(other_set): 두 셋의 교집합을 반환함.
• set.difference(other_set): 두 셋의 차집합을 반환함.
• set.symmetric_difference(other_set): 두 셋의 대칭 차집합을 반환함.

4. 해시 충돌(Hash Collision)

해시 함수는 다양한 입력값을 고유한 해시값으로 변환하려 하지만, 결국 해시값이 중복될 수 있음. 이를 해시 충돌이라고 하며, 이를 해결하기 위해 다양한 방법이 사용됨.

• 체이닝(Chaining): 충돌이 발생하면 동일한 해시값을 가진 항목들을 리스트나 링크드 리스트로 연결하여 저장함.
• 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 자리를 찾아 데이터를 저장함.

5. 코딩테스트에서의 활용

• 중복 원소 확인: set을 이용해 중복 원소를 빠르게 확인하고 제거할 수 있음.
• 두 리스트의 교집합 구하기: set의 intersection 메서드를 사용하여 두 리스트의 공통된 원소를 빠르게 구할 수 있음.
• 단어 출현 횟수 세기: dict를 이용하여 각 단어의 출현 횟수를 계산하는 문제를 풀 수 있음.

예시 코드

# 해시맵 예시
my_dict = {'apple': 3, 'banana': 2, 'orange': 5}
print(my_dict.get('apple'))  # 3
print(my_dict.get('grape', 0))  # 0

# 해시셋 예시
my_set = {1, 2, 3, 4}
my_set.add(5)
print(my_set)  # {1, 2, 3, 4, 5}

# 교집합 구하기
set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1.intersection(set2))  # {2, 3}

# 단어 출현 횟수 세기
words = ["apple", "banana", "apple", "orange"]
word_count = {}
for word in words:
    word_count[word] = word_count.get(word, 0) + 1
print(word_count)  # {'apple': 2, 'banana': 1, 'orange': 1}

위의 내용을 참고하여 코딩테스트에서 해시와 관련된 문제를 효율적으로 해결할 수 있음.