초보 자바 프로그래밍(29) - 개별체이닝 (Separate Chaining)

개별 체이닝 대표 이미지

🔖 INDEX

 

 

개별 체이닝은 각 해시 버킷에 연결 리스트(linked list) 또는 트리와 같은 자료 구조를 사용하여 키-값 쌍을 저장하는 방법입니다. 충돌이 발생하면, 해당 버킷에 있는 연결 리스트에 새로운 키-값 쌍을 추가합니다.

 

개별 체이닝의 특징

개별 체이닝의 장점은 다음과 같습니다:

• 해시 테이블의 크기와 상관없이 삽입, 삭제, 검색 연산이 상수 시간에 가능합니다(연결 리스트의 길이가 작은 경우).
• 해시 테이블의 로드 팩터가 높아져도 성능 저하가 덜 합니다. ​

 

개별 체이닝의 단점은 다음과 같습니다:

• 연결 리스트를 사용하므로, 메모리 할당 및 해제에 추가적인 오버헤드가 발생합니다.
• 연결 리스트를 사용하기 때문에 캐시 지역성이 떨어져 성능이 저하될 수 있습니다.

 

 

개별 체이닝 구현 예제

개별 체이닝 방식을 구현하는 예제 코드는 다음과 같습니다.

import java.util.LinkedList;

public class SeparateChainingHashTable<K, V> {
    private int capacity; // 해시 테이블의 크기
    private LinkedList<Cell<K, V>>[] table; // 연결 리스트의 배열

    // 생성자에서 해시 테이블의 크기를 설정하고, 각 연결 리스트를 초기화합니다.
    public SeparateChainingHashTable(int capacity) {
        this.capacity = capacity;
        table = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 주어진 키에 해당하는 값을 반환합니다.
    public V get(K key) {
        // 해시 함수를 사용하여 해당 키가 저장된 연결 리스트를 찾습니다.
        int index = hash(key);
        for (Cell<K, V> cell : table[index]) {
            if (cell.key.equals(key)) {
                return cell.value;
            }
        }
        return null;
    }

    // 주어진 키와 값을 해시 테이블에 저장합니다.
    public void put(K key, V value) {
        // 해시 함수를 사용하여 해당 키가 저장된 연결 리스트를 찾습니다.
        int index = hash(key);
        for (Cell<K, V> cell : table[index]) {
            if (cell.key.equals(key)) {
                cell.value = value; // 이미 존재하는 키라면 값을 업데이트합니다.
                return;
            }
        }
        table[index].add(new Cell<>(key, value)); // 새로운 키라면 연결 리스트에 추가합니다.
    }

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

    // 연결 리스트의 각 노드로 사용될 객체입니다.
    private static class Cell<K, V> {
        private K key;
        private V value;

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