Java에서 Hashtable은 키(key)와 값(value)을 쌍으로 저장하는 자료구조이다.
각 키는 해시 함수(hash function)를 통해 고유한 해시 값(hash value)으로 변환되고,
이 해시 값은 해당 키-값 쌍이 저장될 배열 인덱스를 결정한다.
이러한 방식으로 Hashtable은 상수 시간(constant time)에 키-값 쌍을 검색할 수 있다.

Hashtable은 내부적으로 배열을 사용하여 키-값 쌍을 저장한다.
각 키에 대한 해시 값을 계산하고, 해당 값에 매핑된 배열 인덱스에 값을 저장한다.
배열의 크기는 일반적으로 저장할 수 있는 최대 요소 수에 따라 결정된다.
Hashtable의 크기가 배열 크기에 도달하면 자동으로 더 큰 배열을 만들고,
모든 요소를 새 배열에 다시 해싱한다.


Hashtable의 검색, 삽입, 삭제는 모두 상수 시간(constant time)에 수행된다.
그러나 배열 크기가 매우 클 경우 해시 충돌(hash collision)이 발생할 수 있다.
해시 충돌은 서로 다른 키가 동일한 해시 값에 매핑되는 경우이다.
해시 충돌이 많이 발생하면 검색, 삽입, 삭제의 성능이 저하될 수 있다.

Hashtable에서 해시 충돌을 해결하는 방법에는 크게 2가지가 있다.

1. 개방 주소법 (Open Addressing)

해시 충돌이 발생하면, 다른 빈 버킷을 찾아서 데이터를 저장하는 방식이다.
선형 탐사(Linear Probing), 이차원 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등의 방법이 있다.

1-1 선형 탐사법(Linear Probing)

충돌이 발생하면, 다음 빈 버킷을 찾아서 데이터를 저장하는 방식이다.
즉, 해시 값이 h인 버킷에 이미 값이 저장되어 있으면, h+1, h+2, h+3, ... 순서대로 다음 빈 버킷을 찾아서 데이터를 저장한다. 이 방식은 저장 공간을 최대한 활용할 수 있으며, 메모리 효율이 높다.
하지만 해시 충돌이 많이 발생하면, 탐색 시간이 길어질 수 있다.

1-2 제곱 탐사법(Quadratic Probing)

충돌이 발생하면, 제곱 수열을 사용하여 다음 빈 버킷을 찾아서 데이터를 저장하는 방식이다.
즉, 해시 값이 h인 버킷에 이미 값이 저장되어 있으면, h+1^2, h-1^2, h+2^2, h-2^2, ... 순서대로 다음 빈 버킷을 찾아서 데이터를 저장한다. 이 방식은 충돌이 발생하면 다음 빈 버킷을 더 넓은 범위에서 찾기 때문에, 선형 탐사보다 충돌이 적게 발생한다.

1-3 이중 해싱(Double Hashing)

충돌이 발생하면, 다른 해시 함수를 사용하여 다음 빈 버킷을 찾아서 데이터를 저장하는 방식입니다. 즉, 해시 값이 h인 버킷에 이미 값이 저장되어 있으면, h+1 x hash2(key), h+2 x hash2(key), h+3 x hash2(key), ... 순서대로 다음 빈 버킷을 찾아서 데이터를 저장합니다. 이 방식은 다른 해시 함수를 사용하기 때문에, 해시 충돌이 많이 발생할 때에도 빈 버킷을 찾을 확률이 높아지기 때문에, 선형 탐사나 이차원 탐사보다 더 좋은 성능을 보입니다.


2. 분리 연결법 (Separate Chaining)

해시 충돌이 발생하면, 같은 버킷에 연결 리스트(Linked List)를 사용하여 데이터를 저장하는 방식이다.
같은 버킷에 해시 충돌이 발생하면, 같은 해시 값에 매핑된 다른 키-값 쌍을 저장하기 위해 해당 배열 인덱스에 연결 리스트(linked list)를 생성한다.
이렇게 연결 리스트를 사용하여 해시충돌을 처리하는 방식을 분리연결법(separate chaining)이라고 한다.

