HashTable

인덱스 찾기

hash라는 메서드로 노드의 인덱스를 정한다.
hash method 특징

• one way
  • 키로 주소(인덱스)를 알아낼 수는 있는데 인덱스로 키를 알아내지는 못함
• Deterministic
  • 주소고정

how to deal with collision

 
 
순서보장 안됨

같은 주소에 여러개 저장 - separate chaining

이미 다른게 저장되어있으면 빈거 찾을때까지 다음으로 - Linear Probing (open addressing)


우리가 할 것은 seperate chaining.
 
 

big O

hash method = 0(1)
set = 0(1)
get = 0(1)  -  seperate chaining 일때.