HashTable, Hash 충돌

해시테이블에 대해서 공부했었지만, 어떤 유튜브를 보고 더 자세히 알게 되어서 쫌 더 자세히 작성하려고 한다.

📌 Hash?

"임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환한 결과물"
이때 생성된 고정된 크기의 값을 해시값(hash value) 또는 해시코드(hash code)라고 한다.

📌 HashTable?

배열과 해시함수를 사용해서 Map을 구현한 자료구조이다.
이는 상수시간(O(1))으로 접근하기 때문에 접근하기에 매우 빠르다.

📌 Hash Function

임의의 크기를 가지는 type의 데이터를 고정된 크기의 type으로 변환하는 함수이다.
예를 들면, "정주현"이라는 값을 해시함수에 넣는다면, 102와 같은 고정된 크기의 type의 값으로 변환해주는 것을 의미한다.

📌 HashTable의 동작방식 및 해시충돌

public static void main(String[] args) {
        Map<BadHash, String> map = new HashMap<>();

        BadHash key1 = new BadHash("010-1234-1234");
        BadHash key2 = new BadHash("010-1211-1211"); // 해시값은 같지만 equals도 다르게 처리

        map.put(key1, "정홍익");
        map.get(key2);

        System.out.println("key1.hashCode(): " + key1.hashCode()); //42
        System.out.println("key2.hashCode(): " + key2.hashCode()); //42
    }

    // 해시 충돌만 유도하고 equals는 재정의하지 않음 (Object 기본값 사용)
    static class BadHash {
        String phone;

        public BadHash(String phone) {
            this.phone = phone;
        }

        @Override
        public int hashCode() {
            return 42; // 고정된 해시값으로 충돌 유도
        }

        @Override
        public String toString() {
            return phone;
        }
    }
}

코드를 통해서 설명하자면,
객체 두 개 생성했으며 서로 다른 휴대폰 번호를 가진 두 객체(key1, key2)를 만들었고,
hashCode()는 항상 같은 값(42)을 반환하도록 구현했다.

• map.put(key1, "정홍익") : key1값을 통해서 hashCode를 얻어오면 hashCode%(버킷의 Capacity(용량))으로 나누어서 얻은 주소값으로 해당 버킷에 (key1, "정홍익") 쌍을 저장한다.
• map.get(key2) : key2.hashCode()도 42이므로, 같은 버킷 위치로 접근한다. 버킷 안의 엔트리 키인 key1과 key2를 equals()로 비교하는데, 기본 Object의 equals()는 참조(메모리 주소) 비교를 하기 때문에, 서로 다른 객체는 false를 반환한다. 따라서 key2로는 값을 찾지 못해 null을 반환한다.

이렇듯, 해시충돌이 발생하는데 이를 해결하는 방법에 대해서 설명하려고 한다.

📌 해시충돌

해시충돌이 발생하는 조건은 2가지가 있다.

• key는 다른데 Hash값이 같을 경우
• key,Hash값도 다른데, Hash %(map의Capacity)이 같을경우

📌 Separate Chaining

이는 해시충돌이 발생했을 경우, 데이터를 삽입할때 링크드리스트 형태로 데이터를 삽입한다.

버킷의 주소값(해시값 기반 인덱스)이 같은 경우, 해당 버킷에는 여러 개의 엔트리(Entry)를 연결 리스트(LinkedList) 형태로 저장한다. 이를 통해 서로 다른 키지만 해시값이 같은 경우에도 문제없이 데이터를 관리할 수 있다.

put() 동작은 다음과 같다
키 객체의 hashCode()를 기반으로 버킷 인덱스를 계산한다.
해당 인덱스에 이미 데이터가 존재할 경우: 기존 키들과 equals()를 통해 비교한다.
동일한 키가 존재하면 해당 엔트리의 value를 덮어씌우고,
동일한 키가 없으면, 연결 리스트의 끝에 새로운 (key, value) 엔트리를 추가한다.

이러한 방식으로 HashMap은 해시 충돌이 발생하더라도 안정적으로 여러 데이터를 저장하고 관리할 수 있다.

📌 Open Addressing

Open Addressing은 해시 충돌이 발생했을 때, 새로운 키-값을 다른 빈 버킷에 저장하는 방식.
즉, 모든 데이터가 해시 테이블 안에 직접 저장되며, LinkedList를 사용하지 않는다.

충돌이 발생했을 때 다음 버킷을 찾는 방식에는 여러 가지가 있고, 대표적으로 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다. 예를 들어 선형 탐사는 충돌 시 바로 다음 칸으로 이동하면서 빈 공간을 찾고, 이중 해싱은 두 번째 해시 함수를 이용해 이동 거리를 계산한다.

Open Addressing의 장점은 포인터나 객체를 추가로 생성하지 않기 때문에 메모리 효율이 높고, 캐시 적중률이 높아져 성능이 향상될 수 있다는 점이다. 하지만 충돌이 많이 발생하면 빈 자리를 찾는 탐색 시간이 길어질 수 있고, 삭제된 요소를 처리하기 위한 별도의 로직이 필요하다는 단점이 있다.

Java의 HashMap은 기본적으로 체이닝(Chaining) 방식을 사용하지만, C++의 unordered_map이나 일부 고성능 라이브러리에서는 Open Addressing 방식을 사용하기도 한다.