[자료구조] 해시 - (2) 구현 - 충돌해결 - ② linear probing

🎈선형탐색법(linear probing)

새 원소 추가 시 인덱스가 이미 점유된 상태라면 인덱스+1 을 찾아보고, 인덱스+1도 점유됐다면 인덱스+2를 찾아보는 식으로 충돌을 회피하는 방법

 

🎀 앞서 기본적인 해시테이블을 구현할 때와 chaining으로 충돌을 해결했을 때에는

기본적으로 해시테이블의 constructor에서 테이블(배열)의 사이즈를 storageLimit으로 지정해놓았었는데,

선형탐색법 방법에서는 제한을 두지 않을 것이다.

 

🎁 다른 프로그래밍 언어에서는 배열의 크기를 미리 정하게 되어 있는데, 선형 탐색법에서 한 가지 신경쓰이는 부분이 배열 인덱스가 가능한 범위를 벗어났을 경우이다. 자바스크립트에서는 배열을 따로 크기를 지정해놓지 않아도 원소를 추가하면 자동으로 크기가 늘어나므로 전혀 고민할 필요가 없다.

 

class ValuePair{

        constructor(key,value){

            this.key = key;

            this.value = value;

        }

    }

class HashTable{

    constructor(){

        this.table = [];

    }

    Hash(key){

        let hash = 0;

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

            hash += key.charCodeAt(i);

        }

        return hash % 10;

    }

    add(key,value){

        let index = this.Hash(key);

        if(this.table[index] === undefined){

            this.table[index] = new ValuePair(key,value);

        }else{

            let anotherIndex = ++index;

            while(this.table[anotherIndex]){

                anotherIndex++;

            }

            this.table[anotherIndex] = new ValuePair(key,value);

        }

    }

    get(key){

       let index = this.Hash(key);

       if(this.table[index] !== undefined){

           if(this.table[index].key === key){

               return this.table[index].value;

           }else{

               let anotherIndex = ++index;

               while(this.table[anotherIndex] === undefined || this.table[anotherIndex].key !== key){

                   anotherIndex++;

               }

               if(this.table[anotherIndex].key === key){

                   return this.table[anotherIndex].value;

               }

           }

       }

       return undefined;

    }

    remove(key){

        const index = this.Hash(key);

        if(this.table[index] !== undefined){

            if(this.table[index].key === key){

                this.table[index] = undefined;

            }else{

                let anotherIndex = ++index;

                while(this.table[index] === undefined || this.table[index].key !== key){

                    anotherIndex++;

                }

                if(this.table[anotherIndex].key === key){

                    this.table[anotherIndex] = undefined;

                }

            }

        }

    }

    print(){

        for(let i = 0; i < this.table.length; i++){

            if(this.table[i] !== undefined){

                console.log(`${i} -> key: ${this.table[i].key}, value: ${this.table[i].value}`);

            }

        }

    };

}