초보 자바 프로그래밍(30) - 개방주소법 (Open Addressing)

개방 주소법 대표 이미지

🔖 INDEX

 

 

개방 주소법(Open Addressing)은 모든 키-값 쌍을 해시 테이블 자체에 직접 저장하는 방법입니다. 충돌이 발생하면, 다른 버킷에 키-값 쌍을 저장하는 방법을 사용합니다. 개방 주소법에는 선형 탐사(linear probing), 이차 탐사(quadratic probing), 더블 해싱(double hashing) 등의 충돌 해결 방식이 있습니다.

 

개방 주소법의 특징

개방 주소법의 장점은 다음과 같습니다:

• 해시 테이블 외부에 추가적인 메모리를 사용하지 않으므로 공간 효율성이 높습니다.
• 캐시 지역성이 좋아서 연속된 메모리 위치에 데이터를 저장할 수 있습니다. ​

 

개방 주소법의 단점은 다음과 같습니다:

• 해시 테이블의 로드 팩터가 높아지면 성능 저하가 심해집니다. 일반적으로 로드 팩터가 0.7 이상이 되면 리사이징을 고려해야 합니다.
• 충돌 해결 방식에 따라 클러스터링(clustered) 문제가 발생할 수 있어 성능이 저하될 수 있습니다. ​

 

개방 주소법 구현 예제 (선형탐사 방식)

다음은 선형 탐사(linear probing) 방식을 구현한 예제 입니다:

public class LinearProbingHashTable<K, V> {
    private int capacity; // 해시 테이블의 크기
    private int size; // 현재 저장된 요소의 개수
    private K[] keys; // 키를 저장하는 배열
    private V[] values; // 값들을 저장하는 배열

    // 생성자에서 초기 용량을 설정하고, 키와 값 배열을 생성합니다.
    public LinearProbingHashTable(int capacity) {
        this.capacity = capacity;
        keys = (K[]) new Object[capacity];
        values = (V[]) new Object[capacity];
    }

    // 주어진 키에 해당하는 값을 반환합니다.
    public V get(K key) {
        // 선형 탐사를 사용하여 주어진 키와 일치하는 키를 찾습니다.
        for (int i = hash(key); keys[i] != null; i = (i + 1) % capacity) {
            if (keys[i].equals(key)) {
                return values[i];
            }
        }
        return null;
    }

    // 주어진 키와 값을 해시 테이블에 저장합니다.
    public void put(K key, V value) {
        // 해시 테이블이 절반 이상 차있으면 크기를 두 배로 늘립니다.
        if (size >= capacity / 2) {
            resize(2 * capacity);
        }

        // 선형 탐사를 사용하여 빈 버킷 또는 주어진 키와 일치하는 버킷을 찾습니다.
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % capacity) {
            if (keys[i].equals(key)) {
                values[i] = value; // 키가 이미 존재하면 값을 업데이트합니다.
                return;
            }
        }
        keys[i] = key;
        values[i] = value;
        size++; // 저장된 요소의 개수를 증가시킵니다.
    }

    // 해시 테이블의 크기를 조정하고, 키와 값을 새로운 크기에 맞게 재해싱합니다.
    private void resize(int newCapacity) {
        LinearProbingHashTable<K, V> temp = new LinearProbingHashTable<>(newCapacity);
        for (int i = 0; i < capacity; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], values[i]);
            }
        }
        keys = temp.keys;
        values = temp.values;
        capacity = temp.capacity;
    }

    // 주어진 키에 대한 해시 값을 계산합니다.
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }
}

 

 

개방 주소법 구현 예제 (이차탐사 방식)

다음은 이차 탐사(quadratic probing) 방식을 구현한 예제 입니다:

public class OpenAddressingHashTable {
    // 해시 테이블 크기 설정
    private static final int TABLE_SIZE = 10;

    // 해시 테이블 배열
    private Integer[] table;

    // 생성자에서 해시 테이블 초기화
    public OpenAddressingHashTable() {
        table = new Integer[TABLE_SIZE];
    }

    // 해시 함수 구현 (key를 해시 테이블 크기로 나눈 나머지를 반환)
    private int hash(int key) {
        return key % TABLE_SIZE;
    }

