알고리즘 이론 깨부수기 Hash Table

Hash Table

Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖습니다. 특정한 값을 search하는데 데이터 고유의 인덱스로 접근하게 되므로 평균적인 시간복잡도가 O(1)이 됩니다.

Hash Function

'특별한 알고리즘'을 hash method 또는 해시 함수(hash function)라고 하고 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 합니다.

동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재(해시(Hash)값이 충돌하는 경우)할 수 있게 되는 것인데 이를 Collision 이라고 합니다.

이를 해결해주기 위한 방법으로는

분리 연결법(Separate Chaining)

Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다.

연결 리스트를 사용하는 방식(Linked List) : 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다.

Tree 를 사용하는 방식 (Red-Black Tree) : 기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다.