섹션 25 해시 테이블

이유정·2022년 11월 9일
0

알고리즘 & 자료구조 마스터

목록 보기
2/11

해시테이블이 뭔지?

해시테이블은 키-값 쌍을 저장하는데 사용된다. (배열처럼)
배열과 달리 해시테이블의 키는 순서를 가지지 않는다.
해시테이블이 멋진 이유는 '값을 찾거나', '새로운 값을 추가하거나', '값을 제거하는데' 빠르다!!!!

거의 모든 언어들은 해시 테이블 종류의 구조를 가지고 있다. 왜냐하면 빠르기 때문이다! 또, 데이터 그 자체가 해시테이블 방법에 따라 저장하는 것이 편한 경우가 많다. 연속적인 흐름이 있는 데이터라면 배열을 사용하면 된다. 순서가 있고, 배열을 사용해서 장소를 지정하는 것이 말이 되는 숫자값을 가진 데이터라면! 그렇지만 많은 경우 데이터는 그런 패턴에 맞지 않는다! 그런 경우 해시 맵이나 해시테이블을 사용한다.

자바스크립트에서 해시 테이블은 Objects나 Maps에 이용된다.
만약 이것들이 사라진다면?
우리는 그래도 키-값 데이터 저장법이 필요하니, 직접 만들어야 한다.

색깔을 원할 때
colors["red"]가 더 좋은 방법이다 colors[2]보다!!

하지만 컴퓨터는 이런걸 못한다. 또 하지만 구원의 손길인 해시 테이블이 있다!

거의 모든 언어에는 내장 해시 테이블 코드가 있다.

해시테이블을 내가 직접 작성해보자

해시테이블을 실행하기 위해서 우린, 배열을 사용할 것이다.
스트링이나 사진, pdf, 영상 등을 입력하면 숫자를 캩어야 한다.
pink 를 해시 함수에 입력하면 0이라는 숫자를 뱉는다.
거기엔 ["pink", "#ff69bs"]가 있다.
cyan을 해시 함수에 입력하면 3이라는 숫자를 뱉는다.
거기엔 ["cyan", "#00ffff"]가 있다.

해시 테이블에서 어떻게 충돌이 일어나는지?
충돌을 해결하는 방법을 배우자
separate chaining (개별 체이닝)
linear probing (선형 조사법)

해시 함수 소개

해시 알고리즘의 정의

해시 함수는 pink나 cyan 같은 string으로 된 키를 배열에서 사용되는 유효한 인덱스, 즉 작은 숫자로 바꿔주는데 사용된다.
해시 함수는 전세계 인터넷과 개인 정보 보호, 일반 계산 업무 등에서 사용이 된다.
해시 함수는 정보 보호, 저장, 사이트 로그인 인증, 암호 기술을 사용하는 암호화폐에서도 사용된다.
해시 함수의 종류는 많은데, 그 중 하나는 암호화 해시 함수라고 불린다. (암호 기술 중에 정말 어려운 계열이다.)
우리가 이야기 할건 기본적인 해시 함수다.
함수의 정의는?

  • 수천자든 수백만 자든 임의의 크기를 가지는 데이터를 입력하면 정해진 크기의 데이터를 출력하는 것
    자바스크립트 같은 언어는 내장 해시 함수를 노출하지 않는다.

  1. 입력값이 무엇인지와 관계없이 비슷한 크기로 정리된 데이터다.

  2. 대부분의 해시 함수에서는 반대로 작업을 할 수 없다.(단방향 함수)

    어떤 것이 좋은 해시 알고리즘을 만드는가?

  3. 빨라야 한다. (해시 테이블에 무언가를 삽입하기 위해서는 해시 작업이 필요하다)
    (무언가를 찾아내거나, 바꾸거나, 제거하기 위해 접근 할 때마다 해시 함수를 다시 실행해야 한다.)
    예) pink의 해시가 무엇인지 물어보고, 그 숫자를 가져다가 배열에서 그 숫자를 찾는 것
    => 여러 번 반복되는 루프가 있어서는 안된다. 상수값의 시간을 가져야한다.

  4. 일관된 방식으로 분배를 해서 다른 것들과 겹치지 않게 한다.

  5. 좋은 해시 함수는 결정론적이다. (특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다. )

    첫번째 해시 함수 작성하기

    hash("pink", 100)
