해시 테이블 (Hash Table)

1. 해시 테이블의 이론과 목적

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 자료 구조로, 특정 데이터를 고유한 키(key)와 연결하여 저장하는 방식을 사용합니다. 해시 테이블은 다음과 같은 목적을 가집니다:

• 데이터 검색 속도 향상: 해시 테이블은 키를 해시 함수를 통해 배열의 인덱스로 변환하므로, 원하는 데이터를 빠르게 찾을 수 있습니다.
• 데이터 저장: 데이터를 키와 함께 저장하여 나중에 검색이나 업데이트를 할 때 사용할 수 있습니다.
• 중복 제거: 해시 테이블은 중복된 키를 허용하지 않으므로, 중복 데이터를 방지할 수 있습니다.

2. 해시 테이블 코드로 구현하기

해시 테이블을 구현하기 위해서는 해시 함수와 배열을 사용합니다. 간단한 파이썬 예제로 해시 테이블을 구현할 수 있습니다:

import java.util.Hashtable;

public class Main {
    public static void main(String[] args) {
        // Hashtable을 생성합니다.
        Hashtable<String, Integer> ht = new Hashtable<>();

        // 키와 값을 추가합니다.
        ht.put("key1", 42);
        ht.put("key2", 15);

        // 특정 키를 사용하여 값을 검색합니다.
        Integer result1 = ht.get("key1");
        Integer result2 = ht.get("key2");

        System.out.println("key1: " + result1);
        System.out.println("key2: " + result2);

        // 특정 키와 연관된 값을 제거합니다.
        ht.remove("key1");

        // 삭제 후 다시 검색해보면 null이 반환됩니다.
        Integer result3 = ht.get("key1");
        System.out.println("key1 after removal: " + result3);
    }
}

3. 해시 테이블의 충돌과 해결

해시 테이블에서 충돌은 두 개 이상의 키가 동일한 해시값을 가질 때 발생합니다. 충돌을 해결하지 않으면 데이터의 무결성이 깨질 수 있습니다.

4. 충돌 해결

4.1. 해시 테이블의 구조 개선

여러 가지 충돌 해결 기법이 있으며, 일반적으로 다음과 같은 방법을 사용합니다:

Separate Chaining

해시 테이블의 각 슬롯(해시값에 해당하는 배열 요소)에 연결 리스트를 사용하여 충돌된 데이터를 저장합니다.

Open Addressing

충돌이 발생한 슬롯을 다른 슬롯으로 이동하거나 다른 빈 슬롯을 찾아 데이터를 저장합니다. 선형 탐색, 이차 탐색, 이중 해싱 등이 사용됩니다.

5. 장단점

5.1. 장점

• 빠른 데이터 검색: 해시 함수를 통해 빠르게 원하는 데이터를 찾을 수 있습니다.
• 중복 방지: 중복된 키를 허용하지 않으므로 중복 데이터를 방지할 수 있습니다.

5.2. 단점

• 해시 충돌: 충돌이 발생하면 성능 저하가 발생하고 충돌 해결 방법이 필요합니다.
• 메모리 소모: 충분한 메모리 공간을 확보해야 하므로 메모리 소모가 큰 경우가 있습니다.

6. 활용 문제 풀어보기

import java.util.Hashtable;

public class Main {
    public static void main(String[] args) {
        Hashtable<String, Integer> ht = new Hashtable<>();

        ht.put("data1", 32);
        ht.put("data2", 11);
        ht.put("data3", 12);
        ht.put("data4", 41);
        
        Integer result = ht.get("data2");
        // 1. 다음 출력될 것은?
        System.out.println(result);

        ht.remove("data3");
        result = ht.get("data3");
        // 2. 다음 출력될 것은?
        System.out.println(result);

        // 3. Hashtable에 이미 존재하는 키를 사용하여 값을 추가하면 어떤 결과가 나오는지 설명하세요.

        // 4. Hashtable의 크기를 확인하는 방법를 작성

        // 5. Hashtable을 비우는 코드를 작성
    }
}