Hash Table

Hash Function(해시 함수)

데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

매핑 전 기존 데이터의 값을 Key, 매핑 후 데이터 값을 Hash Value(해시 값), 매핑하는 과정을 Hashing이라고 한다.

 

Hashing(해싱)

임의의 길이의 값을 해시 함수(Hash Function)을 사용하여 고정된 크기의 값으로 변환하는 작업

 

Hash Table(해시 테이블)

Hashing을 사용하여 데이터를 저장하는 자료구조를 Hash Table이라고 하며, 이는 기존의 자료구조인 이진탐색트리나 배열에 비해서 굉장히 빠른 속도로 탐색, 삽입, 삭제가 가능하다.

즉, Hash Function을 사용하여 변환한 값(Hash Value)를 index로 사용하여 Key와 데이터(value)를 저장하는 자료구조이다.

 

Direct Address Table

가장 간단한 형태의 해시 테이블로서, Key 값을 주소로 사용하는 테이블이다.

이는 탐색, 삽입, 삭제를 O(1)에 수행할 수 있지만 최대 Key 값에 대해 알고있어야하며, 최대 Key 값이 작을 경우 비효율적이며, Key 값이 골고루 분포되어있지 않다면 메모리 낭비가 심하다는 단점이 있다.

 

Hash Table

Hash Function을 사용하여 Hash Value를 알아내고, 해당 Hash Value를 인덱스로 하여 Key 값과 데이터를 저장하는 자료구조이다.

충돌(Hash Collision)이 발생하지 않는다면, 탐색, 삽입, 삭제를 O(1)에 수행할 수 있지만, 충돌이 발생한다면 탐색, 삭제에 최악의 경우 O(K)만큼 걸리게 된다. (같은 인덱스에 모든 Key 값과 데이터가 저장된 경우)

Hash Table의 핵심은 충돌을 최대한 줄여서 연산 속도를 빠르게 하는 것에 있다. 이에 중요하게 작용되는 것이 Hash Function을 구현하는 Algorithm이다. 

Hash Algorithm이 견고하지 못하면, Hash Function을 통해 도출된 Hash Value들이 같은 경우가 빈번하게 발생되고, 이는 곧 잦은 충돌로 이어진다.

 

충돌을 완화하기 위해서는 Hash Table의 구조를 개선하는 방법(Chaining, Open Addressing)과, Hash Function을 개선하는 방법(나눗셈법(Division Method), 곱셈법(Multiplication Method))이 있다.