[자료 구조와 알고리즘] 해시테이블(HashTable)

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

해시테이블(HashTable)

 

 

 

 

📍 해시테이블(HashTable)

👉🏻 해시, 맵,해시맵, 딕셔너리라고도 불림

 

👉🏻 해시 + 테이블 합쳐진 자료 구조

 

 

 

 

📍 해시테이블(HashTable) 예시

 

 

저작권은 롯데 자이언츠에게 잇읍니다 ^^*

👉🏻 야구 선수의 등 번호

👉🏻 기존 테이블은 메모리 낭비하는 경우가 있어(ex: 야구 선수 등번호의 경우 빈 숫자가 있음) 특정한 계산(해시 함수, ex: 10으로 나눠서 넣음)을 거쳐 메모리 절약을 하고자 함

👉🏻 키(Key)를 알고 있을 경우 조회/삽입/삭제를 O(1)의 성능으로 접근할 수 있게 됨

👉🏻 단, 이때 등 번호가 11번, 21번이 있다면 해시 함수를 거친 값은 모두 1이 됨

👉🏻 중복된 값이 있다면 같은 인덱스에 연결 리스트로 연결함

👉🏻 21번을 찾고자 할 때 해시 함수를 거쳐 1번 인덱스에 접근하고, 해당 데이터를 만날 때까지 조사함 - O(n)의 성능

 

-----> 해시 함수의 선정이 매우 중요해짐!

 

 

 

📍 해시테이블(HashTable) 장점

👉🏻 빠른 데이터 읽기, 삽입, 삭제 가능

 

 

 

📍 해시테이블(HashTable) 단점

👉🏻 메모리를 많이 차지함

👉🏻 좋은 해시 함수를 구현하는 것이 필수적

 

 

📍 해시테이블(HashTable) 구현

[ HashTable.mjs ]

import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class HashData {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}

class HashTable {
    constructor() {
        this.arr = [];
        for(let i = 0; i < 10; i++) {
            this.arr[i] = new DoublyLinkedList();
        }
    }
    // 원소마다 빈 이중 연결 리스트 생성 완료!

    hashFunction(number) {
        return number % 10;
    }

    set(key, value) {
        // 해시 함수를 거쳐 배열의 인덱스를 결정해 해당 인덱스의 연결 리스트에 삽입
        this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
    }

    get(key) {
        let currentNode = this.arr[this.hashFunction(key)].head;
        while(currentNode != null) { // 해당 인덱스를 모두 돌아라
            if(currentNode.data.key == key) {
                return currentNode.data.value;
            }
            currentNode = currentNode.next;
        }
        return null;
    }

    remove(key) {
        let list = this.arr[this.hashFunction(key)];
        let currentNode = list.head;
        let deletedIndex = 0;
        while(currentNode != null) {
            if(currentNode.data.key == key) {
                return list.deleteAt(deletedIndex);
            }
            currentNode = currentNode.next;
            deletedIndex++;
        }
        return null;
    }
}

export { HashTable };

[ test_hashtable.mjs ]

import { HashTable } from "./HashTable.mjs";

let hashTable = new HashTable();

hashTable.set(0, "안권수");
hashTable.set(1, "황성빈");
hashTable.set(2, "김민석");
hashTable.set(3, "신윤후");
hashTable.set(4, "이호연");
hashTable.set(5, "김민수");
hashTable.set(6, "한태양");
hashTable.set(7, "이학주");
hashTable.set(8, "전준우");
hashTable.set(9, "정훈");
hashTable.set(10, "이대호");
hashTable.set(11, "최동원");
hashTable.set(12, "김재유");
hashTable.set(13, "안치홍");
hashTable.set(14, "김세민");
hashTable.set(15, "김진욱");
hashTable.set(16, "한현희");
hashTable.set(17, "렉스");
hashTable.set(18, "최준용");
hashTable.set(19, "김강현");
hashTable.set(20, "");
hashTable.set(21, "박세웅");
hashTable.set(22, "구승민");
hashTable.set(23, "김도규");
hashTable.set(24, "김상수");
hashTable.set(25, "한동희");
hashTable.set(26, "진승현");
hashTable.set(27, "유강남");
hashTable.set(28, "반즈");
hashTable.set(29, "");
hashTable.set(30, "이민석");
hashTable.set(31, "신정락");
hashTable.set(32, "강태율");
hashTable.set(33, "최이준");
hashTable.set(34, "김원중");

console.log(`1: ${hashTable.get(1)}`);
hashTable.remove(1);
console.log(`1: ${hashTable.get(1)}`);
console.log(`34: ${hashTable.get(34)}`);

👉🏻 set: 데이터 삽입

👉🏻 get: 데이터 읽기

 

👉🏻 remove: 데이터 제거

 

 

-----> 내가 데이터를 set 한 후에 등 번호 "34번 김원중"을 찾고자 할 때, 해시 테이블에서는 내부적으로 34를 10으로 나눈 4번 인덱스를 찾아 "4번 이호연, 14번 김세민, 24번 김상수"를 거쳐 34와 일치하는 김원중을 찾아낸 것!