자료구조 정리8 : Hash Tables

Kimhojin_Zeno·2023년 4월 4일

Hash Table hash hash function 자료구조 해시 해시함수

자료구조 정리

목록 보기

8/9

해시 테이블

해시 맵이라고도 한다. 매우 자주 사용되는 것들

많은 프로그래밍 언어에 해시 테이블이 내장되어 있다. 배열처럼.

내장되어 있지만 원리를 공부하기 위해 직접 코딩해본다.

해시 알고리즘에 대해서도 공부

해시 테이블에서 충돌이 어떤 의미인지 어떻게 해결하는지

Hash table이란

해시 테이블은 key-value 쌍을 저장하는데 사용된다

해시 테이블의 키는 순서를 가지지 않음.

배열은 인덱스가 0에서 시작하지만 해시 테이블은 아니다

해시 테이블의 장점은 값을 찾거나, 새로운 값을 추가,제거하는데 매우 빠르다

모든 것이 매우 빠름

일반적으로 연속적인 흐름이 있는 데이터가 있다면 배열을 사용하면 된다

그러나 그렇지 않은 데이터는 해시 테이블을 사용한다

여러 프로그래밍 언어에서의 내장 해시 테이블 명칭

Python - Dictionaries
JavaScript - Object, Maps
Java - Maps
Go - Maps
Scala - Maps
Ruby - Hashes

Hash

해시 : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값. 해시값이라고도 한다.
해시 함수 : 해시를 이용한 함수(function). 데이터를 해시값으로 만들때 사용한다
해시 테이블 : 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하여 검색을 빠르게 하기 위한 자료구조. 데이터가 저장되는 곳을 버킷(bucket)또는 슬롯(slot)이라고 한다.

스트링을 해시함수에 넣어서 숫자가 나오면 그 숫자 자리에 데이터를 넣는다

같은 스트링을 넣으면 언제나 같은 숫자가 나와야한다. 그렇지 않으면 전체 구조가 무너짐.

해시함수는 스트링이나 사진, pdf, 영상을 넣으면 숫자를 뱉어야한다. 만들기 쉽지 않다

Hash Function 해시함수

임의의 크기를 가지는 데이터를 입력하면 정해진 크기의 데이터를 출력하는 함수.

해시함수는 전세계 인터넷과 개인정보 보호, 계산 업무 등 널리 쓰인다

암호화폐에서도 사용된다

Cryptographic hash function암호화 해시 함수

연구자들이 많이 연구하는 분야. 암호 기술중에서도 정말 어려운 분야다

해시함수의 두가지 특징

일정한 크기를 가진 데이터로 출력
출력된 데이터로 원래 데이터를 찾을 순 없음, 즉 단방향 함수이다.

좋은 해시 함수의 조건

빨라야 함
겹치지 않고 고르게 퍼져야 함
특정 입력값을 입력할 때마다 같은 출력값이 나와야 함(결정론적)

해시함수 예시

function hash(key, arrayLen) { //arrayLen는 해시테이블의 길이. 100이라면 해시함수는 0-99사이의 값을 주어야한다
  let total = 0;
  for (let char of key) {
    // map "a" to 1, "b" to 2, "c" to 3, etc.
    let value = char.charCodeAt(0) - 96  // 글자코드에서 -96을 하면 알파벳 순서값이 나온다
    total = (total + value) % arrayLen;  // 각 순서값을 더하고 해시테이블 길이를 모듈로 연산한다
  }
  return total;
}

str.charCodeAt(idx) 은 괄호안에 인덱스를 넣으면 앞에 스트링의 UTF-16 글자 코드를 리턴한다.

모듈로 연산Modulo Operation : 어떤 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

해시함수 자체가 작동하는 방식의 세부적인 것은 중요하지 않다.

위 예시의 문제점은 key가 길어지면 반복문을 많이 돌리니 처리 시간이 길어진다.

두번째로 서로 다른 스트링을 입력해도 같은 값이 나오기 쉽다. 뭉치기 쉽다.

이는 좋지 않다. 펼치는 방법이 있다

대부분의 해시함수는 소수(prime number)를 이용한다.

이건 수학의 영역. 소수를 이용하면 충돌이 줄어든다. 데이터가 펼쳐짐.

수정된 해시함수 예시

