해시 테이블(Hash Table)은 키(key)와 값(value)을 저장하고, 키를 기반으로 빠르게 값을 찾을 수 있는 데이터 구조입니다. 일반적으로 배열을 사용하여 구현되며, 키에 해당하는 인덱스를 계산하여 해당하는 배열 요소에 직접 접근하여 값을 검색합니다.

해시 함수(Hash Function)

해시 함수는 키를 받아들여 해시 테이블 배열의 유효한 인덱스로 변환하는 함수입니다. 이 함수는 각 키를 서로 다른 고유한 인덱스로 매핑하여 충돌을 방지합니다. 충돌이 발생하면 일반적으로 연결 리스트(Linked List) 또는 개방 주소법(Open Addressing) 등의 기법을 사용하여 처리합니다.

unsigned int hashFunction(string key, int tableSize) {
    unsigned int hashValue = 0;
    for(char ch : key) {
        hashValue = (hashValue * 31) + ch; // 간단한 해시 함수 예시
    }
    return hashValue % tableSize;
}

해시 충돌(Hash Collision) 처리

해시 충돌은 서로 다른 키가 같은 해시 값으로 매핑되는 상황을 말합니다. 이를 방지하기 위해 좋은 해시 함수를 선택하고 충돌을 효율적으로 처리하는 방법이 중요합니다.

체이닝(Chaining)

체이닝은 각 해시 버킷이 연결 리스트로 구성되어 있는 방법으로, 충돌이 발생한 경우 해당 버킷의 연결 리스트에 값을 추가합니다.

개방 주소법(Open Addressing)

개방 주소법은 충돌이 발생했을 때 다른 빈 버킷을 찾는 방법으로, 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 랜덤 조사(Random Probing) 등의 방법을 사용합니다.

장점

• 해시 테이블은 원하는 요소를 빠르게 찾을 수 있습니다.
• 주어진 키에 대해 고유한 인덱스로 매핑하기 때문에 고속 검색이 가능합니다.

한계

• 충돌을 처리하는 방법에 따른 성능 차이가 있을 수 있습니다.
• 해시 함수의 성능에 따라 검색 속도가 달라질 수 있습니다.

해시 테이블은 많은 애플리케이션에서 효과적으로 사용되며, 충돌 처리와 해시 함수의 선택에 따라 성능이 달라질 수 있습니다.

참고문헌: GeeksforGeeks - Hash Table