[자료구조/해시] 해시 충돌 처리를 (간단하게)구현해보자

체이닝 방식을 이용한 해시 충돌 처리를 구현해보자!

체이닝 방식은 해시 테이블에서 충돌이 발생할 경우 충돌된 키를 연결 리스트 형태로 처리하는 방법이다.

충돌이 발생하면 동일한 해시 버킷에 속한 항목들을 연결 리스트로 연결하여 저장한다.

 

해시를 저장할 버킷을 링크드 리스트로 선언한다.
링크드 리스트에 키값 멤버를 가진 노드를 저장할 것이다.

private static final int DEFAULT_BUCKET_SIZE = 1024;

    private List<Node>[] buckets;
    private int size;
    private int bucketSize;

    public MyLinkedHashTable() {
        this.buckets = new List[DEFAULT_BUCKET_SIZE];
        this.bucketSize = DEFAULT_BUCKET_SIZE;
        this.size = 0;

        // 버킷을 링크드 리스트로 초기화 해준다.
        for (int i = 0; i < bucketSize; i++) {
            this.buckets[i] = new LinkedList<>();
        }
    }

사용자가 파라미터로 전달한 키가 버킷에 이미 존재하는 경우 hashMap 방식으로 처리한다. (덮어쓰자)
링크드 리스트에 추가해주자.

        @Override
        public void put(K key, V value) {
        int idx = hash(key);
        List<Node> bucket = buckets[idx];

                // 만약 사용자가 입력한 키 값이 이미 등록되어 있다면 덮어쓴다. (hashMap 방식)
        for (Node node : bucket) {
            if (node.key.equals(key)){
                node.data = value;
            }
        }

                //링크드 리스트에 노드를 추가해준다.
        Node node = new Node(key, value);
        bucket.add(node);
        size++;
    }

 

Open Addressing (선형 탐사)을 이용한 해시 충돌 처리를 구현해보자!

선형 탐사(Linear Probing)는 오픈 어드레싱의 한 종류로, 충돌이 발생한 경우 다음 순서에 있는 빈 버킷을 찾아 삽입하는 방식이다.

선형적으로 다음 버킷을 검사하여 빈 버킷을 찾을 때까지 진행된다.

 

해시를 저장할 버킷을 배열로 선언한다.

public class MyHashTable<K, V> implements IHashTable<K, V> {

    private static final int DEFAULT_BUKET_SIZE = 1024;

    private Entry<?, ?>[] bucket;
    private int size;
    private int bucketSize;

    public MyHashTable() {
        bucket = new Entry<?, ?>[DEFAULT_BUKET_SIZE];
        size = DEFAULT_BUKET_SIZE;
    }
    
    ...

만약 버킷이 가득 차 있다면 예외를 발생시킬 것이고,

버킷에 공간이 남아있다면 빈 자리를 순차적으로 탐색하여 빈 공간에 해시를 저장한다.

@Override
    public void put(K key, V value) throws IllegalArgumentException {
        if (size == bucketSize) throw new IllegalArgumentException("Hash table is full.");

        int idx = hash(key);

        while (!Objects.isNull(bucket[idx])) {
            idx += 1 % bucketSize;
        }

        bucket[idx] = new Entry<>(key, value);
        size++;
    }

해당 방법은 데이터가 밀집될 확률이 높다.

그렇다면.. 해시충돌이 일어날 확률이 높아진다는 것이다.

 

 

Open Addressing (이차 탐사)을 이용한 해시 충돌 처리를 구현해보자!

@Override
    public void put(K key, V value) throws IllegalArgumentException {
        if (size == bucketSize) throw new IllegalArgumentException("Hash table is full.");

        int idx = hash(key);
        int offset = 1;

        while (!Objects.isNull(bucket[idx])) {
            idx += (idx + offset * offset) % bucketSize;
            offset++;
        }

        bucket[idx] = new Entry<>(key, value);
        size++;
    }

음 선형 탐사보다는 데이터가 밀집될 확률이 낮아진 것 같다.

 

 

Open Addressing (이중 해시)을 이용한 해시 충돌 처리를 구현해보자!

@Override
    public void put(K key, V value) throws IllegalArgumentException {
        if (size == bucketSize) throw new IllegalArgumentException("Hash table is full.");

        int idx = hash(key);
        int offset = hash2(key);

        while (!Objects.isNull(bucket[idx])) {
            idx = (idx + offset) % bucketSize;
        }

        bucket[idx] = new Entry<>(key, value);
        size++;
    }

    private int hash2(K key) {
        int hash = bucketSize - 2;
        return hash - (hash(key) % hash);
    }

해시 충돌이 일어났을 때, 새로운 해시 값을 도출해낼 해시 함수를 구현한다.