Data Structures & Algorithms with Javascript : Hashing

[이전 글] 2024.07.22 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Dictionaries

Hashing은 데이터 추가와 반환을 빠르게 하기 위한 데이터 저장 기술이다.
Hash table이라는 데이터 구조를 사용하는데, hash table은 데이터 추가, 삭제, 반환은 배무 빠르지만 
최소나 최대 값을 구하는 것과 같은 검색은 비효율적이다.

👩🏻‍💻 오늘은 Hash table이 무엇인지, 클래스 구현법, collision과 그 해결법에 대해 살펴보자.

Hashing 이란

Hash table 자료 구조는 array를 기반으로 만들어진다.

이 array는 0부터 정해진 크기의 엘리먼트로 구성된다. (필요에 따라 크기를 변경할 수 있다.)

각 데이터 엘리먼트는 dictionary 자료 구조에서 살펴봤던 것과 비슷하게 키(key)로 저장이 된다.

데이터를 hash table에 저장할 때, 0부터 hash table의 크기에 대응하는 키 값을 hash function으로 구해서 저장한다.

hash table의 크기는 얼마나 커야 할까? hash table의  array 크기는 반드시 prime number (소수)로 정한다.

 

 

이름과 전화번호를 토대로 한 hashing

 

이상적으로는 hash function을 통해 각 키에 하나의 array 엘리먼트가 대응되는 것이 좋다.

하지만 현실적으로는 키 값으로 할 수 있는 숫자는 유한한 반면에, 키의 개수는 무한하므로 가능한 한 키를 array에 고르게 분포하는 것이다. 고르게 분포를 하려고 해도 두 키가 같은 hash (hash function의 결과값)을 가질 수도 있다.

이 경우 "collision(충돌)"이라고 하는데, 충돌이 발생할 경우 어떻게 해결할 지에 대해 이후에 살펴보도록 하자.

🗂️ Hash Table 클래스

hash table 클래스에는 hash 값을 계산할 메소드, 값을 추가할 메소드, hash table로부터 값을 가져오는 메소드, 그리고 hash table의 데이터 분포를 보여줄 메소드를 필수로 포함할 수 있다.

Hash Function 정하기

hash function을 고르는 기준은 키의 데이터 타입에 따라 달라질 수 있다.

 

modular hashing

 

키가 정수일 경우, 가장 간단한 hash function은 array 크기의 키 modulo 값을 리턴하도록 할 수 있다.

다만 모든 키가 0으로 끝나고 array 크기가 10인 경우와 같은 상황에는 부적절할 수 있기 때문에 

array 크기를 정할 때 무조건 소수여야 한다. 랜덤의 정수값이 키일 경우 더 넓게 키를 분포할 수 있다.

 

대부분의 경우 키값이 string 타입이다. string 타입에 맞는 hash function을 구현할 때는 좀 더 신중해야 한다.

간단한 hash function으로 키의 각 문자의 ASCII 값을 더할 수 있다.

 

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

class HashTable{
	constructor(){
    	this.table = new Array(137);
        
    }
    
    // console.log 헬퍼 메서드
    print(item){
    	console.log(item);
    }
    
    // key가 string 타입일 경우 
    simpleHash(data){
    	let total = 0;
        for(let i=0; i< data.length; ++i){
        	total += data.charCodeAt(i);
        }
		this.print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }
    
    // hash table 값 보여주기
    showDistribution(){
    	let n = 0;
        for(let i = 0; i < this.table.length; ++i){
        	if(this.table[i] != undefined){
            	this.print(`${i} : ${this.table[i]}`);
            }
        }
    }

    // hash table에 데이터 추가
    put(data){
    	let position = this.simpleHash(data);
        this.table[position] = data;
    }
}

