[자료구조] 해시 테이블(Hash Table)

[ 해시 테이블 (Hash Table) ]

 키(key) - 값(value) 쌍을 저장하는 배열 기반의 구조.

특정 키를 사용해 값을 검색하고 삭입하거나, 삭제할 수 있다.

 

Hash Table

해시 함수(hash function): 주어진 키를 해시 코드(hash cade)로 변환하는 함수

배열(Array): 해시 테이블의 버킷을 저장. 각 배열 요소는 버킷을 나타내며, 여러 개의 키-값 쌍(Key-Value Pair)을 저장할 수 있다.

버킷(Bucket): 해시테이블의 각 배열 요소. 버킷은 한 개 이상의 키-값 쌍(Key-Value-Pair)을 저장할 수 있다. 데이터를 저장하거나 검색할 수 있는 인터페이스가 제공된다.

 

 해시 테이블에서 가장 중요한 점은 해시 함수(hash function)와 배열(array)을 이용한다는 점이다. 해시 함수는 키의 일부를 사용해 코드를 생성하므로, 동일한 키에 대해서는 항상 동일한 해시 코드가 반환된다. 이렇게 생성된 해시 코드를 이용해 배열의 인덱스를 계산한다.

 해시 테이블은 일반적으로 배열로 구현되며, 각 배열 요소는 버킷(bucket)이라고 한다. 해시 함수를 통해 계산된 인덱스에 해당하는 버킷에 데이터를 저장하고 검색하는 방식이다.

 

 만약 해시 함수를 사용해 계산된 인덱스에 이미 다른 데이터가 저장되어 있는 경우 충돌이 발생한다. 여기서 충돌은 서로 다른 키에 대해 같은 인덱스가 계산되는 경우를 말한다. 충돌을 해결하기 위해 일반적으로 개별 체이닝(Separate Chaining), 개방 주소법(Open Addressing)이 두 가지 기법을 사용한다.

 

[ 개별 체이닝(Separate Chaining) ]

 

Separate Chaining

 인덱스가 동일해서 충돌한다면, 이를 동일한 버킷(bucket)에 저장하는데, 이를 연결 리스트(Linked List) 형태로 저장하는 방법이다. 연결 리스트는 같은 버킷에 속한 데이터를 연결하여 저장하는 방식이다. 충돌이 발생하더라도 데이터를 삽입하고 검색할 수 있다.

 

[ 개방 주소법 (Open Addressing) ]

Open Addressing

 동일한 주소에 다른 데이터가 있을 경우 다른 빈 버킷을 찾아 데이터를 저장하는 방식이다. 

 

 

[ 특징 ]

 일반적으로 해시 테이블은 빠른 시간에(O(1)) 데이터를 검색, 삽입, 삭제할 수 있다는 장점이 있다. 하지만 충돌이 많이 발생하는 경우에는 일일이 충돌을 해결 해야 하기 때문에 성능이 저하될 수 있다..!

 

장점

데이터를 저장하고 검색하는 속도가 빠르다.

데이터의 중복을 허용한다.

데이터 정렬이 필요 없다.

 

단점

데이터의 삽입, 삭제, 검색에 시간이 소요될 수 있다.

해시 함수의 선택이 중요하다.

충돌 해결 기법에 따라 성능이 달라질 수 있다.