[알고리즘] 해시(Hash), 파이썬 딕셔너리(Dictionary)

해시(Hash)

• 데이터를 다루는 방법 중 하나로, O(N) 시간 복잡도를 가진 연산을 O(1) 시간 복잡도로 해결할 수 있다.
• key-value 형태로 데이터가 저장된다.

 

 

해시 함수(Hash function)

• 임의의 길이를 갖는 임의의 데이터를 고정되 길이의 데이터로 매핑하는 단방향 함수
• 해시 값 : 해시 함수를 적용하여 나온 값, 해시 코드, 해시섬(sum), 체크섬 등으로 불린다.
• 해시 충돌(hash collision) : 서로 다른 키가 같은 해시가 되는 경우 

 

해시 테이블(Hash Table)

• 연관 배열 구조(associative array)를 사용해서 데이터를 key, value으로 저장하는 자료구조
  • 연관 배열 구조 : 키 1개와 값 1개가 1:1으로 연관되어 있는 자료구조

 

딕셔너리(Dictionary)

• dictionary는 해시 테이블(hash table)

 

---

Set

- 순서가 없는 데이터의 집합

- 중복 허용 X

- HashSet, TreeSet

 

 

Map

- key, value가 한 쌍으로 이루어지는 데이터의 집합

- 순서가 없는 데이터의 집합

- key 중복 허용 X, value는 중복 허용

- HashMap, TreeMap, Hashtable, Properties

 

Set	Map
value	key : value
값 중복 X	key 중복 X, value 허용
contains(value)	containsKey(key)
get 불가능	get(key)

 

Hash

- 순서가 없다.

 

 

Tree

- 트리 구조로, 순서 유지

 

Hash	Tree
순서 없음	순서 유지
O(1)	O(log n)

---

 

HashMap vs HashSet vs TreeMap vs TreeSet

HashMap	HashSet	TreeMap	TreeSet
key 중복 X value 허용	value 중복 X	key 중복X value 허용	value 중복X
순서 없음	순서 없음	순서 유지	순서 유지

 

 

 

해시 문제 - 7785번 회사에 있는 사람

https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

 

from collections import defaultdict
#n = 4 # 출입 기록 수
# arr = ['Baha enter', 'Askar enter', 'Baha leave', 'Artem enter']

# enter 출근, leave 퇴근
# 대소문자 구분
# 현재 회사에 있는 모든 사람을 구하는 프로그램 작성
n = int(input())
dict = defaultdict(str)

for x in range(n):
    name, opt = input().split()
    if dict[name] == 'enter' and opt == 'leave':
        del dict[name]
    else:
        dict[name] = opt

for x in sorted(dict.keys(),reverse=True):
    print(x)

 

 

해시 문제 - 14425번 문자열 집합

https://www.acmicpc.net/problem/14425

from collections import defaultdict
n, m = map(int, input().split())
answer = 0
S = defaultdict(int)
for x in range(n):
    key = input()
    S[key] = 1

for x in range(m):
    key = input()
    if S[key]:
        answer += 1
print(answer)