분리 연결법은 각 배열 요소에 하나 이상의 키-값 쌍을 저장할 수 있으므로, 배열 크기가 작더라도 충분히 많은 요소를 저장할 수 있다. 그러나 분리 연결법을 사용하면 해시 충돌이 발생할 때마다 연결 리스트를 탐색해야 하므로, 검색, 삽입, 삭제의 성능이 악화될 수 있다. 체이닝은 간단하고 유연한 방식이지만, 각 연결 리스트를 위한 메모리 공간이 추가로 필요하며, 포인터를 사용하여 연결 리스트를 탐색해야 하므로 일반적으로 개방 주소법보다 느릴 수 있다.


개방 주소법 방식은 분리 연결법에 비해 메모리를 적게 사용하고, 연결 리스트를 탐색할 필요가 없으므로 검색, 삽입, 삭제의 성능이 더욱 빠르다. 그러나 개방 주소법 방식도 일정한 배열 요소 간격으로 빈 요소를 찾기 때문에, 빈 요소를 찾지 못하고 무한루프에 빠질 가능성이 있다.

Java에서는 Hashtable과 함께 분리 연결법 방식을 사용합니다.
분리 연결법은 해시 충돌이 발생해도 성능 저하를 크게 경험하지 않기 때문에, 멀티스레드 환경에서 안전하게 사용할 수 있다.
그러나 Hashtable이 다수의 스레드에서 동시에 사용될 때, 연결 리스트에 대한 동기화가 필요해진다. 따라서 Hashtable은 멀티스레드 환경에서 안전하게 사용할 수 있지만, ConcurrentHashMap과 같은 자료구조가 더 나은 성능을 제공한다.


👌HashTable과 HashMap은 모두 해시테이블(Hash Table)을 사용하여 구현된 자료구조이다.
하지만, 둘 사이에는 몇 가지 차이점이 존재한다.

  • 동기화(Synchronization)
    HashTable은 멀티스레드 환경에서 안전하게 사용할 수 있도록 동기화 처리가 되어 있다. 하지만, 이로 인해 멀티스레드 환경이 아닌 경우에는 오버헤드가 발생하여 성능이 떨어질 수 있다.
    HashMap은 동기화 처리가 되어 있지 않다. 따라서, 멀티스레드 환경에서 안전하게 사용하기 위해서는 ConcurrentHashMap을 사용하거나, HashMap을 동기화 처리하여 사용해야 한다.

  • Null 허용 여부
    HashTable은 키(key)와 값(value)에 null 값을 허용하지 않는다. null 값을 허용하지 않는 이유는 해시테이블에서 null 키를 사용할 수 없기 때문이다. HashMap은 키와 값에 null 값을 허용한다.

  • 속도
    HashMap은 동기화 처리가 되어 있지 않으므로, 일반적으로 HashTable보다 속도가 빠르다.
    하지만, 멀티스레드 환경에서는 ConcurrentHashMap을 사용하는 것이 더 빠르다.
    따라서, 멀티스레드 환경이 아닌 경우에는 HashMap을 사용하는 것이 좋다. 하지만, 멀티스레드 환경에서는 ConcurrentHashMap을 사용하는 것이 안전하고 성능적으로 유리하다. 만약, 더 안전한 멀티스레드 환경에서 HashMap을 사용하고 싶다면, Collections.synchronizedMap() 메서드를 사용하여 HashMap을 동기화 처리하여 사용할 수 있다.


🌏 Chat-GPT 예제 소스코드

해시 충돌 해법별 소스코드

1. 개방 주소법

1-1 개방 주소법 (선형 탐사법)

public class LinearProbingHashTable {
    private static final int TABLE_SIZE = 10;
    private static final int EMPTY_SLOT = -1;
    private int[] table;

    public LinearProbingHashTable() {
        table = new int[TABLE_SIZE];
        Arrays.fill(table, EMPTY_SLOT);
    }

    // 해시 함수
    private int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

