해시 테이블

🤓오늘의 공부 주제: 해시 테이블🤓

해시 테이블이란?
해시 테이블은 해시, 맵, 해시맵, 딕셔너리등 다양한 이름으로 불리는 자료 구조로 해시와 테이블이 합쳐진 구조를 가지고 있다.

테이블 = 표. 프로그래밍에서는 배열의 인덱스와 데이터의 형태로 저장한다. 메모리를 절약하기 위해서 인덱스에 해시 함수를 활용.

해시 함수로 인덱스를 새로 만들었기 떄문에 해시 테이블. 인덱스가 key가 되고 데이터가 value가 된다. key만 알면 value에 o(1)의 성능으로 읽기가 가능. 삽입, 수정, 삭제 역시 o(1)의 성능을 가짐.

충돌이 발생하는 문제가 있음. 충돌을 해결하기 위해 인덱스를 연결리스트로 구성해 데이터를 연결함. 여러 데이터를 연결리스트로 하나의 key값에 저장 가능. 이때는 o(n)의 성능.

따라서 해시 함수의 선정이 중요함. 골고루 분배해줄 함수를 사용해야함.

💡요약💡
빠른 데이터 읽기, 삽입, 삭제이나 메모리를 많이 차지함. 좋은 해시 함수가 필요함.

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 };