Hash란?

---

임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 의미한다.
Hash는 데이터의 값을 이용해 저장하거나, 찾을 수 있다.
python의 dictionary를 생각하면 이해하기 쉬우며, python은 dictionary로 hash를 제공한다.

기존의 자료 구조들은 탐색이나 삽입에 선형시간이 걸리지만 Hash를 이용하면 즉시 위치를 참조할 수 있으니 시간을 절약할 수 있다.

Hash 사용목적

---

1. 인덱스 값을 숫자가 아닌 다른 값(문자열 등)을 사용하고 싶을 때

2. 빠른 접근 / 탐색

3. 집계가 필요할 때

ex) 백준 10816 숫자카드2 이분탐색문제지만 해시로도 풀 수 0

    import sys
    input = sys.stdin.readline
    N = int(input())
    li1 = list(map(int,input().split()))
    M = int(input())
    li2 = list(map(int,input().split()))
    dic = {}

    for n in li1:
        if n in dic:    dic[n] += 1
        else:   dic[n] = 1

    for n in li2:
        try:    print(dic[n])
        except:   print(0)
        

시간 복잡도

---

▶ O(1)

dictionary와 list 비교

Operation		Dictionary	List
Get Item		O(1)		O(1)
Insert Item		O(1)		O(1) ~ O(N)
Update Item		O(1)		O(1)
Delete Item		O(1)		O(1) ~ O(N)
Search Item		O(1)		O(N)