Dictionary ADT

key를 가지고 탐색을 진행,

동일한 key를 가지는 원소가 있을 수 있음.

=> 중복 가능

 

List - Based Dict

log file / audit trail : unsorted sequence

insert : O(1)

find && erase : O(n)

log file -> insert는 빠르지만, 나머지 탐색, 삭제는 느림

 

Search Table

search table == lookup table, table = 배열 / sorted array

정렬된 배열 -> 이진 탐색 떠올리기

이진 탐색 -> sorted array떠올리기

 

find : O(log(n)), 이진 탐색을 이용

insert : O(n), 원소 재배치

remove : O(n), 원소 재배치

 

search table은 size가 작거나 공통된 연산이 있을 때 효율적이다.

 

Hash Table

range : [0, N - 1]

h(x) = x mod N

h(x)가 hash value를 의미

원소 (k, o)를 삽입하는 과정 -> index i = h(k)

 

Seperate chain

중복되는 key 값이 나오면 같은 index에 연결리스트로 구현

 

Linear Probing

중복되는 key 값이 나오면 비어있는 index를 찾을 때 까지 index += 1

 

find : 해당 key의 index부터 탐색을 진행

-> 비어있을 때까지 진행 

but) 만약 remove 연산을 진행했다면 비어있음에도 뒤에 원소가 존재할 수 있으므로

remove 연산을 통해 삭제한 index는 available 상태로 변환

 

remove : 앞서 설명했듯이 원소는 삭제하되, 해당 index의 상태를 empty가 아닌 available로 변환

insert : index부터 증가시켜가며 비어있는 || available인 index를 찾아 삽입

 

Double Hashing

linear probe 처럼 index += 1이 아니라

index += (q - (k mod q))로 진행 (q < N, q is prime number)

2차 해시함수의 division method는 0이 되면 안됨

 

최악의 경우 insert, remove, find 연산은 O(n)이 걸리는 반면,

가장 최고의 효율을 보일 때는 O(1)이 걸린다.