[자료구조] 해시 - (2) 구현 - 충돌해결 -① Chaining

class ValuePair{
    constructor(key,value){
        this.key = key;
        this.value = value;
    }
}
class HashTable{
    constructor(){
        this.storageLimit = 10;
        this.table = new Array(this.storageLimit);
    }

    Hash(key){
        let hash = 0;

        for(let i = 0; i < key.length; i++){
            hash += key.charCodeAt(i);
        }

        return hash % this.storageLimit;
    }

    add(key,value){
        const index = this.Hash(key);

        if(this.table[index] === undefined){
            this.table[index] = new LinkedList();
        }
        this.table[index].append(new ValuePair(key,value));
    }

    get(key){
        const index = this.Hash(key);
        let current = this.table[index].getHead();
        if(this.table[index] !== undefined){
            while(current !== null){
                if(current.element.key === key){
                    return current.element.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }

    remove(key){
        const index = this.Hash(key);
        let current = this.table[index].getHead();

        if(this.table[index] !== undefined){
            while(current !== null){
                if(current.element.key === key){
                    this.table[index].remove(current.element);
                    if(this.table[index].isEmpty()){
                        this.table[index] = undefined;
                    }
                }
                current = current.next;
            }
            return true;
        }
        return false;
    }
}

위의 코드는 해시의 충돌을 chaining 방법으로 해결한 코드이다.
chaining 방법이란 서로 다른 키에서 해시 함수를 거쳐 같은 해시 값을 갖게 되는 충돌을 막기 위해
LinkedList로 값을 연결시켜준 형태이다.

HashTable은 배열이고, 각 배열의 인덱스 자리마다 LinkedList를 만들어서 같은 해시 값을 갖게되는 데이터가 계속 들어오더라도 연결 리스트로 처리한다.
즉, HashTable이라는 배열 안에는 LinkedList가 인덱스 마다 들어있고
LinkedList 안에는 Node가 들어 있는데
그 Node 안에는 element와 next가 존재하고
element 안에 ValuePair를 넣었으며 ValuePair는 key,value로 구성되는 것이다.

위의 코드를 실행하기 위해서는 예전 게시물에서 LinkedList를 class로 작성한 코드도 있어야 한다.
한 js 파일 안에 클래스를 다 가져와도 되고, 그것을 실행할 html 파일에서 script src로 js 파일을 두개를 연결해도 된다.