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

해시 테이블은 데이터를 저장하고 검색하는 데 사용되는 데이터 구조입니다. 이것은 효율적인 데이터 검색을 위해 설계되었으며, 특히 키-값 쌍을 저장하고 검색하는 데 효과적입니다. 해시 테이블의 기본 목적은 빠른 검색 속도를 제공하는 것입니다. 해시 테이블은 해시 함수를 사용하여 데이터를 저장하고 검색하는데 사용되며, 이를 통해 데이터를 고속으로 찾을 수 있습니다.

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

해시 테이블을 구현하기 위해서는 해시 함수와 배열을 사용합니다. 해시 함수는 주어진 입력 데이터(키)를 특정 위치(인덱스)로 매핑하는 역할을 합니다. 일반적으로 해시 함수는 입력 데이터의 고유한 해시 코드를 생성하며, 이 해시 코드를 배열의 인덱스로 사용하여 데이터를 저장하거나 검색합니다.

import java.util.LinkedList;

class HashTable<K, V> {
    private static final int DEFAULT_CAPACITY = 16; // 기본 배열 크기
    private LinkedList<Entry<K, V>>[] table;

    // 해시 테이블 생성자
    public HashTable() {
        table = new LinkedList[DEFAULT_CAPACITY];
    }

    // 해시 함수
    private int hash(K key) {
        return key.hashCode() % table.length;
    }

    // 데이터 삽입
    public void put(K key, V value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }

        // 이미 존재하는 키일 경우 업데이트, 아니면 새로운 엔트리 추가
        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        table[index].add(new Entry<>(key, value));
    }

    // 데이터 검색
    public V get(K key) {
        int index = hash(key);
        if (table[index] != null) {
            for (Entry<K, V> entry : table[index]) {
                if (entry.key.equals(key)) {
                    return entry.value;
                }
            }
        }
        return null; // 키를 찾지 못한 경우
    }

    // 엔트리 클래스
    private class Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

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

        // 데이터 삽입
        hashTable.put("one", 1);
        hashTable.put("two", 2);
        hashTable.put("three", 3);

        // 데이터 검색
        System.out.println("Key 'one'의 값: " + hashTable.get("one"));
        System.out.println("Key 'four'의 값: " + hashTable.get("four")); // 없는 키의 경우 null 반환
    }
}

3. 테이블의 충돌과 해결

해시 테이블에서 충돌은 서로 다른 데이터가 동일한 해시 코드로 매핑될 때 발생합니다. 충돌은 해시 테이블의 성능을 저하시킬 수 있으므로 이를 해결하는 방법이 중요합니다. 몇 가지 충돌 해결 방법은 다음과 같습니다:

1. 체이닝 (Chaining): 각 해시 버킷에 연결 리스트를 사용하여 충돌을 처리합니다. 같은 해시 코드를 가진 데이터를 연결 리스트에 추가합니다.
2. 개방 주소법 (Open Addressing): 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 선형 탐색이나 이중 해싱을 사용하여 데이터를 다른 버킷에 저장합니다.

4. 해시 테이블의 시간 복잡도

• 데이터 삽입 (insertion): 일반적으로 O(1)의 시간 복잡도를 가집니다. 그러나 충돌이 발생할 경우 최악의 경우 O(n)이 될 수 있지만, 충돌을 잘 처리한다면 일반적으로 O(1)을 유지합니다.
• 데이터 검색 (search): 일반적으로 O(1)의 시간 복잡도를 가집니다.
• 데이터 삭제 (deletion): 일반적으로 O(1)의 시간 복잡도를 가집니다.

5. 해시 테이블의 장단점

5-1) 장점

• 빠른 데이터 검색 및 삽입: 해시 테이블은 빠른 검색 속도를 제공하므로 대용량 데이터의 검색이 효율적입니다.
• 유연성: 다양한 데이터 유형에 대한 키-값 쌍을 저장할 수 있습니다.

5-2) 단점

• 충돌 처리: 충돌이 발생하면 성능이 저하될 수 있으며, 충돌을 효율적으로 처리하기 위한 추가 논리가 필요합니다.
• 메모리 사용량: 큰 해시 테이블은 많은 메모리를 사용할 수 있습니다.

6. 해시 테이블을 이용한 문제 풀기

Q1. 이 코드의 실행 결과를 작성하세요.

import java.util.HashMap;
import java.util.Map;

public class MostFrequentCharacter {
    public static char findMostFrequentCharacter(String input) {
        if (input == null || input.isEmpty()) {
            throw new IllegalArgumentException("입력 문자열이 유효하지 않습니다.");
        }

        // 문자 빈도를 저장할 해시 맵 생성
        Map<Character, Integer> charFrequency = new HashMap<>();

        // 문자열을 순회하며 문자 빈도 업데이트
        for (char c : input.toCharArray()) {
            charFrequency.put(c, charFrequency.getOrDefault(c, 0) + 1);
        }

        // 가장 빈도가 높은 문자 찾기
        char mostFrequentChar = input.charAt(0);
        int maxFrequency = 0;

        for (char c : charFrequency.keySet()) {
            int frequency = charFrequency.get(c);
            if (frequency > maxFrequency) {
                maxFrequency = frequency;
                mostFrequentChar = c;
            }
        }

        return mostFrequentChar;
    }

    public static void main(String[] args) {
        String input = "programming";
        char result = findMostFrequentCharacter(input);
        System.out.println("가장 많이 나타나는 문자: " + result);
    }
}

• Q1 :