    // 데이터 추가
    public void put(int key, int value) {
        int hashValue = hashFunction(key);

        // 비어있는 슬롯을 찾을 때까지 다음 슬롯으로 이동
        while (table[hashValue] != EMPTY_SLOT) {
            hashValue = (hashValue + 1) % TABLE_SIZE;
        }

        // 데이터 추가
        table[hashValue] = value;
    }

    // 데이터 검색
    public int get(int key) {
        int hashValue = hashFunction(key);

        // 키에 해당하는 데이터를 찾을 때까지 다음 슬롯으로 이동
        while (table[hashValue] != key) {
            hashValue = (hashValue + 1) % TABLE_SIZE;

            // 모든 슬롯을 검색한 경우 데이터가 없다는 것을 의미
            if (table[hashValue] == EMPTY_SLOT) {
                return EMPTY_SLOT;
            }
        }

        return table[hashValue];
    }
}

위 코드에서는 먼저, 해시 함수를 이용하여 버킷의 인덱스를 계산한다. 데이터를 추가할 때는 해당 버킷이 비어있는지 확인하고, 비어있는 경우 해당 버킷에 데이터를 저장한다. 만약 버킷이 비어있지 않다면 다음 버킷으로 이동하여 비어있는 버킷을 찾아 데이터를 저장한다.

데이터를 검색할 때는 먼저, 키에 해당하는 버킷의 인덱스를 계산한다. 해당 버킷에 저장된 데이터가 검색하려는 데이터인지 확인하고, 만약 검색하려는 데이터가 아니라면 다음 버킷으로 이동하여 검색을 진행한다. 만약 모든 버킷을 검색해도 검색하려는 데이터를 찾을 수 없으면, 데이터가 존재하지 않는 것으로 간주한다.

위 코드에서는 빈 슬롯을 찾을 때까지 다음 슬롯으로 이동하며, 이때 슬롯의 인덱스가 배열의 크기를 벗어날 수 있다. 따라서 슬롯의 인덱스를 배열의 크기로 나눈 나머지 값을 사용하여 인덱스를 조정한다. 이렇게 하면 인덱스가 배열의 크기를 벗어나지 않고, 배열의 끝에서 다시 배열의 처음으로 돌아갈 수 있다.

선형 탐사법은 구현하기 쉽고, 메모리 사용량이 적어서 일반적으로 많이 사용된다. 하지만, 클러스터(Cluster)가 형성되는 경우 해시 충돌이 더 자주 발생하여 성능이 저하될 수 있기 때문에, 제곱 탐사법(Quadratic Probing)이나 이중 해싱(Double Hashing)과 같은 다른 해시 충돌 해결법을 사용할 수 있다.

1-2 개방 주소법 (제곱 탐사법)

제곱 탐사법은 해시 충돌이 발생한 경우, 일정한 간격으로 버킷을 건너뛰며 비어있는 버킷을 찾아 데이터를 저장한다. 이때 간격을 계산하는 방법에 따라 다양한 제곱 탐사법이 존재한다.

public class QuadraticProbingHashTable {
    private static final int TABLE_SIZE = 10;
    private static final int EMPTY_SLOT = -1;
    private int[] table;

    public QuadraticProbingHashTable() {
        table = new int[TABLE_SIZE];
        Arrays.fill(table, EMPTY_SLOT);
    }

    // 해시 함수
    private int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

    // 제곱 탐사법 함수
    private int quadraticProbing(int hashValue, int i) {
        return (hashValue + i * i) % TABLE_SIZE;
    }

    // 데이터 추가
    public void put(int key, int value) {
        int hashValue = hashFunction(key);
        int i = 0;

        // 비어있는 슬롯을 찾을 때까지 제곱 탐사법 수행
        while (table[hashValue] != EMPTY_SLOT) {
            hashValue = quadraticProbing(hashValue, ++i);
        }

        // 데이터 추가
        table[hashValue] = value;
    }

