04. 해쉬 테이블 (Hash Table)

1. 해쉬테이블 구조

- 키(key)에 데이터(value)를 저장하는 데이터 구조

- key를 통해 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라짐

- 보통 배열로 미리 Hash Table 사이즈 만큼 생성 후 사용

- 데이터 저장/읽기 속도가 빨라 검색 속도가 빠르다는 장점이 있음

- 일반적으로 저장공간이 더 필요하며 여러 키에 해당하는 주소가 동일 할 경우 충돌을 해결하기 위해 별도 자료구조가 필요한 단점이 있음

키 (key)	- 고유한 값으로 해시 함수의 input - 다양한 길이의 값이 될 수 있으며 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해야 하기 때문에 해시 함수로 값을 바꾸어 저장함
해쉬 함수 (Hash Function)	- 키(key)를 해시(Hash)로 바꿔주는 역할을 함 - 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줌
해쉬 (Hash)	- 키를 고정 길이로 변환 한 해쉬 함수의 결과물 - 저장소(bucket, slot)에서 값(value)과 매칭되어 저장됨
값 (value)	- 저장소(bucket, slot)에 최종적으로 저장되는 값 - 키와 매칭되어 저장, 삭제, 검색, 접근이 가능함

출처: 위키백과 - 해쉬테이블

2. 해쉬 테이블 구현 - 해쉬 충돌(Hash Collision) 고려 안함

 

class ValuePair {
    constructor (key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[${this.key}:${this.value}]`;
    }
}


class HashTable {
    constructor () {
        this.table = {};
    }

    toString(value) {
        if (value === null) {
            return 'NULL';
        } else if (value === undefined) {
            return 'UNDEFINED';
        } else if (typeof value === 'string' || value instanceof string) {
            return `${value}`;
        }
        return value.toString();
    }

    // hash function : key to hash
    hashFunction(key) {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this.toString(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }

    hashCode(key) {
        return this.hashFunction(key);
    }

    // 1. put : Add new item to the hash table
    put(key, value) {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            this.table[position] = new ValuePair(key, value);
            return true;
        }
        return false;
    }

    // 2. remove : Remove the value from the hash table using the key
    remove(key) {
        const hash = this.hashCode(key);
        const valuePair = this.table[hash];
        if (valuePair != null) {
            delete this.table[hash];
            return true;
        }
        return false;
    }

    // 3. get : Return a specific value searched by the key
    get(key) {
        const valuePair = this.table[this.hashCode(key)];
        return valuePair == null? undefined : valuePair.value;
    }

}

const hash = new HashTable();
hash.put('yk', 'yk@gmail.com');
hash.put('js', 'js@gmail.com');
hash.put('ksj', 'ksj@gmail.com');

console.log(`hash: ${hash.hashCode('yk')} value: ${hash.get('yk')}`);
console.log(`hash: ${hash.hashCode('js')} value: ${hash.get('js')}`);
console.log(`hash: ${hash.hashCode('ksj')} value: ${hash.get('ksj')}`);

 

3. 해쉬 충돌 (Hash Collision)

- hash function으로 hash를 산출하는 과정에서 서로 다른 key가 값은 hash로 변경되는 문제

- key와 value가 1:1로 매칭 되어야 한다는 규칙을 위반한 것으로 문제가 됨

 

4. 해쉬 충돌 해결

1) Separate Chaining

- 충돌이 일어나면 Linked List 자료구조를 사용하여 Linked List로 데이터를 추가로 뒤에 연결시켜 저장

class HashTableSeparateChaining {

    constructor() {
        this.table = {};
    }

    toString(value) {
        if (value === null) {
            return 'NULL';
        } else if (value === undefined) {
            return 'UNDEFINED';
        } else if (typeof value === 'string' || value instanceof string) {
            return `${value}`;
        }
        return value.toString();
    }

    hashFunction(key) {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this.toString(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }

    hashCode(key) {
        return this.hashFunction(key);
    }

    put(key, value) {

        if (key != null && value != null) {
            const position = this.hashCode(key);
            if (this.table[position] == null) {
                this.table[position] = new LinkedList();
            }
            this.table[position].push(new ValuePair(key, value));
            return true;
        }
        return false;
    }

    get(key) {
        const position = this.hashCode(key);
        const linkedList = this.table[position];
        if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead();
            while (current != null) {
                if (current.element.key === key) {
                    return current.element.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }

    remove(key) {
        const position = this.hashCode(key);
        const linkedList = this.table[position];
        if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead();
            while (current != null) {
                if (current.element.key === key) {
                    linkedList.remove(current.element);
                    if (linkedList.isEmpty()) {
                        delete this.table[position];
                    }
                    return true;
                }
                current = current.next;
            }
        }
        return false;
    }

}

2) Linear Probing

- Close Hashing 기법 중 하나로 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결 하는 방법

- 충돌이 일어나면 해당 Hash address 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 (저장 활용도 UP)

 

5. 시간 복잡도

- 일반적인 경우 (Collision이 없는 경우) O(1)

- 최악의 경우 (Collision이 모두 발생하는 경우) O(n)

- 해쉬 테이블의 경우 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)이라고 할 수 있음 (Hash function의 중요함...)

 

 

소스참고: Learning JavaScript Data Structures and Algorithms