[알고리즘]해쉬테이블_hash table

220617 작성

<본 블로그는 Chan-Su Shin님의 유튜브를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=Bzmepm6pYQI 

 

1. hash table

: 정렬이 안된다

: 검색 속도 o(1) 걸린다       but 오래 걸리면 o(n)

: key-value 관계이다

: 검색속도가 매우 빠르다

: 해시코드로 인덱스 배열 -> linked list

: 충돌이 든다

 

2. hash table 큰 특징

- table 은 list!

- hash function을 만든다

- 충돌 해결 방안을 찾는다

 

3. hash function

: division hesh func

f(k) = k % m

: perfect func

key -> slot (1대 1)

비이상적

: c - universal hash func

Pr{f(x) == f(y)} == 1/m

충돌확률

- multiplication

- folding

- mid

- extraction

 

4. 충돌회피

- open addressing (linear probing & quadratic probing & double hashing)

- chaining