// 만약 100개의 요소가 들어가는 배열에 해시 테이블을 저장한다면,
//pink를 0에서 99 사이의 숫자로 배정해줄 것. 해당 배열에서 유효한 인덱스 값의 범위다.
hash("pink", 9)
// 이 함수는 0에서 8사이의 숫자를 돌려줘야 한다. 
hash("pink")
// 숫자는 생각않고, string 의 배열 길이 값에 따라 넣어준다고 하면 한 곳에 완전 많이 모이겠지
"a".charCodeAt(0)
// 각 글자는 UTF 16 글자 코드가 있다. 모든 글자는 각각 해당하는 숫자값을 가진다. 
//97 
"hi".charCodeAt(0)
// 104 //h에 해당하는 값이 나옴 
"hi".charCodeAt(1)
// 105 // i에 해당하는 값이 나옴

"a".charCodeAt(0)-96
//1 // 이렇게 하면 알파멧 1부터 26까지 구할 수 있음
"d".charCodeAt(0)-96
//4
"z".charCodeAt(0)-96
//26 


```js
let total = 0; 
total += "hello".charCodeAt(0)-96
total += "hello".charCodeAt(1)-96
total += "hello".charCodeAt(2)-96
total += "hello".charCodeAt(3)-96
total += "hello".charCodeAt(4)-96
total // 52 

hash("hello", 11)
//예를 들어 우리의 배열의 길이가 11이라고 하자. 
// 그러면 유효한 인덱스가 필요한데 52는 유효하지 않아

//모듈로 연산을 사용하는 방법을 !!! 
//11로 % 이 연산을 하면 0과 10사이의 유효한 배열 인덱스가 나온다. 
total%11
//8
1090089898394935%11
//9 

// 해시 함수 자체가 작동하는 방식의 세부적인 것은 중요하지 않다. 
function hash(key, arrayLen){
	let total = 0; 
    for(let char of key){
    	let value = char.charCodeAt(0)-96
        total = (total + value) % arrayLen 
    }
  return total; 
}

hash("pink", 10) //0
hash("oranged", 10) //7
hasg("cyan", 10) //3

problem

  1. 위 함수는 잘 작동하지만 string에 대해서만 해시 처리를 한다.
    예를 들어 숫자나 불린 값이나 배열 같은 것을 넣으면 제대로 작동하지 않을 것이다.
    스트링에 대한 메소드니까 !
  2. 상수 값의 시간을 가지지 않는다.
    스트링의 길이나 데이터의 크기에 따라 연산 시간이 달라진다.
  3. 무작위성이 떨어진다. 생각보다 뭉친다.

해시 함수 성능 향상시키기

위 문제를 조금은 해결해보자. 

function hash(key, arrayLen){
	let total = 0; 
  for(let i=0; i < key.length; i++){
  	let char = key[i];
    let value = char.charCodeAt(0) - 96 
    total = (total + value) % arrayLen; 
  }
  return total; 
}

그냥 다른 테이블 길이(소수가 아닌 길이를 리스트에 사용)를 사용하는 것으로, 그냥 1이 더 작은 소수를 사용하는 것만으로 충돌의 숫자를 아주 많이 낮출 수 있다. 그러니까 우리가 값들을 저장하는 해시 테이블은 소수 값의 길이를 가지는 것이 항상 유리하다. 테이블을 소수로 바꾸는 것에서 어떻게 이런 변화가 나타나는지에 대한 많은 내용들을 다 알지는 못해도 길이 값을 소수로 사용해야겠죠? 

function hash(key, arrayLen){
	let total = 0; 
    let WEIRD_PRIME = 31 // 소수값을 가지는 배열 길이 // 충돌 횟수를 줄이고 데이터가 더 퍼지고 무작위성을 갖도록 한다. 
  for(let i=0; i < Math.min(key.length,100); i++){ // key가 100보다 클 때 100만큼만 루프 돌게 할 것임// 원칙적으로 최대값을 정함으로써 속도를 높임 // 아주 큰 데이터를 입력하면 맨 앞의 100글자만 보게 된다. 
  	let char = key[i];
    let value = char.charCodeAt(0) - 96 
    total = (total * WEIRD_PRIME + value) % arrayLen; 
  }
  return total; 
}

hash("hello", 13) 여기 옆에 숫자를 소수로 사용하는 것임

--지금까지 스트링에만 사용할 수 있는 기본적인 해시 함수를 만들어봤다. 코드를 고쳐봤는데 이제 거의 상수값의 시간을 가진다.

충돌 처리

충돌을 해결하는 방법에 대해 배워보자
해시 함수를 사용할 때 데이터가 아주 많이 있는 경우라면 충돌이 어느정도 일어날 가능성이 높다. 데이터 저장 공간이 크고, 해시 함수가 아주 좋은 것일지라도 여전히 충돌은 발생한다.

  1. separate chaining (개별 체이닝)
  • 기본적으로 같은 장소에 여러 데이터를 저장할 때 배열이나 연결 리스트 등과 같은 것을 활용하여 이중 데이터 구조를 쓰는 것
    index4 에 저장되어 있음
    [["다크블루", "#00008b"],["주황", "#fa8072"]]
    이렇게 배열을 활용할 때 사용은 쉽지만 중첩 배열 구조가 나온다.
  1. linear probing (직선 탐색법)
  • 각 위치에 하나의 데이터만 저장한다는 규칙을 그대로 살린다.
  • 충돌이 발생하면 일단 다음 빈 칸이 어디인지 확인한다.
  • 이렇게 하면 조금 더 복잡한데, 이렇게 하면 데이터가 같은 인덱스에 저장되는 것을 막을 수 있다.
    index[4]에 ["다크블루", "#00008b"]가 저장되어 있다.
    index[4]에 salmon 을 넣으려고 했는데 뭔가 저장되어 있네. => 그럼 index5는 비어 있나? => 응 => 거기다 넣어!

해시 테이블 Set과 Get 메소드

class HashTable{
	constructor(size=53//소수값으로 해시 테이블 크기 결정){
    	this.keyMap = new Array(size); // size에 맞는 새로운 배열을 만들어서 keyMap에 저장 // this.keyMap에 모든 데이터를 저장할 것이다. 
    }
    _hash(key){ // 해시 함수를 그냥 복사해왔다. 해시 테이블의 크기가 이미 클래스에 있어서 입려을 따로 할 필요가 없음 
    	let total = 0; 
        let WEIRD_PRIME = 31; 
        for(let i=0; i<Math.min(key.length, 100); i++){
        	let char = key[i]; 
            let value = char.charCodeAt(0) -96
            total = (total * WEIRD_PRIME +value) % this.keyMap.length;
        }
        return total; 
    }
}

set과 get과 같은 메소드들을 추가할 것이다. 그것들을 hash와 호출해서 키를 입력하면 값을 얻게 될 것이다.

Set

  • set은 값 하나와 키 하나를 입력한다. (pink라는 키에 해당하는 값이 있다.)
  1. 먼저 키를 해시 처리한다. (어디에 저장할지 알아내는 것)
  2. 개별 체이닝을 한다. (중첩 구조에 저장을 하는것) (이미 index[4]에 데이터가 있다면 거기에 push를 해주면되고, 데이터가 없다면 먼저 배열을 만들고 그 배열안에 데이터를 넣는다.)
    set
  3. Accepts a key and a value
  4. Hashes the key
  5. Stores the key-value pair in the hash table array via separate chaining

Get

salmon이라는 키를 입력한다고 하면,
salmon을 해시처리한다. 그러면 이미 정의되어 있는 해시함수에 의해서 숫자가 나온다.
일단 값을 얻고 나면, keyMap 배열의 인덱스에 해당하는 자리로 간다.
그리고 루프를 돌면서 salmon을 찾는다. 그리고 찾으면 ["salmon", "#fa8072"] 전체를 출력한다(index[4]에 salmon이 몇번째에 있는지는 모른다. 그냥 찾는것 ! )
해시테이블에 해당하는 것이 없다면 undefined를 출력!
get
1. Accepts a key
2. Hashes the key
3. Retrieves the key-value pair in the hash table
4. If the key isn't found, return undefined

해시 테이블 Set 메소드 솔루션

해시 테이블 Get 메소드 솔루션

class HashTable{
	constructor(size=53//소수값으로 해시 테이블 크기 결정){
    	this.keyMap = new Array(size); // size에 맞는 새로운 배열을 만들어서 keyMap에 저장 // this.keyMap에 모든 데이터를 저장할 것이다. 
    }
    _hash(key){ // 해시 함수를 그냥 복사해왔다. 해시 테이블의 크기가 이미 클래스에 있어서 입려을 따로 할 필요가 없음 
    	let total = 0; 
        let WEIRD_PRIME = 31; 
        for(let i=0; i<Math.min(key.length, 100); i++){
        	let char = key[i]; 
            let value = char.charCodeAt(0) -96
            total = (total * WEIRD_PRIME +value) % this.keyMap.length;
        }
        return total; 
    }
 set(key, value){
 	let index = this._hash(key); 
   if(!this.keyMap[index]){
   	this.keyMap[index] = []
   }
   this.keyMap[index].push([key,value])
 }
 get(key){
 	let index = this._hash(key); 
   if(this.keyMap[index]){
     //return this.keyMap[index] // 이렇게 하면 그 인덱스에 있는 전체를 리턴
   	for(let i=0; i<keyMap[index].length; i++){
    	if(this.keyMap[index][i][0] === key){//[0]은 키를 뜻함
        	return this.keyMap[index][i][1] //[1]은 값을 뜻함
        }
    }
   }
   return undefined
 }
}

let ht = new HashTable(); 
ht.set("hello world", "goodbye!!")
ht.set("maroon","#800000")
ht.set("yellow","#FFFF00")
ht.set("olive","#808000")

// 전체 출력했을 때 그 인덱스에 있는거 전체 출력하는 상황
// ht.get("yellow") 
//["maroon","#800000"]
//["yellow","#FFFF00"]

ht.set("are we done?", "yes!")
ht.get("are we done?")
// "yes"

키와 값이 한 쌍을 이루는 해시 테이블

이제 해시 테이블에 두 가지 메소드를 더 추가해야 한다.

keys

배열, 즉 테이블에 있는 모든 키를 포함한 목록
: Loops through the hash table array and returns an array of keys in the table

values

: Loops through the hash table array and returns an array of values in the table

key는 유일하지만 values는 겹칠 수 있다.
["이유정","a"]["김민수","c"]["백지현","a"]
이에 대한 메소드를 만들어볼 것임

해시 테이블의 키와 값 솔루션

class HashTable{
	constructor(size=53//소수값으로 해시 테이블 크기 결정){
    	this.keyMap = new Array(size); // size에 맞는 새로운 배열을 만들어서 keyMap에 저장 // this.keyMap에 모든 데이터를 저장할 것이다. 
    }
    _hash(key){ // 해시 함수를 그냥 복사해왔다. 해시 테이블의 크기가 이미 클래스에 있어서 입려을 따로 할 필요가 없음 
    	let total = 0; 
        let WEIRD_PRIME = 31; 
        for(let i=0; i<Math.min(key.length, 100); i++){
        	let char = key[i]; 
            let value = char.charCodeAt(0) -96
            total = (total * WEIRD_PRIME +value) % this.keyMap.length;
        }
        return total; 
    }
 set(key, value){
 	let index = this._hash(key); 
   if(!this.keyMap[index]){
   	this.keyMap[index] = []
   }
   this.keyMap[index].push([key,value])
 }
 get(key){
 	let index = this._hash(key); 
   if(this.keyMap[index]){
     //return this.keyMap[index] // 이렇게 하면 그 인덱스에 있는 전체를 리턴
   	for(let i=0; i<keyMap[index].length; i++){
    	if(this.keyMap[index][i][0] === key){//[0]은 키를 뜻함
        	return this.keyMap[index][i][1] //[1]은 값을 뜻함
        }
    }
   }
   return undefined
 }
 // 값들만 배열에 리턴한다(중복된 값들은 뺀다)
 values(){
	let valuesArr = []; 
   for(let i=0; i<this.keyMap.length; i++){
     if(this.keyMap[i]){
    for(let j=0; j<this.keyMap[i].length; j++){
    	if(!valuesArr.includes(this.keyMap[i][j][1])){
        	valusArr.push(this.keyMap[i][j][1])
        }
      }
     }   
   }
   return valuesArr; 
 }
// 위에 values()를 복붙하고 인덱스만 바꿔줬다. 
// 중복된 키를 빼주는 코드가 작성되어 있는데, 원래 키는 중복된 키를 애초에 set 하지 말아야 하는데 위에 그렇게 정교하게 코드를 작성해놓진 않았다는 점을 참고해주세용~!
keys(){
	let keysArr = []; 
   for(let i=0; i<this.keyMap.length; i++){
     if(this.keyMap[i]){
    for(let j=0; j<this.keyMap[i].length; j++){
    	if(!keysArr.includes(this.keyMap[i][j][0])){
        	keysArr.push(this.keyMap[i][j][0])
         }
       }
     }   
   }
   return keysArr; 
 }
}

//keys메소드를 이용해 순회할 수 있게 됐다~~
ht.keys().forEach(function(key){
	console.log(ht.get(key))
})

해시 테이블의 빅오 복잡도

(average case)

  • Insert : O(1)
    삽입을 할 때 연산을 한번만 한다는 것을 의미하지 않는다. 전체적인 흐름이 그렇다는 것
  • Deletion : O(1)
  • Access : O(1)

해시함수가 좋아야 한다
1) 해시 함수가 얼마나 빠른지
2) 얼마나 고르게 데이터를 분배해서 충돌 횟수를 줄이는지

실제로 해시 함수를 가지고 있는 거의 모든 프로그래밍 언어에서는 해시 함수가 상수값의 시간을 가진다.
암호기술 때의 해시 함수와는 다르게 해시 테이블을 말하는 거면 데이터의 일부나 스트링의 일부만 봐도 괜찮다.

직접 해시 함수를 작성하는 것을 추천하지 않는다. 잘 알려진 해시 함수를 사용해라
왜냐? 너가 해시 함수를 자칫 잘못 만들면 해시테이블의 하나의 인덱스에 모든 값들이 만약 다들어가? 그럼 그냥 리스트나 다름없어 !!!

마지막 복습

  • Hash tables are collections of key-value pairs
  • Hash tables can find values quickly given a key
  • Hash tables can add new key-values quickly
  • Hash tables store data in a large array, and work by hashing the keys
  • A good hash should be fast, distribute keys uniformly, and be deterministic
  • Separate chaining and linear probing are two strategies used to deal with two keys that hash to the same index
  • 자바스크립트에는 객체와 비슷하지만 사실은 맵과 조금 더 유사하다
  • 거의 대부분 언어에는 해시 테이블 기능이 있다.
  • 이건 일단 해시 테이블과 해시 맵에서 말하는 해시 함수고, 암호기술을 사용한 보안 해시 함수가 아니다.
profile
이유정
팀에 기여하고, 개발자 생태계에 기여하는 엔지니어로
이전 포스트

Set이 왜 해시인지에 대하여

다음 포스트

섹션21 스택 + 큐

0개의 댓글