해시

참고문서: CLRS

hash

해시의 작업은 INSERT, SEARCH, DELETE 로 나눌 수 있다.

direct-address tables

직접 주소 테이블은, 어떤 값의 키 값을 직접적으로 테이블 키 값으로 활용하는 방법이다.

T[x.key] = x  # INSERT
return T[x.key] # SEARCH
T[x.key] = None # DELETE

직접 주소 테이블은 주로 실제 값의 키를 활용하는데, 주요 작업에 대해 O(1) 시간복잡도에 동작할 수 있다. 이 경우, 값의 키를 직접 테이블 키로 저장하므로 연결될 값에는 키가 빠져도 된다.
직접 주소의 경우 같은 값을 여러 번 저장 하려면, 같은 인덱스에 대해 doubly linked list로 값을 저장하면, 삭제시에도 상수 시간으로 제거할 수 있다. 직접 주소 테이블의 가장 단점은 전체 군 U(Universe)가 굉장히 클 수 있기 때문에, 직접 주소테이블이 모든 키에 대해 사용가능 하려면, 메모리적으로 실용적이지 않기 때문이다.

hash-table

해시 테이블은 전체 군 U에 대해 공간 복잡도를 O(|K|)로 제한하면서 시간 복잡도를 O(1)로 해줄 수 있다. 시간복잡도의 평균 복잡도가 O(1)이며, 반면 직접 주소 테이블은 최악 복잡도가 O(1)이다. 해시 테이블은 해시 함수를 써서 U 군의 값의 키를 실용적인 크기로 줄이는 것이 핵심이다. U -> {0, 1, ..., m-1}. 이 경우 전혀 다른 값이더라도 해시 함수에 의해 같은 키를 가지는 경우가 생기는데, 이를 충돌이라고 표현한다. 충돌을 해결하는데에 두 가지 방법이 있는데, chaining 방식과 open addressing이 있다.

chaining

chaining 방식은 키에 값을 저장하는 것에 대해 doubly linked list로 관리하며, 삽입에 대해 최악시간복잡도 O(1), 검색과 삭제에 대해 평균 복잡도 O(1)을 지원한다. 삽입의 경우 해시 함수를 통해 키를 찾고, doubly linked list의 tail이나 head에 붙이기만 하면된다. 검색과 삭제는 해시 함수를 통해 키를 찾고, 실제적으로 doubly linked list내에서 값을 찾아야한다. 그래서 최악 시간 복잡도는 해당 doubly linked list의 길이일 것이다.
chainig의 가장 최악 시간복잡도는 O(n) 이다. 모든 값들의 키가 해시 함수에 의해 같은 키를 가지는 경우이다. 이 경우 doubly linked list의 길이는 n이 되기 때문이다. 역으로, 해시 함수가 모든 값들의 키를 적절히 분배한다면 평균 시간 복잡도가 O(1)을 갖게 된다.
만약 해시 함수가 simple uniform hashing임을 가정한다면, n개의 값을 m 크기 테이블로 옮기는 함수에 대해선 예상 값(길이)은 n/m이다. 이 경우 값을 찾는 경우 값이 없을 때 최악의 복잡도는 O(n/m)이다. 평균복잡도가 O(1)인 것은, 쉽게 생각하면 n/m 길이에 대해 각 원소는 1/(n/m)의 일 가능성을 가지므로, n/m * m/n 이라 생각하면, 평균 복잡도가 O(1) 이라 러프하게 생각할 수 있다. (정확한 방식인지 확실하지 않다.)

open addressing

오픈 어드레싱 방식은 충돌시 테이블 내의 다른 슬롯으로 이동하여 채워 넣는 방법이다. linear probing은 1씩(또는, 상수) 증가하며 채워 넣는 방법이며, 충돌시 상수만큼씩 이동한다. 그렇다면 탐색과 삭제시 해당 값의 키 h(k)서 부터 1씩 이동하며 값이 있는지 확인 하거나 삭제한다. 이 때 삭제시, None 대신 DELETED 어트리뷰트를 추가해서 사용한다면, 탐색시 DELETED를 만나면 그 뒤에도 probing을 하면 값이 나올 수 있겠다고 기대할 수 있다. None을 만나게 된 경우 더이상 probing을 하더라도 값이 있을 수가 없기에, 탐색을 하지 않는다.
probing의 방식에서는 Linear (1씩), Quadratic Probing(제곱), Double hasing(해시함수 두 개) 방식으로 사용된다. Linear Probing은 primary clustering으로 겹칠 수 있는 가능성이 매우 많다. 반면 Quadratic Probing인 경우 h(k, i) = h'(k) + c_1i + c_2i^2이다. 이 경우도 어떤 두 개체의 키 값이 동일 한 경우 secondary clustering이 발생할 수 있다.
Double hasing은 open addressing에서 가장 나은 선택지를 주는데 h(k,i) = (h_1(k) + i*h_2(k)) mod m 으로 표현될 수 있다. linear, quadratic probing과 다르게 해시 두개를 사용하며 두 해시를 조합하는데 다양한 방법을 사용할 수 있다.