function hash(key, arrayLen) {
  let total = 0;
  let WEIRD_PRIME = 31;
  for (let i = 0; i < Math.min(key.length, 100); i++) { // 스트링 길이와 100중 작은 값. 즉 아주 긴 스트링은 앞에 100글자만.
    let char = key[i];
    let value = char.charCodeAt(0) - 96
    total = (total * WEIRD_PRIME + value) % arrayLen; // 기존 total에 소수를 곱하고 새값을 더한 후 길이로 모듈로 연산
  }
  return total;
}

소수가 작동하는 복잡한 세부사항들은 매우 복잡하다. 다 알기 어렵다

해시함수의 리스트, 즉 테이블의 길이는 소수값이며 긴게 좋다.

스트링을 받아서 스트링의 길이와, 100중에 적은 값만큼 루프를 돈다.

이렇게 소수를 쓰면 훨씬 나은 해시함수가 된다.

충돌해결

Hash Collisions

해시충돌 : 해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황

충돌 해결법

separate chaining개별 체이닝,
linear probing선형 조사법

Separate Chaining 개별 체이닝

개별 체이닝은 기본적으로 같은 장소에 여러 데이터를 저장할 때 배열이나 연결 리스트 등과 같은 것을 활용하여 이중 데이터 구조를 쓰는 것이다.

즉 공동 저장을 하는 것. 여러 개의 키-값 쌍을 같은 자리에 저장한다

배열을 쓴다면 한 자리에 중첩 배열 구조가 되는 것이다. [ [], [] ]

Linear Probing 선형 조사법

각 위치에 하나의 데이터만 저장한다.

충돌이 발생하면 다음 빈 칸을 찾아서 거기에 넣는다

해시 테이블 구현

class HashTable {
  constructor(size=53){ //생성자 함수엔 size 해시 테이블의 크기를 결정. 소수로 한다. size를 따로 추가하지 않으면 53이 된다.
    this.keyMap = new Array(size); //배열로 만든다
  }

  _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

해시 테이블에 새로운 값 넣기

값 하나와 키 하나를 입력한다
키를 해시 처리한다
개별 체이닝한다

set(key,value){
    let index = this._hash(key); //키를 해시 함수에 넣어 값을 인덱스로 선언한다
    if(!this.keyMap[index]){ // 배열에 해당 인덱스 값이 없다면
      this.keyMap[index] = []; // 빈 배열을 넣어주고(개별 체이닝을 위한 중복배열)
    }
    this.keyMap[index].push([key, value]); // 그 배열 안에 키-값 쌍을 넣은 배열을 넣는다
  }

get

키를 가지고 해시 테이블에서 값 찾기

키를 받아서
키를 해시 처리한다
얻은 값을 가지고 인덱스에 해당하는 자리로 가서 값을 확인한다

get(key){
    let index = this._hash(key); // 키를 받아서 해시함수에 넣어 인덱스를 얻는다
    if(this.keyMap[index]){ // 배열에 해당 인덱스가 존재하면
      for(let i = 0; i < this.keyMap[index].length; i++){ // 중첩배열을 반복문으로 돌려서 값을 찾는다.(개별 체이닝)
        if(this.keyMap[index][i][0] === key) {
          return this.keyMap[index][i][1]
        }
      }
    }
    return undefined; // 배열에 해당 인덱스가 없다면 undefined.
  }

keys, values

keys는 배열, 즉 테이블에 있는 모든 키를 포함한 목록을 출력한다.

values는 모든 값을 포함한 목록을 출력한다.

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]) // 해당 키를 push한다
          }
        }
      }
    }
    return keysArr;
  }
  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])){ //해당 값이 리턴할 배열에 존재하지 않으면
            valuesArr.push(this.keyMap[i][j][1]) // 넣는다
          }
        }
      }
    }
    return valuesArr;
  }

해시 테이블의 Big-O

insertion - O(1)

deletion - O(1)

access - O(1)

평균적인 경우와 최상의 경우에 상수값을 가진다

그러나 해시함수의 성능이 좋지 않으면 (덜 퍼지면) 개별 체이닝을 사용했을 때 한 자리에 들어가는 키-값이 많아져 O(n) 이 될수 있다

그러니 좋은 해시함수는 빠르고 균일하게 데이터를 분배해야 한다

해시함수를 직접 작성하는 것을 추천하지 않는 이유. 알려진 좋은 해시함수를 써라.

Kimhojin_Zeno

Developer

이전 포스트

자료구조 정리7 : Binary heaps

다음 포스트

자료구조 정리8 : Hash Tables