    // 데이터 검색
    public int get(int key) {
        int hashValue = hashFunction(key);
        int i = 0;

        // 키에 해당하는 데이터를 찾을 때까지 제곱 탐사법 수행
        while (table[hashValue] != key) {
            hashValue = quadraticProbing(hashValue, ++i);

            // 모든 슬롯을 검색한 경우 데이터가 없다는 것을 의미
            if (table[hashValue] == EMPTY_SLOT || i >= TABLE_SIZE) {
                return EMPTY_SLOT;
            }
        }

        return table[hashValue];
    }
}

위 코드에서는 먼저, 해시 함수를 이용하여 버킷의 인덱스를 계산한다. 데이터를 추가할 때는 해당 버킷이 비어있는지 확인하고, 비어있는 경우 해당 버킷에 데이터를 저장한다. 만약 버킷이 비어있지 않다면 일정한 간격으로 다음 버킷으로 이동하여 비어있는 버킷을 찾아 데이터를 저장한다.

데이터를 검색할 때는 먼저, 키에 해당하는 버킷의 인덱스를 계산한다. 해당 버킷에 저장된 데이터가 검색하려는 데이터인지 확인한다. 만약 검색하려는 데이터가 아니라면 일정한 간격으로 다음 버킷으로 이동하여 검색을 계속한다. 이때 간격을 계산하는 방법은 제곱 탐사법 함수를 이용하여 구한다. 제곱 탐사법 함수에서 i는 반복 횟수를 나타내며, 제곱 값을 이용하여 간격을 구한다.

위 코드에서는 제곱 탐사법 함수를 이용하여 간격을 구했다. 제곱 탐사법은 일반적으로 클러스터(Cluster)가 형성되는 경향이 있기 때문에 해시 충돌을 해결하기 위한 다른 방법과 함께 사용된다.

1-3 개방 주소법 (이중 해싱)

이중 해싱은 해시 충돌이 발생한 경우, 해시 함수의 출력값에 일정한 값을 더하여 다음 버킷을 찾아 데이터를 저장한다. 이때 더해지는 값은 해시 충돌이 발생한 버킷과의 거리에 따라 달라진다. 이렇게 함으로써 같은 버킷에 계속해서 데이터가 쌓이는 클러스터(Cluster)를 방지할 수 있다.

public class DoubleHashingHashTable {
    private static final int TABLE_SIZE = 10;
    private static final int EMPTY_SLOT = -1;
    private int[] table;

    public DoubleHashingHashTable() {
        table = new int[TABLE_SIZE];
        Arrays.fill(table, EMPTY_SLOT);
    }

    // 첫 번째 해시 함수
    private int hashFunction1(int key) {
        return key % TABLE_SIZE;
    }

    // 두 번째 해시 함수
    private int hashFunction2(int key) {
        return 7 - (key % 7);
    }

    // 데이터 추가
    public void put(int key, int value) {
        int hashValue = hashFunction1(key);
        int i = 0;

        // 비어있는 슬롯을 찾을 때까지 이중 해싱 수행
        while (table[hashValue] != EMPTY_SLOT) {
            hashValue = (hashFunction1(key) + i * hashFunction2(key)) % TABLE_SIZE;
            i++;
        }

        // 데이터 추가
        table[hashValue] = value;
    }

    // 데이터 검색
    public int get(int key) {
        int hashValue = hashFunction1(key);
        int i = 0;

        // 키에 해당하는 데이터를 찾을 때까지 이중 해싱 수행
        while (table[hashValue] != key) {
            hashValue = (hashFunction1(key) + i * hashFunction2(key)) % TABLE_SIZE;
            i++;

            // 모든 슬롯을 검색한 경우 데이터가 없다는 것을 의미
            if (table[hashValue] == EMPTY_SLOT || i >= TABLE_SIZE) {
                return EMPTY_SLOT;
            }
        }

        return table[hashValue];
    }
}

위 코드에서는 먼저, 첫 번째 해시 함수를 이용하여 버킷의 인덱스를 계산한다. 데이터를 추가할 때는 해당 버킷이 비어있는지 확인하고, 비어있는 경우 해당 버킷에 데이터를 저장한다. 만약 버킷이 비어있지 않다면 이중 해싱을 이용하여 일정한 값을 더하여 다음 버킷으로 이동하여 비어있는 버킷을 찾아 데이터를 저장한다. 이때 첫 번째 해시 함수와 두 번째 해시 함수를 모두 사용하여 각각 계산된 값을 더해준다. 이렇게 함으로써 같은 버킷에 계속해서 데이터가 쌓이는 클러스터(Cluster)를 방지할 수 있다.

