Hash Table (해시 테이블)의 필요성과 문제점, 해결 방법
Direct Address Table 의 한계
direct address table은 키(key)와 값(value)의 쌍(pair)을 저장하는 자료구조로, 키를 인덱스(index)로 사용하여 값을 저장하고 검색할 수 있다.
이 때, 인덱스의 크기가 충분히 크면(예를 들어, 0부터 999까지의 인덱스가 있을 때, 1000개), O(1)의 검색 시간을 제공한다.
그러나 인덱스의 크기가 매우 작거나 값이 희소하게 분포할 경우, 메모리 공간의 낭비가 발생하게 된다.
이러한 direct address table의 한계를 극복하기 위해, 해싱 기법을 사용하는 해시 테이블(Hash Table)이 개발되었다.
해시 테이블은 키를 해시 함수(hash function)로 변환하여 인덱스를 생성하므로, 인덱스의 크기와 값의 분포에 구애받지 않는다.
또한, 해시 함수를 이용하여 데이터의 위치를 찾으므로, O(1)의 검색 시간을 제공한다.
하지만 해시 테이블에도 몇가지 문제점이 존재한다.
Hash Table 의 문제점
1. 충돌 (Collision)
해시 함수에 의해 생성된 인덱스가 다른 데이터와 이미 할당된 경우 충돌이 발생한다.
충돌이 발생하면, 데이터를 추가적으로 처리하여 충돌을 해결해야 한다.
2. 해시 함수 성능
해시 함수의 성능이 좋지 않으면 데이터 검색 시간이 길어지게 된다.
해시 함수는 인덱스를 생성하는데 사용되므로 충돌을 최소화하면서 빠른 속도를 제공하는 함수를 선택해야 한다.
이러한 문제점을 극복하기 위해 충돌 해결(Collision Resolution)방법과 좋은 Hash Function을 선택하는것이 중요하다.
이러한 문제점들을 극복하기 위해, 충돌 해결(Collision Resolution) 방법과 좋은 해시 함수(Hash Function)를 선택하는 것이 중요하다.
충돌 해결 방법으로는 Open Addressing, Chaining 등이 있으며, 좋은 해시 함수 선택을 위해서는 해시 함수의 충돌 가능성과 보안성을 고려해야 한다.
충돌 해결 방법
충돌은 데이터를 검색하는 데 시간이 걸리며, 해시 함수 성능을 저하시킨다.
따라서 충돌을 최소화하는 해시 함수를 선택해야 하며, 충돌이 발생하였을 때는 이를 해결하는 방법을 선택해야 한다.
1. Open Addressing
Open Addressing은 충돌된 데이터를 다른 해시 테이블 위치에 저장하는 기법이다.
충돌이 발생하면, 해당 위치 이후의 다른 위치를 검색하여 데이터를 저장한다.
이러한 방법은 충돌 해결 방법 중에서도 가장 간단한 방법 중 하나이다.
하지만 충돌이 발생할 경우 해시 함수의 성능이 저하되므로, 충돌이 적은 경우에만 사용된다.
2. Chaining
Chaining은 충돌된 데이터를 같은 위치의 연결 리스트(Linked List)에 저장하는 기법이다.
충돌이 발생하고 해당 위치에 이미 데이터가 저장되어 있으면 연결 리스트에 데이터를 추가한다.
이러한 방법은 해시 함수의 성능에 영향을 미치지 않으며, 충돌이 많은 경우에도 사용할 수 있다.
좋은 해시 함수 선택 방법
- 좋은 해시 함수를 선택하기 위해서는 해시 함수의 충돌 가능성과 보안성을 고려해야 한다.
- 충돌 가능성이 높으면 검색 시간이 길어지므로, 충돌 가능성이 적은 함수를 선택해야 한다.
- 보안성이 중요한 경우에는 보안 해시 함수 또는 암호학적 해시 함수를 선택해야 한다.