const names = ["David", "Jennifer", "Donnie", "Raymond",
"Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];;
const hashTable = new HashTable();
for(let i=0; i < names.length; ++i){
    hashTable.put(names[i]);
}
hashTable.showDistribution();

/**
Hash value: David -> 488
Hash value: Jennifer -> 817
Hash value: Donnie -> 605
Hash value: Raymond -> 730  // 충돌!!
Hash value: Cynthia -> 720
Hash value:: Mike -> 390
Hash value: Clayton -> 730 // 충돌!!
Hash value: Danny -> 506
Hash value: Jonathan -> 819


35 : Cynthia
45 : Clayton
57 : Donnie
77 : David
95 : Danny
116 : Mike
132 : Jennifer
134 : Jonathan
*/

 

하지만 위의 hash function의 경우 키 값들이 고르게 분배되어 있지 않다.

그리고 names array에 있던 이름들이 모두 할당되지 않는다는 것도 문제다.

Raymond와 Clayton의 각 문자를 ASCII 코드로 변환하여 숫자를 더한 값이 같아서 충돌이 발생한 것이다.

 

Horner's method

 

충돌을 방지하기 위해 hashFunction을 개선해보자.

먼저 hash table array의 크기는 100보다 큰 소수여야 한다. 100 이상의 소수 중에서 충돌이 발생하지 않는 제일 작은 숫자는 137이라는 걸 여러 실험을 통해 발견했다. Horner’s method이라는 알고리즘을 활용하면 hash 값 계산을 개선할 수 있다.

ASCII 값으로 변환한 값들을 더하는 과정에 상수인 소수를 곱해서 더해주는 방식으로 구현할 수 있다.

class HashTable {
    constructor() {
        this.table = new Array(137);
    }
    
    // console.log 헬퍼 메서드
    print(item) {
        console.log(item);
    }
    
    // key가 string 타입일 경우 
    simpleHash(data) {
        let total = 0;
        for (let i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        this.print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    // Horner's method을 활용해 개선한 hashing function
    betterHash(string) {
        const H = 37; // base로 쓰일 소수
        let total = 0;
        for (let i = 0; i < string.length; ++i) {
            total = H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        return parseInt(total);
    }
    
    // hash table 값 보여주기
    showDistribution() {
        let n = 0;
        for (let i = 0; i < this.table.length; ++i) {
            if (this.table[i] != undefined) {
                this.print(`${i} : ${this.table[i]}`);
            }
        }
    }

    // hash table에 데이터 추가
    put(data) {
        // let position = this.simpleHash(data); 
        let position = this.betterHash(data);
        this.table[position] = data;
    }
}

const names = ["David", "Jennifer", "Donnie", "Raymond",
"Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
const hashTable = new HashTable();
for (let i = 0; i < names.length; ++i) {
    hashTable.put(names[i]);
}
hashTable.showDistribution();

/**
10 : Mike
12 : Danny
72 : David
73 : Jonathan
88 : Clayton
92 : Raymond
104 : Donnie
109 : Jennifer
133 : Cynthia
*/

 

Hashing Integer keys

 

지금까지는 string 타입을 키로 갖는 hash function을 다뤄봤다.

이번에는 정수 타입을 hash 키로 갖는 예시를 살펴보자.

 

다음과 같이 학생 ID와 성적을 위에서 살펴봤던 betterHash()와 simpleHash()로 비교한 hash table을 만들어보자.

// 랜덤 성적
function getRandomInt (min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 학생 데이터
function generateStudentData(arr){
	for(let i = 0; i < arr.length ; ++i){
    	let num = "";
        // 학생 점수 생성
        for(let j = 1; j <= 9; ++j){
        	num += Math.floor(Math.random() * 10);
        }
        num += getRandomInt(50, 100);
        // 학생 ID에 점수 할당
        arr[i] = num;
    }
}

class HashTable {
    constructor() {
        this.table = new Array(137);
    }
    
    // console.log 헬퍼 메서드
    print(item) {
        console.log(item);
    }
    
    // key가 string 타입일 경우 
    simpleHash(data) {
        let total = 0;
        for (let i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        this.print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    // Horner's method을 활용해 개선한 hashing function
    betterHash(string) {
        const H = 37; // base로 쓰일 소수
        let total = 0;
        for (let i = 0; i < string.length; ++i) {
            total = H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        return parseInt(total);
    }

    // hash table 값 보여주기
    showDistribution() {
        let n = 0;
        for (let i = 0; i < this.table.length; ++i) {
            if (this.table[i] != undefined) {
                this.print(`${i} : ${this.table[i]}`);
            }
        }
    }

    // hash table에 데이터 추가
    // put(data) {
    //     // let position = this.simpleHash(data); 
    //     let position = this.betterHash(data);
    //     this.table[position] = data;
    // }

    // 두 hash function 비교를 위해 type 에 따라 분기
	put(data,type="betterHash"){
		let position = type === "betterHash"?  this.betterHash(data): this.simpleHash(data);
        this.table[position] = data;
	}
}

let numStudents = 10;
let arrSize = 97;
let idLength = 9;
let students = new Array(numStudents);
const print = (item) =>console.log(item);
generateStudentData(students);

for(let i = 0;i<students.length; ++i){
    print(students[i].substring(0,8) + " " + students[i].substring(9));
} 

/**
//학생ID  성적

03393080 94
55511088 81
80924513 89
16529442 54
71582662 81
02959617 86
75489309 76
04226751 77
22656462 76
99380949 53
*/


print("\n\nData distribution: \n");

let betterHashTable = new HashTable();
let simpleHashTable = new HashTable();
for (let i = 0; i < students.length; ++i) {
   betterHashTable.put(students[i],"betterHash");
   simpleHashTable.put(students[i],"simpleHash");
    
}

print("\nbetter hash function:\n");
betterHashTable.showDistribution();
print("\nsimple hash function:\n");
simpleHashTable.showDistribution();

/**
Data distribution: 

Hash value: 03393080594 -> 572
Hash value: 55511088981 -> 579
Hash value: 80924513989 -> 586
Hash value: 16529442154 -> 571
Hash value: 71582662781 -> 581
Hash value: 02959617586 -> 586
Hash value: 75489309776 -> 593
Hash value: 04226751777 -> 576
Hash value: 22656462476 -> 578
Hash value: 99380949253 -> 589

better hash function:

0 : 03393080594
10 : 55511088981
13 : 80924513989
14 : 02959617586
15 : 04226751777
46 : 71582662781
60 : 75489309776
82 : 99380949253
108 : 22656462476
131 : 16529442154

simple hash function:

23 : 16529442154
24 : 03393080594
28 : 04226751777
30 : 22656462476
31 : 55511088981
33 : 71582662781
38 : 02959617586
41 : 99380949253
45 : 75489309776
*/

 

simple hash function을 살펴보면 모든 데이터가 할당되지 않았다. 10명의 학생 점수가 있지만 collision 때문에 9명의 점수만 할당되었다. 뿐만 아니라 키의 분포가 밀집되어 있다는 걸 확인할 수 있다.

반면 better hash function은 모든 데이터가 할당되어 있고 키가 고르게 분배되어 있다는 걸 알 수 있다.

따라서 타입과 관계없이 better hash function을 사용하는 것이 더 좋다.

Hash table에 데이터 저장 및 회수

hash function 중 더 좋은 hash 값을 구하는 방식에 대해 살펴봤다.

betterhash function을 활용해 데이터를 저장하는 put 과 데이터를 회수하는 get 메서드를 구현해보자.

class HashTable {
    constructor() {
        this.table = new Array(137);
    }
    
    // console.log 헬퍼 메서드
    print(item) {
        console.log(item);
    }
    
    // key가 string 타입일 경우 
    simpleHash(data) {
        let total = 0;
        for (let i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        this.print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    // Horner's method을 활용해 개선한 hashing function
    betterHash(string) {
        const H = 37; // base로 쓰일 소수
        let total = 0;
        for (let i = 0; i < string.length; ++i) {
            total = H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        return parseInt(total);
    }
    
    // hash table 값 보여주기
    showDistribution() {
        let n = 0;
        for (let i = 0; i < this.table.length; ++i) {
            if (this.table[i] != undefined) {
                this.print(`${i} : ${this.table[i]}`);
            }
        }
    }
    
	///////////////////////////////// 💖추가 /////////////////////////////////
    
    // hash table에 데이터 추가
    put(data) {
        // let position = this.simpleHash(data); 
        let position = this.betterHash(data);
        this.table[position] = data;
    }

    // hash table에서 데이터 가져오기
    get(key) {
        let position = this.betterHash(key);
        return this.table[position];
    }
    
    ///////////////////////////////// 💖추가 /////////////////////////////////  
}
const print = (item) => console.log(item);
const names = ["David", "Jennifer", "Donnie", "Raymond",
"Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];

const hashTable = new HashTable();

for (let i = 0; i < names.length; ++i) {
    hashTable.put(names[i]);
}
hashTable.showDistribution();

print("Retrieving values:");

for (let i = 0; i < names.length; ++i) {
    print(names[i] + " -> " + hashTable.get(names[i]));
}

/**
10 : Mike
12 : Danny
72 : David
73 : Jonathan
88 : Clayton
92 : Raymond
104 : Donnie
109 : Jennifer
133 : Cynthia
Retrieving values:
David -> David
Jennifer -> Jennifer
Donnie -> Donnie
Raymond -> Raymond
Cynthia -> Cynthia
Mike -> Mike
Clayton -> Clayton
Danny -> Danny
Jonathan -> Jonathan
*/

Collision 해결하기

hash function이 두 개 이상의 값에 같은 키를 생성하면 collision (충돌)이 발생한다.

충돌을 해결하기 위한 방법인 "separate chaining" 과 "linear probing"에 대해 살펴보자. 

 

Separate Chaining

hash table의 각 array 엘리먼트를 array와 같은 다른 데이터 구조를 저장하고,

충돌이 발생한 키의 array에 각 데이터를 저장하는 방식으로 2차원 array 구조로 만들어 충돌을 해결할 수 있다. 

 

separate chaining

 

 

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!! 원본 문서의 배열이 아닌 linked list로 대체 구현해봤습니다!!

이전 LinkedList를 내부 데이터 구조로 활용한 separate chaining에 대해 살펴보자.

class LinkedList {
    constructor() {
        this.head = null;
    }

    append(data) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    toString() {
        let current = this.head;
        let string = '';
        while (current !== null) {
            string += JSON.stringify(current.data) + ' ';
            current = current.next;
        }
        return string.trim();
    }
}

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

 

class HashTable {
    constructor() {
        this.table = new Array(137);
        for (let i = 0; i < this.table.length; ++i) {
            this.table[i] = new LinkedList();
        }
    }
    
    // console.log 헬퍼 메서드
    print(item) {
        console.log(item);
    }
    
    // key가 string 타입일 경우 
    simpleHash(data) {
        let total = 0;
        for (let i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        this.print("Hash value: " + data + " -> " + total);
        return total % this.table.length;
    }

    // Horner's method을 활용해 개선한 hashing function
    betterHash(string) {
        const H = 37; // A prime number used as the base
        let total = 0;
        for (let i = 0; i < string.length; ++i) {
            total = H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        return parseInt(total);
    }
    
    // hash table 값 보여주기
    showDistribution() {
        for (let i = 0; i < this.table.length; ++i) {
            if (this.table[i].head !== null) {
                this.print(`${i} : ${this.table[i].toString()}`);
            }
        }
    }

    // hash table에 데이터 추가
    put(key, value) {
        let position = this.betterHash(key);
        this.table[position].append({key, value});
    }

    // hash table에서 데이터 가져오기
    get(key) {
        let position = this.betterHash(key);
        let current = this.table[position].head;
        while (current !== null) {
            if (current.data.key === key) {
                return current.data.value;
            }
            current = current.next;
        }
        return undefined;
    }
}

const print = item => console.log(item);

const names = ["David", "Jennifer", "Donnie", "Raymond",
"Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
const hashTable = new HashTable();
for (let i = 0; i < names.length; ++i) {
    hashTable.put(names[i], `Value for ${names[i]}`);
}
hashTable.showDistribution();


print("\nRetrieving values:");
for (let i = 0; i < names.length; ++i) {
    print(names[i] + " -> " + hashTable.get(names[i]));
}

/**
10 : {"key":"Mike","value":"Value for Mike"}
12 : {"key":"Danny","value":"Value for Danny"}
72 : {"key":"David","value":"Value for David"}
73 : {"key":"Jonathan","value":"Value for Jonathan"}
88 : {"key":"Clayton","value":"Value for Clayton"}
92 : {"key":"Raymond","value":"Value for Raymond"}
104 : {"key":"Donnie","value":"Value for Donnie"}
109 : {"key":"Jennifer","value":"Value for Jennifer"}
133 : {"key":"Cynthia","value":"Value for Cynthia"}

Retrieving values:
David -> Value for David
Jennifer -> Value for Jennifer
Donnie -> Value for Donnie
Raymond -> Value for Raymond
Cynthia -> Value for Cynthia
Mike -> Value for Mike
Clayton -> Value for Clayton
Danny -> Value for Danny
Jonathan -> Value for Jonathan
*/

 

Linear Probing

 

linear probing은 open-addressing hashing의 예시 중 하나다.

충돌이 발생하면 프로그램은 hash table의 다음 요소가 비어있는 지 확인하고 , 비어 있으면 키를 할당한다.

이 방식이 동작하려면 빈 공간이 충분히 있을 만큼 hash table이 커야 한다.

 

그럼 separate chaining과 linear probing 중 어떤 걸 사용해야 할까?

array 크기가 저장할 엘리먼트의 개수 반 이하일 경우 separate chaining을 사용하고,

array 크기가 저장할 크기의 엘리먼트의 두 배 이상일 수 있는 경우에는 linear probing을 사용하는 것이 좋다.

 

linear probing 클래스를 구현해보자.

class HashTable {
    constructor() {
        this.table = new Array(137);
        this.values = [];
    }
    
    // console.log 헬퍼 메서드
    print(item) {
        console.log(item);
    }
    
    // Horner's method을 활용해 개선한 hashing function
    betterHash(string) {
        const H = 37; // A prime number used as the base
        let total = 0;
        for (let i = 0; i < string.length; ++i) {
            total = H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length - 1;
        }
        return parseInt(total);
    }
    
    // hash table 값 보여주기
    showDistribution() {
        for (let i = 0; i < this.table.length; ++i) {
            if (this.table[i] != null) {
                this.print(`${i} : ${this.table[i]}`);
            }
        }
    }

    // hash table에 데이터 추가
    put(key, data) {
        let position = this.betterHash(key);
        if(this.table[position] == undefined){
			this.table[position] = key;
            this.values[position] = data;
        } else {
        	while(this.table[position] != undefined){
            	position++;
            }
            this.table[position] = key;
            this.values[position] = data;
        }
    }

    // hash table의 hash 위치에서 키가 일치하면 위치에 할당하고, 
    // 아니라면 할당되지 않은 위치(undefined)가 나올 때까지 루프를 돌다가 할당을 한다.
    get(key) {
        let hash = -1;
        hash = this.betterHash(key); 
        if (hash > -1) {
        	for (let i = hash; this.table[hash] != undefined; i++) { 
            	if (this.table[hash] == key) {
        			return this.values[hash]; 
                }
    		} 
        }
        return undefined; 
        }
}


const print = item => console.log(item);

const names = ["David", "Jennifer", "Donnie", "Raymond",
"Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
const hashTable = new HashTable();
for (let i = 0; i < names.length; ++i) {
    hashTable.put(names[i], `Value for ${names[i]}`);
}
hashTable.showDistribution();


print("\nRetrieving values:");
for (let i = 0; i < names.length; ++i) {
    print(names[i] + " -> " + hashTable.get(names[i]));
}

/**
10 : Mike
12 : Danny
72 : David
73 : Jonathan
88 : Clayton
92 : Raymond
104 : Donnie
109 : Jennifer
133 : Cynthia
 
Retrieving values:
David -> Value for David
Jennifer -> Value for Jennifer
Donnie -> Value for Donnie
Raymond -> Value for Raymond
Cynthia -> Value for Cynthia
Mike -> Value for Mike
Clayton -> Value for Clayton
Danny -> Value for Danny
Jonathan -> Value for Jonathan
*/

 

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9