데이터를 검색할 때도 마찬가지로 첫 번째 해시 함수를 이용하여 키에 해당하는 버킷의 인덱스를 계산한다. 해당 버킷에 저장된 데이터가 검색하려는 데이터가 아니라면 이중 해싱을 이용하여 일정한 값을 더하여 다음 버킷으로 이동하여 검색을 계속한다. 이때 첫 번째 해시 함수와 두 번째 해시 함수를 모두 사용하여 각각 계산된 값을 더해주고, 만약 검색하려는 데이터를 찾지 못하고 모든 버킷을 검색한 경우 데이터가 존재하지 않는 것으로 간주한다.

이중 해싱은 제곱 탐사법(Quadratic Probing)과 비슷한 원리를 가지고 있지만, 이중 해싱에서는 간격이 일정하지 않고 해시 함수의 출력값에 따라 달라지기 때문에 클러스터(Cluster)가 형성되는 경향이 덜하다는 장점이 있다.

2. 분리 연결법

분리 연결법은 해시 테이블의 각 버킷에 연결 리스트(Linked List)를 이용하여 데이터를 저장한다. 따라서 같은 버킷에 여러 개의 데이터가 저장될 수 있다. 해시 충돌이 발생하더라도 다른 버킷의 데이터에 영향을 주지 않기 때문에 해시 충돌 해결 방법 중 가장 간단하고 효율적인 방법이다.

public class SeparateChainingHashTable {
    private static final int TABLE_SIZE = 10;
    private LinkedList<Integer>[] table;

    public SeparateChainingHashTable() {
        table = new LinkedList[TABLE_SIZE];

        // 각 버킷에 빈 연결 리스트를 할당합니다.
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 해시 함수
    private int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

    // 데이터 추가
    public void put(int key, int value) {
        int hashValue = hashFunction(key);

        // 해당 버킷의 연결 리스트에 데이터를 추가합니다.
        table[hashValue].add(value);
    }

    // 데이터 검색
    public int get(int key) {
        int hashValue = hashFunction(key);

        // 해당 버킷의 연결 리스트를 검색하여 데이터를 찾습니다.
        for (int value : table[hashValue]) {
            if (value == key) {
                return value;
            }
        }

        // 데이터가 없는 경우 -1을 반환합니다.
        return -1;
    }
}

위 코드에서는 먼저, 각 버킷에 빈 연결 리스트를 할당한다. 데이터를 추가할 때는 해시 함수를 이용하여 해당 버킷의 연결 리스트에 데이터를 추가한다. 데이터를 검색할 때는 해시 함수를 이용하여 해당 버킷의 연결 리스트를 검색하여 데이터를 찾는다.

분리 연결법은 해시 충돌 해결 방법 중에서 구현이 간단하고 효율적인 방법입니다. 그러나, 저장할 데이터의 수가 적은 경우에는 메모리 낭비가 발생할 수 있습니다. 또한, 연결 리스트의 길이가 길어질수록 검색 시간이 느려질 수 있습니다. 이러한 단점을 보완하기 위해서는 다른 해시 충돌 해결 방법을 사용할 수 있습니다.


HashTable 예제 소스 (프로그래머스 문제)

1. 폰켄몬 (Level.1)

폰켓몬 문제는 폰켓몬이 담긴 배열에서 N/2마리의 폰켓몬을 선택하는 문제이다. 중복되지 않는 폰켓몬의 종류 수를 반환하는 문제이다.

해시 테이블을 이용하여 중복되지 않는 폰켓몬의 종류 수를 구하는 방법이 있다.

import java.util.HashSet;

public class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            hashSet.add(num);
        }
        return Math.min(hashSet.size(), nums.length / 2);
    }
}

