[알고리즘] 해시 테이블

• INSERT, SEARCH, DELETE 지원하는 dynamic set 필요
• hash table : effective data structure for implementing dictionaries

Direct-address table

Direct-Address-Search(T,k)
	return T[k]
Direct-Address-Insert(T,x)
	T[x.key] = x
Direct-Address-Delete(T,x)
	T[x.key] =NIL

T[k] 에는 포인터가 들어간다 (element 안들어감)
비어있으면, NIL

이 모든것이 O(1) 수행시간 안에 끝난다

전체 universe U크기가 커서, 낭비되는 메모리 많음

Hash table

element is stored in slot h(k)
we use a hash function h to compute the slot from the key k
k 는 hashes to slot h(k)(hash value of k )

• collision(두개이상이 같은 해쉬값을 가진다 ) U가 m보다 훨씬 크기 때문이다
  -> chaining / open addressing

• chaining
  linked list 형태로 해쉬값이 같은 element 들을 연결했다 ,, 배열에는 값이 들어가느느 것이 아니라 첫 원소를 가르키는 pointer 가 들어간다
  만일 존재하지 않다면 NIL

• CHAINED HASH INSERT(T,x)
  insert x , head of list T[h(x.key)]

  최악의 경우도 O(1)시간수행을 하긴한다 , insert하는 애는 리스트에 이미 존재하지 않는다고 가정한다. , 만일 존재하는지 확인하고 싶다면 search 연산을 수행해야 한다.
  

• CHAINED_HASH_SEARCH(T,k)
  search key k , T[h(k)]리스트에서 찾는다

  h(k) 슬롯에 있는 요소들의 길이에 비례한 수행시간을 가진다

  doubled link 면 delete는 상수
  search 와 동일 한 O(n) 은 single link

  chaining 기법을 사용하면 평균적인 수행시간은 세 함수 모두 상수시간