[알고리즘] Hash (해쉬)이란

해쉬란?

해쉬는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말한다. 다른 말로는 해시 값이라고한다.

 

 

사용하는경우 

배열의 인덱스위치, 위치, 데이터 값을 저장하거나 검색할때 활용된다.

 

특징 

키(KEY)에 데이터(VALUE)를 매핑할 수 있는 데이터 구조

해쉬 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산

 

 

 

 

 

장단점

장점

데이터 저장/ 읽기 속도가 빠름 (검색속도가 빠름)

해시는 키에 대한 데이터가 있는지 확인이 쉬움

 

단점

일반적으로 저장곤간이 많이 필요

여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요

 

 

 

 

 

 

 

코드

class hashTable{
    constructor(size){
        this.storage = [];
        if(size){
            this.size = size;
        }
        else{
            this.size = 100;
        }
    }
    insert = (key,value) => {               
        let index = this.hash(key);
        
        if(this.storage[index] === undefined){
            this.storage[index] = [[key, value]];
        }
        else{
            let storageFlag = false;
            for(let i = 0; i < this.storage[index].length; i++){
                if(this.storage[index][i][0] === key){
                    this.storage[index][i][1] = value;
                    storageFlag = true;
                }
            }
            if(!storageFlag){
                this.storage[index].push([key,value]);
            }
        }
    }
    delete = (key) => {
        let index = this.hash(key);
        if(this.storage[index] === undefined){
            return false;
        }
        else if(this.storage[index].length === 1 && this.storage[index][0][0] === key){
            this.storage.splice(index,1);
            return true;
        }
        else{
            for(let i = 0; i < this.storage[index].length; i++){
                if(this.storage[index][i][0] === key){
                    this.storage[index].splice(i,1)
                    return true;
                }
            }
            return false;
        }
    }
    search = (key) => {
        let index = this.hash(key);
        if(this.storage[index] === undefined){
            return false;
        }
        else if(this.storage[index].length === 1 && this.storage[index][0][0] === key){
            return this.storage[index][0][1];
        }
        else{
            for(let i = 0; i < this.storage[index].length; i++){
                if(this.storage[index][i][0] === key){
                    return this.storage[index][i][1];
                }
            }
            return false;
        } 
    }

    hash = (key) => {
        let hash = 0;
        for(let i = 0; i < key.length; i++){
            hash += key.charCodeAt(i);
        }
        return hash % this.size;
    }

    getTable(){
        return this.storage;
    }

}

let data = new hashTable(100);
data.insert(1,5);
data.insert('asd', 12);
data.insert(213,14);
data.insert('a', 'b');
data.insert('213', '12');
console.log(data.search(1));
console.log(data.search(213));
data.delete(1);
console.log(data.search(1));
data.insert(1,10)
data.delete('a');
console.log(data.search(1));
console.log(data.getTable())