해시 테이블(Hash Table)

해시 테이블(Hash Table)

• 유일한 값(반복되지 않는 값)을 저장하기 위한 자료 구조입니다.
• 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 바꿔 저장한 자료 구조입니다.
• 자바스크립트 객체와 같은 방식으로 key : 값 형식으로 저장됩니다.

해싱이란??

다양한 길이의 키(key) => 고정된 길이 해시(hash)로 바꿔주는 과정을 말합니다

해시 충돌

키(key)는 다른데 해시(hash)값이 똑같은 경우

ex)

11 % 2  == 1
21 % 2 == 1

 

해시 함수

키(key)를 해시(hash)로 바꿔주는 역할을 한다.
다양한 길이를 가지고 있는 키(key)를 고정된 길이를 가지는 해시(hash)로 변경하여
저장소(해시테이블)를 효율적으로 운영할 수 있도록 도와줍니다.

• 다양한 길이 : [... 3, ... 52 ... 50 ... 5004] - 데이터는 4개지만, 길이가 5005인 배열
  (기존 데이터의 키(key)일 경우)

• 고정된 길이 : [0(50), null, 2(52), 3(3), 4(5004)] - 데이터는 4개지만, 길이가 5인 배열
  (해시함수를 통과한 hash일 경우)

좋은 해시함수 만드는 법

• 결정성 : 동일한 키는 동일한 해시 값을 만들어야 합니다.
• 균일한 분배 : 배열 전체를 최대한 효율적으로 활용해야 합니다.
• 키는 다른데 해시 값이 똑같은 경우 충돌을 피할 수 있게 생성해야 합니다.

해시테이블 장단점

장점

• 작은 저장소(해시 테이블)로 많은 데이터를 효율적으로 관리할 수 있습니다.
• index에 해시값을 사용하여서 모든 데이터를 살피지 않고 검색, 삽입, 삭제를 빠르게 수행할 수 있습니다.
• 길이가 서로 다른 데이터에 대해 일정한 길이로 만들 수 있어서 '데이터 축약' 기능도 수행 가능합니다.

단점

• 순서가 있는 배열에는 어울리지 않습니다.(순서와 상관없이 key를 hash로 바꿔주기 때문)
• 공간 효율성이 떨어집니다.(데이터가 저장되기 전에 미리 공간을 확보해야 하고, 공간이 부족한 경우 채워지지 않기 때문)

해싱 기법

• 선형 탐사 : 키가 다른데 동일한 해시값이 나온경우 hash + 1 하여 저장하는 기법
• 이차 탐사 : 키가 다른데 동일한 해시값이 나온 경우 hash + (중복된 횟수 제곱) 하여 저장하는 기법
• 이중 해싱 : 키가 다른데 동일한 해시값이 나온 경우 hash값을 한번더 해시함수를 이용하여 저장하는 기법

code

function hashTable(size) {
  this.size = size;
  this.keys = this.initArr(size);
  this.values = this.initArr(size);
  this.limit = 0;
}

hashTable.prototype.initArr = function(size) {
  var arr = [];
  for(var i=0; i<size; i++) {
    arr.push(null);
  }
  return arr
}

hashTable.prototype.put = function(key, value) {
  if(this.limit >= this.size) {
    return console.log('더이상 추가 할 수 없습니다.')
  }

  var hashIndex = this.hash(key);

  while(this.keys[hashIndex] !== null) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }

  this.keys[hashIndex] = key;
  this.values[hashIndex] = value;
  this.limit++;
}

hashTable.prototype.get = function(key) {
  var hashIndex = this.hash(key);
  while(this.keys[hashIndex] != key) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }
  return this.values[hashIndex];
}

hashTable.prototype.hash = function(key) {
  if(!Number.isInteger(key)) {
    return console.log('숫자가 아닙니다')
  }
  return key % this.size;
}



var test = new hashTable(13);
test.put(4, "kim");
test.put(13, "lee");
test.put(18, "you");
test.put(33, "heo");
test.put(59, "son");
test.put(82, "jung");
test.put(101, "seo");
test.put(109, "sad");

console.log(test)

// hashTable {
//   size: 13,
//   keys: [
//     13,   null, null, null,
//     4,    18,   82,   33,
//     59,   109,  101,  null,
//     null
//   ],
//   values: [
//     'lee',  null,  null,
//     null,   'kim', 'you',
//     'jung', 'heo', 'son',
//     'sad',  'seo', null,
//     null
//   ],
//   limit: 8
// }

 

설명

1. HashTable 생성

function hashTable(size) {
  this.size = size;
  this.keys = this.initArr(size);
  this.values = this.initArr(size);
  this.limit = 0;
}

hashTable.prototype.initArr = function(size) {
  var arr = [];
  for(var i=0; i<size; i++) {
    arr.push(null);
  }
  return arr
}

var test = new hashTable(13);

console.log(test)

// hashTable {
//   size: 13,
//   keys: [
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null
//   ],
//   values: [
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null
//   ],
//   limit: 0
// }

2.  추가

// 해시 테이블에 데이터를 추가하는 함수
hashTable.prototype.put = function(key, value) {
  // size == 테이블 최대 크기
  // limit == 현재 테이블 크기
  if(this.limit >= this.size) {
    return console.log('더이상 추가 할 수 없습니다.')
  }

  // 해싱 함수를 호출하여 key값을 => hash값으로 바꿈
  var hashIndex = this.hash(key);

  // 이미 해당 hash값이 있다면 +1 하여 저장
  while(this.keys[hashIndex] !== null) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }

  // 중복되지 않은 해시값이 정해졋을때 hash값 : value 저장하고 현재 테이블 크기도 +1 해줌
  this.keys[hashIndex] = key;
  this.values[hashIndex] = value;
  this.limit++;
}

// key => hash로 바꿔주는 함수
hashTable.prototype.hash = function(key) {
  if(!Number.isInteger(key)) {
    return console.log('숫자가 아닙니다')
  }
  return key % this.size;
}

test.put(4, "kim");
test.put(13, "lee");
test.put(18, "you");
test.put(33, "heo");
test.put(59, "son");
test.put(82, "jung");
test.put(101, "seo");
test.put(109, "sad");

3. 검색

// 해시 테이블에 해당 hash값을 가지고 있는지 검색하는 함수
hashTable.prototype.get = function(key) {
  // 해싱 함수를 호출하여 key값을 => hash값으로 바꿈
  var hashIndex = this.hash(key);

  // 이미 해당 hash값이 있다면 +1하여 검색
  while(this.keys[hashIndex] != key) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }

  console.log(this.values[hashIndex])
  // 해당 key의 hash값을 찾았을때 value값을 return함
  return this.values[hashIndex];
}

// key => hash로 바꿔주는 함수
hashTable.prototype.hash = function(key) {
  if(!Number.isInteger(key)) {
    return console.log('숫자가 아닙니다')
  }
  return key % this.size;
}

test.get(4, "kim");
test.get(13, "lee");
test.get(18, "you");
test.get(33, "heo");
test.get(59, "son");
test.get(82, "jung");
test.get(101, "seo");
test.get(109, "sad");