[자료구조] 해시

해시

0) 정의

-> 데이터를 다루는 기법 중 하나로, 검색과 저장에 아주 유용한 구조이다. key-value 쌍으로 데이터를 저장함

1) 해시함수란 ? 

-> 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수 

 

2) 해시 구현 방법 

· 딕셔너리에 삽입

hash = dict()
hash[1] = 'apple'
hash['banana'] = 3
hash[(4, 5)] = [1, 2, 3]
hash[10] = dict({1: 'a', 2: 'b'})

위와 같은 형태로 해시 함수를 사용할 수 있지만, 집합과 배열은 해시 함수의 키 값으로 사용할 수 없다. (인덱스로 변환 불가) 

 

ex) hash({3, 5}), hash([3, 5]) -> 사용 x 

 

· 딕셔너리 값 추출 

hash.pop(1)   # 'melon'
hash.pop('banana')   # 10
hash.pop((4, 5))   # [1, 2, 3]
hash.pop(10)   # {1: 'a', 2: 'b'}

· 딕셔너리 값 삭제 

del hash[1]
del hash['banana']
del hash[(4, 5)]
del hash[10]

· 딕셔너리 루프 (keys, values, items)

for k in hash.keys():
    print(k)
    
for v in hash.values():
    print(v)
    
for k, v in has.items():
    print(k, v)

· 딕셔너리 정렬 -> sorted()를 통해 정렬하며, 항상 list 타입 반환 

hash = dict({1:10, 3:12, 5:7, 7:6, 4:5})

# 오름차순 정렬 
sorted(hash.keys(), key = lambda x: x)
sorted(hash.values(), key = lambda x: x)
sorted(hash.items(), key = lambda x: x)

# 내림차순 정렬 
sorted(hash.keys(), key = lambda x: -x)
sorted(hash.values(), key = lambda x: -x)

내림차순 정렬시에 key, values()와 달리 items()을 사용할 경우 오류를 반환하는데, 이는 items()의 반환 값이 튜플이기 때문에, 정렬 x

(튜플에는 - 값을 줄 수 x) 

 

∴ 다음과 같이 정렬 할 수 있음

sorted(hash.items(), key = lambda x: (x[0], x[1]))   # key 오름차순, value 오름차순
sorted(hash.items(), key = lambda x: (-x[0], x[1])   # key 내림차순, value 오름차순 
sorted(hash.items(), key = lambda x: (x[1], [0])   # value 오름차순, key 오름차순