해시(Hash)

Eugenius1st·2022년 10월 13일

JavaScript_algorithm

목록 보기

16/21

해시(Hash)

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 -> 해시라고 한다.

그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다.

해시 테이블

해시 테이블은 키(Key)에 데이터(Value)를 저장하는 자료구조 형이다.
key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다.
python 딕셔너리(Dict)타입이 해쉬의 테이블의 예이다.(파이썬에서는 해쉬를 별도 구현할 이유가 없다)

자바스크립트 객체가 아닌 해쉬를 사용해야 하는 이유
https://intrepidgeeks.com/tutorial/the-object-in-js-is-not-a-hash-table
해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다.
해시 함수(Hash Function)을 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다.

해싱 과정 예시

function hashStringToInt(s, tableSize) {
  let hash = 17;
  for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize;
  }
  return hash;
}
// 해시 테이블//
class HashTable {
  table = new Array(71);
  setItem = (key, value) => {
    const idx = hashStringToInt(key, this.table.length);
    this.table[idx] = value;
  };
  getItem = (key) => {
    const idx = hashStringToInt(key, this.table.length);
    return this.table[idx];
  };
}