Hashtable

해시 함수는 해시 테이블의 핵심 구성 요소로, 임의의 길이를 가진 입력 데이터(키)를 고정된 길이의 값(해시 값 또는 해시 코드)으로 변환하는 함수이다. 이 변환 과정을 해싱이라고 한다. 이상적인 해시 함수는 서로 다른 키에 대해 가능한 한 서로 다른 해시 값을 생성하여 충돌을 최소화해야 하며, 동일한 키에 대해서는 항상 동일한 해시 값을 반환하는 결정론적 특성을 가져야 한다.

해시 함수의 성능은 해시 테이블의 효율성을 직접적으로 좌우한다. 좋은 해시 함수는 키의 공간을 버킷 배열의 인덱스 공간에 균일하게 분포시켜야 한다. 이를 통해 데이터가 특정 버킷에 집중되는 현상인 클러스터링을 방지하고, 평균적인 연산 시간을 O(1)에 가깝게 유지할 수 있다. 일반적으로 사용되는 해시 함수 기법에는 나눗셈법, 곱셈법, 유니버설 해싱 등이 있다.

해시 함수 설계 시 고려해야 할 점은 계산 속도와 충돌 빈도 사이의 균형이다. 매우 복잡한 함수는 충돌을 줄일 수 있지만 계산에 시간이 많이 소요될 수 있고, 너무 단순한 함수는 빠르게 계산되지만 충돌이 빈번히 발생할 수 있다. 또한, 특정 애플리케이션의 키 분포 특성을 고려한 함수 선택이 중요하다. 대부분의 현대 프로그래밍 언어와 라이브러리는 이러한 요소들을 고려하여 표준 객체나 자료형에 대해 효율적인 기본 해시 함수를 제공한다.

해시 테이블에서 서로 다른 키가 동일한 해시 버킷 인덱스로 매핑되는 현상을 충돌이라고 한다. 충돌을 해결하는 방법은 크게 두 가지로 나눌 수 있다.

첫 번째 방법은 체이닝이다. 이 방법은 각 버킷을 연결 리스트나 트리와 같은 자료 구조로 관리하여, 같은 인덱스에 여러 개의 키-값 쌍을 저장한다. 충돌이 발생하면 해당 버킷의 리스트에 새로운 항목을 추가한다. 체이닝은 구현이 비교적 간단하고 버킷의 개수보다 많은 데이터를 저장할 수 있다는 장점이 있다. 그러나 연결 리스트를 따라 순차 탐색을 해야 하므로 버킷 내 데이터가 많아질수록 성능이 저하될 수 있다.

두 번째 방법은 개방 주소법이다. 이 방법은 충돌이 발생하면 미리 정해진 규칙에 따라 다른 빈 버킷을 찾아 데이터를 저장한다. 대표적인 탐사 방법으로는 선형 탐사, 이차 탐사, 이중 해싱 등이 있다. 개방 주소법은 추가적인 포인터 저장 공간이 필요 없어 메모리 효율이 좋은 편이다. 하지만 클러스터링 현상이 발생할 수 있으며, 삭제 연산이 복잡해질 수 있다는 단점이 있다.

해시 테이블에 데이터를 저장하는 삽입 연산은 일반적으로 put 또는 set이라는 이름의 메서드로 제공된다. 이 연산의 핵심은 주어진 키를 해시 함수에 입력하여 해시값을 계산하고, 이 값을 배열의 인덱스로 사용하여 해당 키와 연결된 값을 저장하는 것이다.

삽입 과정에서 가장 중요한 고려 사항은 해시 충돌의 처리이다. 계산된 인덱스 위치에 이미 다른 데이터가 존재하는 경우, 즉 충돌이 발생하면 사전에 정의된 충돌 해결 방법을 적용해야 한다. 가장 일반적인 방법인 체이닝에서는 해당 인덱스가 가리키는 연결 리스트나 이진 트리에 새로운 키-값 쌍을 추가한다. 반면 개방 주소법을 사용하는 구현에서는 선형 탐사나 이중 해싱과 같은 방법으로 빈 슬롯을 찾아 데이터를 저장한다.

삽입 연산의 효율성은 해시 함수의 품질과 부하율에 크게 의존한다. 부하율, 즉 저장된 항목 수와 버킷 수의 비율이 일정 임계값을 초과하면 성능이 저하될 수 있다. 많은 해시 맵 구현체는 이 경우 재해싱 과정을 통해 내부 배열의 크기를 동적으로 늘리고 모든 기존 항목을 새로운 배열에 재배치하여 평균적인 시간 복잡도를 O(1)에 가깝게 유지하려고 한다.

