Hash

• 자료의 삽입, 찾기, 삭제의 수행시간이 $O(1)$ $\cdots$ Linked List 는 $O(n)$, Tree는 $O(logn)$
• 수행시간은 빠르지만 메모리 공간은 많이 소모.
• 중복성 문제(collision) 가 발생하기 때문에 해결해야함.

Direct Address Table

• 값이 k인 자료를 k번째 주소에 저장하는 방법(단, 0≤k≤m)
• 미리 m개짜리 배열 T[]가 준비
• 아무 데이터가 들어가있지 않으면 nil 저장

• 메모리의 크기에 한계가 있기 때문에 정해진 키 값 이상은 저장할 수 없다

• 큰 키 값을 저장하기 위해서는 메모리의 크기를 늘려야함 → 공간 낭비!

• 이를 해결하기 위한 hash table

• hash function 정의 필요

  $H : K → \{0,1,2, \cdots, m-1 \}$

  k : 가능한 모든 키들의 집합, m : hash table 크기

• 위의 정의만 만족하면 다야한 종류를 만들어낼 수 있다.

  ex : $H(k) = k \ mod \ n$

  

Hash Table : Chaining과 Collision

• Hash 함수는 n:1대응 함수이므로 같은 해시값을 갖는 키가 두 개 이상 존재할 수 있음
• 기존 알고리즘으로 같은 저장소에 두 개 자료가 들어가면 내용이 덮어쓰여지게 됨.
• 따라서 chaining 기법을 사용!