[ch11]해시 테이블

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ]

---

* 해시 테이블(해시 맵)

: 키를 값에 매핑할 수 있는 구조

- 해시 함수 

: 임의의 크기의 데이터를 고정 크기의 값으로 매핑하는 데 사용할 수 있는 함수

= 해싱 : 해시 함수를 사용해 해시 테이블에 인덱싱하기 위한 것 

 

* 동일 키 값 - 충돌 발생

1. Separate Chaining

: 연결 리스트로 연결

2. Open Addressing

: 충돌 발생 시, 테이블 공간 내 탐사를 통해 빈 공간을 찾아 해결한다.

---

ex) 빈도 요소 순에서 상위 k 번째 요소 

import collections

nums = [1,1,1,2,2,3]
k = 2

count = collections.Counter(nums)

print(count)

print(
    list(zip(*count.most_common(k)))[0]    #--zip 함수 와 아스테리스크(*) 
)

* zip 함수

# 2개 이상의 시퀀스에서, 짧은 길이를 기준으로
# 일대일 대응하는 새로운 튜플 시퀀스 생성

a = [1,2,3,4,5]
b = [2,3,4,5]
c = [3,4,5]

list(zip(a,b)) 
# [(1, 2), (2, 3), (3, 4), (4, 5)]

d = list(zip(a,b,c))
# [(1, 2, 3), (2, 3, 4), (3, 4, 5)]

d[0][0] = 0 # tuple 요소는 수정 불가, Typeerror 발생

* 아스테리스크(*)

: Unpack 의 역할로, 주로 튜플이나 리스트를 언패킹하는 데 사용한다.

cc = ['a','b','c','d']
print(*cc)

def func(*params):
    print(params)

func('aa','bb','cc')

---

* Counter 객체 간 덧셈,뺄셈 가능

# 프로그래머스 - 해시
from collections import Counter

participant = ['m','s','m','a']
completion = ['s','a','m']

p = Counter(participant)
c = Counter(completion)
res = p-c

key = list(res.keys())[0]
# completion 에 없는 m 1개 리턴