체이닝 해시테이블 (ChainingHashTable) 구현해보기

Lainlnya·2022년 10월 4일

알고리즘

목록 보기

14/25

오늘의 TMI

모듈 연결을 할 때에는 연결하기를 원하는 클래스의 가장 아래쪽에 export { LinkedList }; 처럼 ‘LinkedList’로 export 하겠다는 것을 정의해줘야 하고, 사용하는 쪽에서는 import { LinkedList } from ‘./linked_list.mjs’; 처럼 처리해주면 사용이 가능하다.
그리고 파일 이름은 import하는 쪽과 export하는 쪽 둘 다 mjs로 저장해줄 것!

실수 LOG
처음 LinkedList를 만들 때 this.head에 node를 저장해야 하는데, node.data를 저장해버리는 바람에 체이닝 해시테이블을 만드는데 계속해서 오류가 발생했다. 왜 그런 실수를 했는지 아직까지 알 수는 없지만, 처음에 잘못 만들게 되면 다른 모듈에서 import 했을 때 문제가 발생할 수 있기 때문에 항상 조심해야겠다는 생각이 들었다.

체이닝 해시테이블

별도의 자료구조인 연결 리스트를 병합 사용하여 Hash 충돌을 해결한 해시테이블 기반 자료구조

하나의 주소 공간은 그대로 사용하고, next element를 가리키는 pointer를 이용해서 충돌을 해결한다.

구현 메서드

객체 초기화 / 크기 반환 : ChainingHashTable.clear(), ChainingHashTable.size()
전체 데이터 반환, 전체 데이터 출력: ChainingHashTable.getBuffer(), ChainingHashTable.print()
추가 / 삭제 / 반환: ChainingHashTable.put(), ChainingHashTable.remove(), ChainingHashTable.get()

hashCode(), size(), clear() 메서드의 경우 일반 해시테이블과 동일하다.

1. 데이터 삽입 (put(key, value))

index의 hashCode를 구한다.
this.table[index]가 undefined일 경우, 새로운 LinkedList 객체를 만든다.
그 객체에 append 메서드를 이용해서 새로운 데이터를 삽입한다.

put (key,value) {
        let index = this.hashCode(key);

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

2. 데이터 반환 (get(key))

index의 hashCode를 구한뒤, this.table[index]가 undefined가 아니거나, 비어있지 않을 경우

current에 this.table[index].head를 저장한다.
current.data.key가 구하고자 하는 key와 같다면 current.data.value를 반환한다.
원하는 key와 다르다면, current = current.next로 바꾼다.

get (key) {
        let index = this.hashCode(key);

        if (this.table[index] !== undefined && !this.table[index].isEmpty()) {
            let current = this.table[index].head;
            while (current != null) {
                if (current.data.key === key) {
                    return current.data.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }

3. 데이터 제거 (remove(key))

index의 hashCode를 구한 뒤, this.table[index]가 undefined가 아니면 current에 this.table[index].head를 저장한다.
current.data.key가 구하고자 하는 key와 같다면 current.data를 remove한다.
남아있는 this.table[index]가 비어있을 경우, LinkedList도 함께 없앤다.
해당하지 않을 경우 current = current.next를 하며 데이터를 찾는다.

remove (key) {
        let index = this.hashCode(key);
        let element = undefined;

        if (this.table[index] !== undefined) {
            let current = this.table[index].head;

            while (current !== null) {
                if (current.data.key === key) {
                    element = current.data;
                    this.table[index].remove(current.data);

                    if (this.table[index].isEmpty()) {
                        delete this.table[index];
                    }
                }
                current = current.next;
            }
        }

        this.length--;
        return element;
    };

4. 데이터 배열로 반환 (getBuffer())

remove나 get처럼 current = this.table[index].head를 저장해 둔 다음, this.table[index]가 존재한다면 array배열에 넣는다.

getBuffer () {
        let array = [];

        for (let i = 0; i < this.table.length; i++) {
            if (this.table[i]) {
                let current = this.table[i].head;

                while (current !== null) {
                    array.push(current.data);
                    current = current.next;
                }
            }
        }
        return array;
    }

5. 데이터 출력 (print())

getBuffer()와 비슷한 형식이지만, 데이터를 console.log로 출력한다는 것만 다르다.

print () {
        for (let i = 0; i < this.table.length; i++) {
            if (this.table[i]) {
                let current = this.table[i].head;
                process.stdout.write(`#${i} `);
                while (current !== null) {
                    process.stdout.write(` -> ${current.data.key} : ${current.data.value}`);
                    current = current.next;
                }
                console.log("");
            }
        }
    }