---

📍 해시 (Hash)

해시 (함수)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수
즉, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수

해시 함수를 적용하여 나온 고정된 길이의 값을 해시값(또는 해시 코드, 해시섬, 체크섬)이라고 함

📍 해시 테이블 (Hash Table)

해시 구조란 키(Key)와 값(Value)쌍으로 이루어진 데이터 구조를 의미

해시 테이블이란 해시 구조를 사용하는 데이터 구조
해시 테이블이란 검색하고자 하는 키값을 입력 받아, 해시 함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조

장점

• Key를 이용하여 데이터(Value)를 찾기에 검색과 저장이 아주 빠름
• Key에 대한 데이터가 있는지, 중복 확인이 쉬움

단점

• 저장공간이 좀 더 많이 필요함
• 여러 키에 해당하는 주소가 동일할 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요함 (충돌 해결 알고리즘)

시간 복잡도

• 일반적인 경우(충돌이 없는 경우): O(1)
  • 탐색) 인덱스로 값을 탐색하기에
  • 삽입) 해시 함수를 통해 인덱스가 정해지므로
  • 삭제) 인덱스와 인덱스 안의 값만 지워주면 되기 때문에 (순서를 다시 정리하거나 할 필요 X)
• 최악의 경우(모든 경우에 충돌이 발생하는 경우): O(n)
  • 탐색) 인덱스로 값을 탐색한 후 linked list를 순차탐색해야 함 (linked list 길이 n만큼 시간 소요)
  • 삽입) linked list의 탐색을 거치게 되므로
  • 삭제) linked list의 탐색을 거치게 되므로

dic의 모든 인덱스를 찾는 것이 아닌 key값이 ㅇㅇ인 것에 접근하면 되기 때문
해시테이블(딕셔너리)에 요소를 추가하면, 그 요소의 키 값을 hash()에 넣어 나온 숫자 값이 딕셔너리의 인덱스를 정하고, 그 인덱스에 key와 value를 저장하는 것

---

⭐ 파이썬에서의 해시

파이썬에서는 해시를 별도로 구현할 필요 없음
파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조

참고) 키 생성 함수는 파이썬의 기본 라이브러리 hash() 함수 사용

# 딕셔너리 생성
dic = {'name':'Jo', 'phone':'01012345678', 'birth':'1202'} # Key: name, Value: Jo ...
print(dic) # {'name': 'Jo', 'phone': '01012345678', 'birth': '1202'}

# Set (Key, Value 쌍 추가)
dic['age'] = '26'

# Set (값 수정)
dic['age'] = '27'

# Get (원소 가져오기)
print(dic['age']) # 27
print(dic.get('age')) # 27

# Delete (특정 key값 삭제)
# 1. del dic[key]
print(dic) # {'name': 'Jo', 'phone': '01012345678', 'birth': '1202', 'age': '27'}
del dic['age'] # 주의) key 없다면 keyError 발생
print(dic) # {'name': 'Jo', 'phone': '01012345678', 'birth': '1202'}

# 2. pop(key[, default])
dic.pop('birth') # 주의) Key 없다면 keyError 발생, defualt를 설정해주자
print(dic) # {'name': 'Jo', 'phone': '01012345678'}
print(dic.pop('birth', 'hi')) # Key 없기에 'hi' 출력 // hi

# Iterate (for문 이용하여 조회)
# 1. key로만 순회
for key in dic:
    print(key)
    # name
    # phone
# 2. key, value 동시 순회 (items() 사용)
for key, value in dic.items():
    print(key, value)
    # name Jo
    # phone 01012345678

# 그 외..
# 1. 특정 key가 딕셔너리에 있는지 없는지 조회 - in 사용
dic = {'조': 100, '권': 200}
print('조' in dic) # True
print("조" not in dic) # False

# 2. key 또는 value만 뽑아내는 방법
# key만: keys()
print(dic.keys()) # dict_keys(['조', '권'])
# value만: values()
print(dic.values()) # dict_values([100, 200])
# key - value 모두: items()
print(dic.items()) # dict_items([('조', 100), ('권', 200)])

---

✅ 해시는 언제 사용하면 좋을까?

1. 리스트를 쓸 수 없을 때
   리스트는 숫자 인덱스를 이용하여 원소에 접근함, 즉 list[1]은 가능하지만 list['a']는 불가능함
   인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용하려고 할 때 딕셔너리를 사용하면 좋음!

2. 빠른 접근 및 탐색이 필요할 때
   딕셔너리 함수의 시간복잡도는 일반적인 경우 O(1)이므로 아주 빠른 자료구조

3. 집계가 필요할 때
   원소의 개수를 세는 문제는 코딩 테스트에서 많이 출제되는 문제임
   해시와, collections 모듈의 Counter 클래스를 사용하면 아주 빠르게 문제를 풀 수 있음!

---