해시 테이블에서 검색 연산은 키를 사용하여 저장된 값을 찾아내는 과정이다. 사용자는 찾고자 하는 데이터의 키를 제공하면, 해시 테이블은 내부적으로 해시 함수를 통해 해당 키를 배열의 인덱스로 변환한다. 이 인덱스 위치에 바로 접근하여 값을 확인할 수 있다.

검색의 효율성은 해시 함수의 품질과 충돌 해결 방법에 크게 의존한다. 이상적인 경우, 즉 충돌이 발생하지 않으면 계산된 인덱스 위치에 한 번의 접근으로 원하는 값을 즉시 얻을 수 있다. 이로 인해 해시 테이블의 검색 연산은 평균적으로 상수 시간인 O(1)의 시간 복잡도를 가진다.

그러나 서로 다른 키가 동일한 인덱스로 해싱되는 해시 충돌이 발생하면 상황이 복잡해진다. 체이닝 방식을 사용하는 경우, 해당 인덱스에 연결된 연결 리스트나 트리를 순차적으로 탐색해야 한다. 개방 주소법을 사용하는 경우, 정해진 탐사 순서에 따라 빈 슬롯을 찾을 때까지 다음 위치를 확인하며 탐색을 계속한다. 최악의 경우, 대부분의 키가 하나의 인덱스로 몰리거나 테이블이 가득 차면 모든 항목을 확인해야 할 수 있으며, 이때 시간 복잡도는 O(n)이 된다.

따라서 해시 테이블을 통한 검색은 일반적으로 매우 빠르지만, 그 성능을 보장하기 위해서는 균일한 키 분포를 생성하는 해시 함수와 적절한 부하율 관리가 필수적이다. 많은 프로그래밍 언어의 표준 라이브러리에 구현된 해시 맵이나 딕셔너리는 이러한 검색 기능을 제공하는 대표적인 사례이다.

해시테이블에서 특정 키에 매핑된 항목을 제거하는 연산이다. 삭제 연산은 일반적으로 검색 연산을 선행한다. 먼저 주어진 키를 해시 함수에 입력하여 버킷의 인덱스를 계산하고, 해당 버킷 내에서 키를 비교하여 삭제할 항목을 찾는다.

충돌 해결 방법에 따라 삭제 처리 방식이 달라진다. 분리 연결법을 사용하는 경우, 연결 리스트나 트리에서 해당 노드를 제거하면 된다. 개방 주소법을 사용하는 경우, 특히 선형 탐사나 이차 탐사 방식에서는 단순히 항목을 비우는 것만으로는 문제가 발생할 수 있다. 빈 슬롯은 탐사 종료 조건으로 작용하기 때문에, 이후 다른 키를 검색하거나 삭제할 때 탐사가 조기에 중단되어 데이터를 찾지 못하는 오류가 발생할 수 있다.

이를 해결하기 위해 삭제된 슬롯에 특별한 표시(예: "삭제됨" 플래그)를 두어, 검색 시에는 탐사를 계속 진행하되, 삽입 시에는 새로운 항목을 저장할 수 있는 위치로 재활용하는 방법이 사용된다. 이는 클러스터링 현상을 완화하고 테이블의 성능을 유지하는 데 도움이 된다. 삭제 연산의 시간 복잡도는 평균적으로 상수 시간 O(1)에 수행되지만, 모든 항목이 하나의 버킷에 모이는 최악의 경우 O(n)이 될 수 있다.

해시 테이블은 많은 프로그래밍 언어의 표준 라이브러리나 핵심 라이브러리에 포함되어 있으며, 각 언어마다 고유한 구현체와 이름을 가지고 있다. 대표적으로 자바에서는 HashMap과 Hashtable 클래스가 있으며, 파이썬은 내장 자료형인 dict(딕셔너리)가 해시 테이블로 구현되어 있다. C++의 표준 템플릿 라이브러리(STL)에는 unordered_map이, C#에는 Dictionary<TKey, TValue>가 해시 테이블 기반의 연관 컨테이너로 제공된다.

자바스크립트의 객체(Object)와 Map도 키-값 쌍을 저장하는데, 특히 ES6에서 도입된 Map 객체는 키로 객체를 포함한 모든 값을 사용할 수 있어 해시 테이블의 특성을 가진다. 루비의 Hash, PHP의 연관 배열, 스위프트의 Dictionary 역시 해시 테이블을 기반으로 한다.

이러한 구현체들은 언어의 철학과 필요에 따라 세부 동작이 다르다. 예를 들어, 자바의 Hashtable은 스레드 안전하지만 HashMap은 그렇지 않으며, 파이썬의 딕셔너리는 매우 최적화되어 있어 높은 성능을 제공한다. 개발자는 각 언어의 공식 문서를 참조하여 정확한 사용법, 시간 복잡도, 메모리 사용량 등의 특성을 확인하는 것이 중요하다.