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

어제 선형탐사 방식을 통하여 해시값 충돌시 해시값을 유효범위까지 늘려 충돌을 우회했다. 그러나 open adress방식을 사용하면 유효범위가 유한하기 때문에 언젠가 충돌이 일어날 수 있었다. 그렇기에 이번에는 chaining 방식을 통해 조금 더 유연한 hash table을 만들어 보겠다. 

 

Seperate Chaining 

 

 

Seperate chaining 은 배열에 연결리스트를 넣어서 유한하던 저장공간문제를 해결하는 방식이다. 다만 메모리문제와 탐색시 최악의 시간 복잡도가 O(n)이 된다는 단점도 가지고 있다. 

 

Double Linked List

function Dictionary(key,value){
    return {
        llink : null,
        key : key,
        value : value,
        rlink : null,
    }
}

 

배열에 저장하는 노드는 key 와 value를 가지고 있으며 추가와 삭제를 용이하게 하기 위해 이중 연결 리스트의 형태를 취하게 만들었다. 

 

Hash Function

 hashFunc(key){
            let hashValue = key.length % size;
            if(hashValue % 4 != 0 && hashValue <= 16){
                while(hashValue % 4 != 0){
                    hashValue++;
                }
            }
            return hashValue;
        },

 

해시 함수는 해당 배열의 Max_size로 key의 length를 나눈 나머지의 값을 hash value로 사용하는 나누기 방법을 택하였다. 

 

add

 add(key,item){
            if(array[this.hashFunc(key)] == null){
                temp = new Dictionary(key,item);
                array[this.hashFunc(key)] = temp;
                temp.rlink = temp;
                temp.llink = temp;
            }else{
                let p = array[this.hashFunc(key)];
                let node = new Dictionary(key,item);
                node.llink = p.llink;
                node.rlink = p;
                p.llink.rlink = node;
                p.llink = node;
            }
        },

 

add는 일반적인 double linked list의 insert 와 같이 처음 배열에 node를 저장할때와 배열내부에 노드가 있을때로 나뉜다. 그리고 저장을 쉽게 하기위해 배열의 끝(head.llink)에 새로운 노드를 추가할 수 있도록 했다 .

 

 

get

get(key){
            hashValue = this.hashFunc(key);
            p = array[hashValue];
            if(p == null){
                return "해당 키를 가진 value가 없습니다.";
            }else{
                head = p.key;
                while(p != null && p.rlink.key != head && p.key != key){
                    console.log(head);
                    p = p.rlink
                }
                if(p != null && p.key == key){
                    return p.value;
                }else{
                    return "해당 key를 가진 value가 없습니다. "
                }
            }
        },

 

get은 해당 키를 가진 node를 찾을때까지 노드를 이동하다가 해당 노드를 찾으면 해당 노드의 value를 반환한다. 

 

delete 

delete(key){
            let hashValue = this.hashFunc(key);
            if(array[hashValue] == null){
                console.log("해당 key를 가진 노드가 없습니다.");
            }else{
                let p = array[this.hashFunc(key)];
                while(p.key != key && p.rlink != array[this.hashFunc(key)]){
                    p = p.rlink;
                }
                if(p.llink === p){
                    array[hashValue] = null;
                }else if(p.key == key){
                    pre = p.llink;
                    pre.rlink = p.rlink;
                    p.rlink.llink = pre;
                    temp = Object.assign({},pre);
                    array[hashValue] = temp;
                }else{
                    console.log("해당 key의 value가 없습니다. ")
                }
            }
        },

 

delete 메서드가 조금 복잡한데 사실 자바스크립트의 연결리스트는 c처럼 포인터를 이용한 구조가 아니라 해당 프로퍼티에 다른 노드를 가지고 있는 구조이다. 그래서 temp 위 코드라인까지 작성해도 맨 처음 입력한 key를 가진 노드는 지울 수 없고 array[hashValue] 에 있는 item은 여전히 맨 처음 저장한 node 객체(p)를 가지고 있는 것이다. 그래서 p.rlink.llink = pre 결과를 array[hashValue]에 저장하기 위해 Object.assign()메서드를 사용하여 link의 정보가 바뀐 객체를 깊은복사하여 array[hashValue]에 할당하는 것이다. 

 

전체

function Dictionary(key,value){
    return {
        llink : null,
        key : key,
        value : value,
        rlink : null,
    }
}

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;
        },
        add(key,item){
            if(array[this.hashFunc(key)] == null){
                temp = new Dictionary(key,item);
                array[this.hashFunc(key)] = temp;
                temp.rlink = temp;
                temp.llink = temp;
            }else{
                let p = array[this.hashFunc(key)];
                let node = new Dictionary(key,item);
                node.llink = p.llink;
                node.rlink = p;
                p.llink.rlink = node;
                p.llink = node;
            }
        },
        delete(key){
            let hashValue = this.hashFunc(key);
            if(array[hashValue] == null){
                console.log("해당 key를 가진 노드가 없습니다.");
            }else{
                let p = array[this.hashFunc(key)];
                while(p.key != key && p.rlink != array[this.hashFunc(key)]){
                    p = p.rlink;
                }
                if(p.llink === p){
                    array[hashValue] = null;
                }else if(p.key == key){
                    pre = p.llink;
                    pre.rlink = p.rlink;
                    p.rlink.llink = pre;
                    temp = Object.assign({},pre);
                    array[hashValue] = temp;
                }else{
                    console.log("해당 key의 value가 없습니다. ")
                }
            }
        },
        get(key){
            hashValue = this.hashFunc(key);
            p = array[hashValue];
            if(p == null){
                return "해당 키를 가진 value가 없습니다.";
            }else{
                head = p.key;
                while(p != null && p.rlink.key != head && p.key != key){
                    console.log(head);
                    p = p.rlink
                }
                if(p != null && p.key == key){
                    return p.value;
                }else{
                    return "해당 key를 가진 value가 없습니다. "
                }
            }
        },
    } 
}

let hash = new HashTable();
hash.add("hokeys","hello");

console.log(hash.get("hokeys"));
hash.delete("hokeys");
console.log(hash.get("hokeys"));

 

정리하며 

이 해시테이블을 만들며 해당 key에 맞는 노드를 반환하고 후속처리가 제일 귀찮았다. 그냥 이중연결리스트는 다루기 쉬웠지만 해당 key에 해당하는 노드가 없을때를 구분해야 하니 여간 짜증나는게 아니였다. ...ㅜ.ㅜ