    // 이차 탐사 함수 구현 (i 제곱을 반환)
    private int quadraticProbing(int i) {
        return i * i;
    }

    // 삽입 함수 구현
    public void insert(int key) {
        int index = hash(key); // 해시 함수를 이용해 인덱스 계산
        int i = 0;

        // 이차 탐사 방식으로 충돌이 해결될 때까지 반복
        while (table[(index + quadraticProbing(i)) % TABLE_SIZE] != null) {
            i++;
        }

        // 충돌이 해결된 위치에 key를 삽입
        table[(index + quadraticProbing(i)) % TABLE_SIZE] = key;
    }

    // 검색 함수 구현
    public int search(int key) {
        int index = hash(key); // 해시 함수를 이용해 인덱스 계산
        int i = 0;

        // 이차 탐사 방식으로 원하는 key를 찾거나, 빈 공간을 발견할 때까지 반복
        while (table[(index + quadraticProbing(i)) % TABLE_SIZE] != null && table[(index + quadraticProbing(i)) % TABLE_SIZE] != key) {
            i++;
        }

        // 원하는 key를 찾은 경우 해당 인덱스를 반환, 그렇지 않으면 -1을 반환
        return (table[(index + quadraticProbing(i)) % TABLE_SIZE] != null) ? (index + quadraticProbing(i)) % TABLE_SIZE : -1;
    }
}

위의 코드는 자바로 작성된 개방주소법 이차탐사 방식을 구현한 예제입니다. 이차탐사 방식은 충돌이 발생한 경우, 이차 함수를 이용해 다음 위치를 탐색하여 충돌을 해결합니다. 이 방식은 선형 탐사 방식보다 클러스터링 현상이 덜 발생하여 효율이 좋습니다.

 

 

개방 주소법 구현 예제 (더블해싱 방식)

다음은 더블 해싱(double hashing) 방식을 구현한 예제 입니다:

public class DoubleHashingHashTable {
    // 해시 테이블 크기 설정
    private static final int TABLE_SIZE = 10;

    // 해시 테이블 배열
    private Integer[] table;

    // 생성자에서 해시 테이블 초기화
    public DoubleHashingHashTable() {
        table = new Integer[TABLE_SIZE];
    }

    // 첫 번째 해시 함수 구현 (key를 해시 테이블 크기로 나눈 나머지를 반환)
    private int hash1(int key) {
        return key % TABLE_SIZE;
    }

    // 두 번째 해시 함수 구현 (소수 R로 나눈 나머지에 1을 더한 값을 반환)
    private int hash2(int key) {
        int R = 7; // 해시 테이블 크기보다 작은 소수
        return R - (key % R) + 1;
    }

    // 삽입 함수 구현
    public void insert(int key) {
        int index = hash1(key); // 첫 번째 해시 함수를 이용해 인덱스 계산
        int step = hash2(key); // 두 번째 해시 함수를 이용해 스텝 계산

        // 더블 해싱 방식으로 충돌이 해결될 때까지 반복
        while (table[index] != null) {
            index = (index + step) % TABLE_SIZE;
        }

        // 충돌이 해결된 위치에 key를 삽입
        table[index] = key;
    }

    // 검색 함수 구현
    public int search(int key) {
        int index = hash1(key); // 첫 번째 해시 함수를 이용해 인덱스 계산
        int step = hash2(key); // 두 번째 해시 함수를 이용해 스텝 계산

        // 더블 해싱 방식으로 원하는 key를 찾거나, 빈 공간을 발견할 때까지 반복
        while (table[index] != null && table[index] != key) {
            index = (index + step) % TABLE_SIZE;
        }

        // 원하는 key를 찾은 경우 해당 인덱스를 반환, 그렇지 않으면 -1을 반환
        return (table[index] != null) ? index : -1;
    }
}

위의 코드는 자바로 작성된 개방주소법 더블 해싱 방식을 구현한 예제입니다. 더블 해싱 방식은 충돌이 발생한 경우, 두 개의 해시 함수를 사용하여 다음 위치를 탐색하여 충돌을 해결합니다. 이 방식은 이차탐사 방식보다 클러스터링 현상이 더욱 줄어들어 효율이 좋습니다.