Hash Table, Radix, Binary Trie

 * Hash Table

- 최악의 경우를 따지지 않고, 평균적인 경우 즉 대부분의 경우에만 가능한 자료구조

- 조건에 맞으면 동작이 상수 시간 안에 끝나고, 간단하다.

- delete가 복잡하다. delete가 많은 상황에서는 쓰지 않는다.

- idea : 지정석. ex) 100만개의 가능한 키가 모두 등장.

- 정의 : 키 값 k,  k->h(k)

 h(k) : Hash Function. 범위는 0부터 배열의 크기-1 까지.

- k는 h(k)에 저장한다.

- Hash function. (입력값과 무관해 보이는 결과값을 원함)

 k % n

 (p*k) % n

 string folding

-Overflow handling (거의 발생하지 않는다. 따라서 성능에 특별한 영향을 안 줌)

 Open Addressing : linear probing(+1, +2 ...), quadratic probing(^2, ^3 ....) , rehashing(다른 hash함수 사용)

, random probing( pseude random number generator 사용)

 Chaining : 해당 인덱스를 링크드 리스트로 만들어서 저장

 Overflow bucket : 특정 공간을 만들어서 overflow된 값들을 저장. 디스크에서 주로 사용.

 Dynamic Hashing : 넘치면 두배로 늘림. 늘린후 hash값을 모두 재계산 하거나 lazy separation을 사용

 Bloom Filter : hash table보다 훨씬 큰 bitmap filter를 사용. table에 없는 값을 search할 경우 filter에서 걸러짐. 실제로 많이 사용됨.

 * RADIX

-내부 구조에 관심을 가져보자

-많은 경우에 O(nlog n). 범위가 좁고 개수가 적당할수록 성능이 보장됨

- Compression : Run-Length Encoding, Differential Encoding, Huffman Encoding

  Huffman Encoding

- idea : 자주 등장하는 character를 짧은 bit sequence로 표현.

- 각 character의 등장 확률이 미리 주어졌을 때, 최적의 prefix-tree code 생성

- radix의 한 예. tree의 좌, 우가 의미하는 바가 key의 내용에 관계가 있음.

- counting sort : 배열의 데이터가 곧 해당하는 인텍스 넘버의 개수.

- bucket sort : 배열에 버켓을 범위별로 나눠서 넣은 후 각각을 sort.

- radix sort : 배열에 버켓을 2개만 놓고 1개는 첫비트가 0인것, 나머지 1개는 1인것으로 넣음. 그리고 반복.

 * Binary Trie

- retrieve, 꺼내기 쉬운 자료구조

- 키 : integer ( 2진수로 표현 )

- 왼쪽 child는 해당 비트가 0 인 것, 오른쪽 child는 해당 비트가 1인 것.

- Compressed Binary Trie : 특정 노드 이하로 하나의 leaf만 존재할 경우, 그 leaf까지의 모든 비트를 한 레이블에 모아서 적어놓음. delete가 복잡해짐

- Radix trie, Patricia : compressed binary trie의 변형. interner node를 없앰.

- string trie : child로 가는 edge가 해당 칸의 문자열을 의미.

- Aho-corasick Trie : multiple keyword matching.

- Suffix tree : index structure. compressed trie 기반. 사전에 사용.