[javascript] Hash table, 해시 테이블 (2)

hash table에 대한 포스팅을 조금 더 찾아봤는데 충돌이 일어날 경우  open adress 방식이나, seperate Chaining 방식으로 해당 충돌을 우회 해야한다고 다들 적어놓았지만 충돌이 일어나 다른 곳에 저장한 후 해당 key로 어떻게 data를 찾는지는 나오지 않았다.

 

그래서 해시테이블을 직접 만들어 보면 어떨까 싶어 해시테이블 2부를 만들게 되었다. 

 

원시적인 해시테이블

 

function HashTable(){
    let array = [];
    let size = 20;

    return {
        hashFunc(key){
            let hashValue = key.length % size;
            return hashValue;
        },
        add(key,item){
            if(array[this.hashFunc(key)] != null){
                console.log(new Error("해시값 충돌 !"));
                return;
            }
            array[this.hashFunc(key)] = item;
        },
        delete(key){
                array[this.hashFunc(key)] = null;
        },
        get(key){
            return array[this.hashFunc(key)];
        }
    } 
}

let hash = HashTable();

hash.add("jhon","hokeys");
hash.add("jhaa","hokeys"); // 에러

console.log(hash.get("jhon"));

 

아주 간단하게 나누기 방법으로 해시값을 만들어서 배열에 저장하는데 여기 까지는 문제가 없다. 그러나 만약 jhon과 같이 4글자의 다른 key로 저장을 하면 해시충돌이 일어날 것이다. 그래서 충돌이 일어날 경우에 대비해 선형 탐사 방법으로 충돌을 우회해 보려 한다. 

 

function HashTable(){
    let array = [];
    let size = 20;

    return {
        hashFunc(key){
            let hashValue = key.length % size;
            if(hashValue % 4 != 0 && hashValue <= 16){
                while(hashValue % 4 != 0){
                    hashValue++;
                }
            }
            return hashValue;
        },
        linearSearch(hashValue){
            let max = hashValue +4;
            while(array[hashValue] != null && hashValue != max){
                hashValue++
            }
            if(hashValue+1 == max){
                console.log(new Error("해쉬테이블에 빈공간이 없습니다."));
            }
            return hashValue;
        },
        add(key,item){
            array[this.linearSearch(this.hashFunc(key))] = item;
        },
        delete(key){
                array[this.hashFunc(key)] = null;
        },
        get(key){
            return array[this.hashFunc(key)];
        }
    } 
}

let hash = HashTable();
hash.add("jhon","hokeys");
hash.add("mark","toto");

console.log(hash.get("jhon"));

 

위와 같이 해쉬값들을 4의 배수로 만들고 linearSearch라는 메서드를 만들어서 충돌을 충돌우회범위값 까지 새롭게 늘렸지만 get으로 새롭게 추가한 mark key를 가진 value를 찾을 수는 없었다. 그래서 예전에 c#에서 봤던 dictionary라는 것을 사용해서 배열에 저장할 때 key와 value를 함께 보관하도록 새로운 클래스를 만들어 보겠다. 

 

function Dictionary(key,value){
    return {
        key : key,
        value : value,
    }
}

 

Dictionary는 생성자인자로 key와 value를 받아 key와 value 프로퍼티에 저장한다. 그래서 이번엔.get과 delete에서 해당 key를 대조해보고 방을 이동해서 해당 key를 가진 dictionary가 있는지를 판단하도록 변경해보겠다.

 

linearSearch(hashValue){
            let max = hashValue +4;
            while(array[hashValue] != null && hashValue != max && array[hashValue].value != "deleted"){
                hashValue++
            }
            if(hashValue+1 == max){
                
                return console.log("해쉬테이블에 빈공간이 없습니다.");
            }
            return hashValue;
        },

 

linearHashValue(key){
            let hashValue = this.hashFunc(key);
            let max = hashValue +4;
            while(array[hashValue] != undefined && array[hashValue].key != key && hashValue != max && array[hashValue].value == "deleted"){
                hashValue++
            }
            if(hashValue + 1 == max || array[hashValue] == undefined){
                return "찾는 value 가 없습니다.";
            }
            return hashValue;
        }

 

linearSearch와 linearHashValue 메서드는 각각 add를 하기 위해 빈방을 찾아주는 함수와 key에 알맞은 hashValue를 반환 하는 함수이다. 

 

각 함수의 반복문을 보면 상당히 조건이 까다롭고 길다. 

 

그리고 add와 delete, get 또한 변경 되었다. 

add(key,item){
            array[this.linearSearch(this.hashFunc(key))] = new Dictionary(key,item);
            console.log(array);
        },
        delete(key){
            hashValue = this.linearHashValue(key);
            if(hashValue === new String()){
                console.log("오류");
                return hashValue;
            }
            array[hashValue].value = "deleted";
        },
        get(key){
            hashValue = this.linearHashValue(key);
            if(typeof hashValue === typeof String()){
                return hashValue;
            }
            return array[hashValue].value;
        },

 

 

전체

 

function Dictionary(key,value){
    return {
        key : key,
        value : value,
    }
}

function HashTable(){
    let array = [];
    let size = 20;

    return {
        hashFunc(key){
            let hashValue = key.length % size;
            if(hashValue % 4 != 0 && hashValue <= 16){
                while(hashValue % 4 != 0){
                    hashValue++;
                }
            }
            return hashValue;
        },
        linearSearch(hashValue){
            let max = hashValue +4;
            while(array[hashValue] != null && hashValue != max && array[hashValue].value != "deleted"){
                hashValue++
            }
            if(hashValue+1 == max){
                console.log(new Error("해쉬테이블에 빈공간이 없습니다."));
                return 0;
            }
            return hashValue;
        },
        add(key,item){
            array[this.linearSearch(this.hashFunc(key))] = new Dictionary(key,item);
            console.log(array);
        },
        delete(key){
            hashValue = this.linearHashValue(key);
            if(hashValue === new Error){
                console.log("오류");
                return hashValue;
            }
            array[hashValue].value = "deleted";
        },
        get(key){
            hashValue = this.linearHashValue(key);
            if(typeof hashValue === typeof String()){
                return hashValue;
            }
            return array[hashValue].value;
        },
        linearHashValue(key){
            let hashValue = this.hashFunc(key);
            let max = hashValue +4;
            while(array[hashValue] != undefined && array[hashValue].key != key && hashValue != max && array[hashValue].value == "deleted"){
                hashValue++
            }
            if(hashValue + 1 == max || array[hashValue] == undefined){
                return "찾는 value 가 없습니다.";
            }
            return hashValue;
        }
    } 
}

let hash = HashTable();
hash.add("jhon","hokeys");
hash.add("mark","toop");
hash.add("lee jong ho","jasmin");

console.log(hash.get("lee jong ho"));

hash.delete("jhon");
console.log(hash.get("jhon"));
console.log(hash.get("mark"));
hash.add("jhon","hokeys");
console.log(hash.get("jhon"));

 

정리하며 

잘 작동은 하나 일단은 썩 마음에 들지 않는다. 해당 리니어 서치를 하기위해서 O(1) 의 시간복잡도에서 O(1 + a) 가 되어버렸다. 만약 충돌시 폭이 넓었다면 더 오래 걸렸을 것이다. 조금 더 좋은 해시값충돌우회 방법을 연구해봐야 겠다.