위 코드에서는 HashSet을 이용하여 중복되지 않는 폰켓몬의 종류를 저장하고, 최종 결과값을 반환한다.
HashSet의 크기와 배열 길이의 절반 중 더 작은 값을 반환하여, 중복되지 않는 폰켓몬 종류수를 구할 수 있다.


2. 완주하지 못한 선수 (Level.1)

완주하지 못한 선수 문제의 해결을 위해서는 다음과 같은 알고리즘을 구현해야 한다.

  1. 해시 테이블을 이용하여 참여한 선수들의 이름과 참여 여부를 저장한다.
  2. 완주한 선수들의 이름을 해시 테이블에서 검색하여 참여 여부를 false로 변경한다.
  3. 참여하지 못한 선수(참여 여부가 true인 선수)를 해시 테이블에서 검색하여 반환한다.

다음은 위 알고리즘을 구현한 코드이다.

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

public class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        // 참여한 선수들의 이름과 참여 여부를 저장하는 해시 테이블을 생성합니다.
        Map<String, Integer> hashTable = new HashMap<>();

        // 참여한 선수들의 이름과 참여 여부를 해시 테이블에 추가합니다.
        for (String name : participant) {
            if (!hashTable.containsKey(name)) {
                hashTable.put(name, 1);
            } else {
                hashTable.put(name, hashTable.get(name) + 1);
            }
        }

        // 완주한 선수들의 이름을 해시 테이블에서 검색하여 참여 여부를 false로 변경합니다.
        for (String name : completion) {
            hashTable.put(name, hashTable.get(name) - 1);
        }

        // 참여하지 못한 선수(참여 여부가 true인 선수)를 해시 테이블에서 검색하여 반환합니다.
        for (String name : participant) {
            if (hashTable.get(name) != 0) {
                answer = name;
                break;
            }
        }

        return answer;
    }
}

위 코드에서는 먼저, 참여한 선수들의 이름과 참여 여부를 저장하는 해시 테이블을 생성한다. 참여한 선수들의 이름과 참여 여부를 해시 테이블에 추가한다. 그리고, 완주한 선수들의 이름을 해시 테이블에서 검색하여 참여 여부를 false로 변경한다. 마지막으로, 참여하지 못한 선수(참여 여부가 true인 선수)를 해시 테이블에서 검색하여 반환한다.

해시 테이블을 이용하여 데이터를 저장하고 검색하는 연습을 할 수 있는 좋은 문제!


3. 전화번호 목록 (Level.2)

전화번호 목록 문제는 전화번호부에 적힌 전화번호들 중에 어떤 번호가 다른 번호의 접두어인 경우가 있는지를 판별하는 문제이다. 해시 테이블을 이용하여 효율적으로 해결할 수 있다.

다음은 phone_book 배열에 저장된 전화번호들 중에서 어떤 번호가 다른 번호의 접두어인지 판별하는 함수 solution의 예시 코드이다. (사실, 챗GPT가 풀어준 정답...)

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

public class Solution {
    public boolean solution(String[] phone_book) {
        // 해시 테이블을 생성합니다.
        Map<String, Integer> hashTable = new HashMap<>();

        // 전화번호들을 해시 테이블에 추가합니다.
        for (String phone : phone_book) {
            hashTable.put(phone, 1);
        }

        // 각 전화번호의 접두어가 해시 테이블에 존재하는지 검사합니다.
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                String prefix = phone.substring(0, i);
                if (hashTable.containsKey(prefix)) {
                    return false;
                }
            }
        }

        return true;
    }
}

위 코드에서는 HashMap을 이용하여 각 전화번호를 저장하고, 각 전화번호의 접두어가 해시 테이블에 존재하는지 검사하여 결과를 반환한다.

문제를 효율적으로 해결하기 위해, 전화번호를 해시 테이블에 추가하기 전에 각 전화번호의 접두어가 이미 해시 테이블에 존재하는지 검사하지 않는 것이 중요하다. 이렇게 하면 각 전화번호의 접두어가 이미 해시 테이블에 존재하는 경우에도 전화번호를 추가할 수 있기 때문이다.


profile
I'm still hungry.

0개의 댓글