[python] 해시(Hash)와 딕셔너리(dict)

프로그래머스 알고리즘 고득점 kit 해시

 

- 해시는 해시 함수와 해시 테이블의 개념을 기반으로 한다.

- 언제쓸까? 정보를 빨리 찾고 싶을때, 특히 string을 기반으로 정보를 관리할 때 (대부분 Key가 String), 중복을 확인할 때

- 데이터가 너무 길거나 많을때, 한 번 계산한 해시 값을 재활용 할 수 있을 때(매번 데이터를 다 읽지 않아도 됨)

* 간혹 서로 다른 데이터가 같은 해시 값을 가지는 충돌이 발생할 수 있어, 중요한 상황에서는 해시와 == 를 함께 사용

- get/put/getorDefault

 

 

1. 파이썬 내장 함수 hash()

- 입력 데이터를 특정 고유값을 가지는 정수(해시값)로 매핑하는 함수

- 동일 값은 동일한 해시 값을 반환한다.

- 숫자의 경우 데이터 타입은 관계 없다(int, float 모두 값만 같으면 같게 나옴)

- 데이터를 숫자로 바꿔놓기 때문에 비교가 빠르다

(예: 두 백만글자짜리 문자열을 비교할 경우, 해시 대신 ==로 비교하면 데이터를 하나 하나 확인해야 한다.)

hash('hi') # 7165339163956087309
hash(1) # 1
hash(1) == hash(10) # False
hash(1) == hash(1.0) # True
hash(True) == hash(1.0) # True

 

2. 해시 테이블(Hash Table)

- Key-Value 쌍 데이터를 저장하는 자료구조로, 해시 값을 기반으로 데이터를 효율적으로 검색한다.

- Python에서는 해시 테이블의 구현을오 딕셔너리(dict)를 사용한다.

- 해시는 평균적으로 O(1)의 시간 복잡도로 키에 접근할 수 있어 빠른 검색 속도라는 장점이 있다.

- 해시 테이블의 키로 사용하려면, 객체가 변경 불가능(immutable)하고, 해시 함수를 사용할 수 있어야 한다.

- 사용 가능: 숫자, 문자열, 튜플

- 불가능: 리스트, 딕셔너리, set은 가변 객체로 해시 함수 사용 불가능 해 키로 사용할 수 없다.

 

3. hashmap

- 해시 테이블을 구현한 자료 구조, 예: dict 

 

4. dict

greeting = dict({
    "ko" : "안녕",
    "en" : "Hi"
})
type(greeting)

# key에 해당하는 value 가져오기
greeting.get("ko") # '안녕'

# 해당 key없으면 "없음" 표시
greeting.get("jp","없음") # '없음'

# key값들만 가져오기
greeting.keys() # ['ko','en']

# key,value쌍 튜플로 모두 가져오기
greeting.items() #  [('ko','안녕'),('en','Hi)]