[Javascript] 해시 충돌의 해결

지난번에 해시 테이블을 구현했지만, 해시 충돌을 해결할 수는 없었습니다. 그래서 이번에는 해시 충돌의 해결 방법을 알아보겠습니다.

---

1. 첫번째 방법, 선형 탐사법 Linear Probing

여태까지 많은 자료구조와 알고리즘을 하면서 선형이라는 이름이 붙으면 어떻게 하는지 기억하시나요? 바로 하나씩 일일히 순서대로 확인했습니다. 바로 선형 탐사법이 이 방식을 이용해서 빈 테이블의 위치를 찾습니다. 선형 방식의 문제들이 그렇듯이 테이블의 크기가 늘어나면 해시의 빠른 연산속도가 느려진다는 단점을 수반합니다.

    insertLinearProbing(key, value) {
        const id = this.hash(key);

        if(this.table[id]) {
            let flag = true;

            for (let i = id + 1; i !== id; i++) {
                if(i === this.table.length) {
                    i = 0;
                }
                if (!this.table[i]) {
                    this.table[i] = value;
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return console.log('삽입 실패: 테이블에 공간이 없습니다!');
            }
        }
        else {
            this.table[id] = value;
        }
    }

 

 

 

2. 두번째 방법, 체이닝 Chaining

이전에 본 선형 탐사는 해시 충돌 발생 시 다른 위치에 value를 저장합니다. 이 방식을 open addressing method라고합니다. 반면 이번에 볼 체이닝 방식은 closed addressing method로 무조건 해당 자리에 저장을 하는 방식입니다. 그런데, 이미 자리를 차지하고 있는 테이블에 어떻게 다른 값을 넣을 수 있을까요?

그 방법은 2차원 배열과 연결 리스트를 이용하면 됩니다. 2차원 배열을 이용하면 해시값에 여러개의 값을 넣을 수 있습니다. 또 연결 리스트를 이용하면 해당 해시값에 노드들을 줄줄이 이어서 마찬가지로 여러 값을 이용할 수 있게 되는 방식입니다. 이 중에서도 연결 리스트를 줄줄이 연결해서 체인처럼 이었다고 해서 해시 충돌을 막는 두번째 방법을 체이닝이라고 부릅니다.

class HashTableNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.nextNode = null;
    }
}

    insertChaining(key, value) {
        const id = this.hash(key);
        const newNode = new HashTableNode(key, value);

        //삽입 위치에 이미 노드가 있으면
        if (this.table[id]) {
            const currentNode = this.table[id];
            
            //새 노드를 head로 두고 이어준다.
            this.table[id] = newNode;
            this.table[id].next = currentNode;
        }
        else {
            this.table[id] = newNode;
        }
    }

 

 

체이닝은 연결 리스트를 이용해서 탐색도 약간 다른 방식으로 진행합니다. 하지만 어렵지 않습니다.

    searchChaining(key) {
        const id = this.hash(key);
        let currentNode = this.table[id];

        //찾으려는 key와 일치할 때 까지 노드를 찾음
        while(currentNode) {
            if (currentNode.key === key) {
                break;
            }

            currentNode = currentNode.next;
        }
        return currentNode;
    }

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/data-structure/HashTable.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록