[알고리즘/해쉬(Hash)] 개념, 해시 충돌(Hash Collision), Python-Dictionary 문법

Hash 개념

Key : Value 형태를 갖는 자료구조

• Key: 이름 - Value: 전화번호
• 모든 데이터 타입으로 접근 가능

Hash Table

💡 Key - Value

Hashing: Hash Function

• Key: 고유한 값, 해시 함수의 input(저장 시 값을 해시 함수로 바꾸어 저장함)
• Value: bucket(저장소)에 최종적으로 저장되는 값, key와 매칭되어 저장, 검색, 접근, 삭제 가능
• Hash Function: key 값을 Hash로 변경해 주는 함수
  ⇒ Hash Table에서 key 값은 해시 함수를 통해 해시로 변경(index 매핑)되며, 이 Hash 값은 key와 매칭되어 bucket(저장소)에 저장됨

 

해시 충돌(Hash Collision)

필연적 문제

• Hash를 이용한 자료구조 방식에서 필연적으로 나타날 수 있는 문제
  • 무한한 값(key)를 유한한 값(Hash)로 표현하면서 서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 됨
  • 이게 무슨 말이야?

• 💡 B와 C라는 서로 다른 key 값이 해시 함수를 통과 → 4라는 동일한 Hash 값을 부여받게 됨 ⇒ 해시 충돌

 

해결 방법

• Chaining
  • 해시 테이블에서 동일한 해시 값에 대해 충돌 발생 → 그 위치에 있던 버킷이 다음 키 값을 연결하는 방법
  • 연결리스트 자료구조를 활용하여 bucket에서 연결될 수 있는 entry에 제한을 두지 않고 체인 형태로 연결하는 것
  • 과정: key의 해시값 계산 → 해시값에 해당하는 List index를 구함 → 같은 해시값을 가진 key가 있다면(충돌) List로 연결

 

• Open Addressing ⇒ Python의 해결 방법
  • 하나의 bucket에 하나의 entry만 들어갈 수 있는 형태
  • 해시 충돌 발생 시, 비어있는 배열 슬롯이 발견될 때까지 array의 위를 검색(저장공간이 정해져 있음)
  • 즉, 배열의 빈 공간을 탐사하면서 해시 충돌을 피하는 방식

 

Python - 언제 쓸까?

Dictionary

• Python에서는 Dictionary 형태로 해시 테이블이 구현되어 있음
• 💡 collection 모듈
  index값이 숫자가 아닌 다른 값
  빠른 접근, 탐색, 집계가 필요할 때 
  • 중복이 불가능한 collection 자료형(List, Tuple, Set, Dictionary)
  • key는 중복 불가, key에 리스트를 사용할 수 없음
  • index 값이 숫자가 아닌 다른 값(문자열, 튜플)을 사용할 때 dictionary 사용
  • 빠른 접근, 탐색이 필요할 때
  • 집계가 필요할 때
  • (dictionary 함수의 시간 복잡도: 대부분 O(1))

 

• Dictionary vs. List
  • 원소를 넣거나 삭제, 찾는 일이 많을 때는 Dictionary를 사용하는 것이 더 효율적임
  
  

  구분	Dictionary	List
  삽입	평균: O(1) 최악: O(n) - 해시 충돌	O(n)
  삭제	평균: O(1) 최악: O(n) - 해시 충돌	O(n)
  검색	평균: O(1) 최악: O(n) - 해시 충돌	O(n)

 

문법

• Init

# 기본
dict1 = {}
dict2 = dict()

# key-value 쌍을 가진 dictionary 선언
Dog = {
	'name': '젤리',
	'age': 6,
}
=> {'name': '젤리', 'age': 6}

# dictionary를 value로 가지는 dictionary 선언
Animals = {
	'Dog': {
		'name': '젤리',
		'age': 6
	},
	
	'Cat': {
		'name': '메롱',
		'age': 3
	}
}
=> {'Dog': {'name': '젤리', 'age': 6}, 'Cat': {'name': '메롱', 'age': 3}}

 

• Get

# []
dict = {'하이': 300, '헬로': 180, 3: 5}
dict['헬로'] # 180

# get 메소드 이용
dict = {'하이': 300, '헬로': 180}
dict.get('동동', 0) # 0, 딕셔너리에 해당 key가 없을 때 Key Error 대신 특정한 값을 가져오도록 함

dict = {'하이': 300, '헬로': 180}
dict.get('헬로', 0) # 180

 

• Set

# 삽입
dict = {'김철수': 300, 'Anna': 180}
dict['홍길동'] = 100
dict #{'Anna': 180, '김철수': 300, '홍길동': 100}

# 수정
dict = {'김철수': 300, 'Anna': 180}
dict['김철수'] = 500
dict # {'Anna': 180, '김철수': 500}

dict = {'김철수': 300, 'Anna': 180}
dict['김철수'] += 500
dict # {'Anna': 180, '김철수': 800}

 

• Delete

# del
dict = {'김철수': 300, 'Anna': 180}
del dict['김철수']
dict #{'Anna': 180}

my_dict = {'김철수': 300, 'Anna': 180}
del my_dict['홍길동'] # key가 없는 경우 Error 발생

# pop
my_dict = {'김철수': 300, 'Anna': 180}
my_dict.pop('김철수', 180) # 300

my_dict = {'김철수': 300, 'Anna': 180}
my_dict.pop('홍길동', 180) # 180 - key가 없는 경우 default로 리턴

 

• Iterate

# key 순회
dict = {'김철수': 300, 'Anna': 180}
for key in dict:
    print(key) # 김철수, Anna

# key-value 순회
dict = {'김철수': 300, 'Anna': 180}
for key, value in dict.items():
    print(key, value) # 김철수 300, Anna 180

 

---

• 참고자료
  • https://velog.io/@petcu1004/Python-해시-Hash
  • https://youtu.be/zFL29ydL9D8?si=Gm4GKimL-5jMvxgv
  • https://wayhome25.github.io/python/2017/06/14/time-complexity/
  • https://velog.io/@citizenyves/Hash-table2-hash-colision-해시충돌
  • https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table해시-해싱-해시테이블-자료구조의-이해-6ijyonph6o
  • https://yunaaaas.tistory.com/46