Hash Table이란 ?

Wike 曰

• 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조
• 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산

어떤 특정값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스에 저장하는 자료구조. 보통 배열을 이용해서 구현

직접 주소 테이블(Direct Address Table)

직접 주소 테이블이란

내가 이해한 것은 ... 마치 신발장같은 느낌 !
헬스장 신발장을 생각해보자
1번부터 100번까지 지정되어있는 신발장이 있다고 치자
그치만 코로나로인해 회원수가 줄어들어서 회원이 3명뿐 ㅠㅠ

3번 회원 7번 회원 98번 회원

3번 사물함에는 3번 회원
7번 사물함에는 7번 회원
98번 사물함에는 98번 회원

사물함 번호와 회원 번호가 같아서 쉽게 찾을 수 있다.
문제는 3개의 사물함 빼고는 전부 쓸 곳이 없다는 것이다. !

(100) [0, 0, 3, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 98, 0, 0]

요것이 직접 주소 테이블이다.

• 장점
  • 인덱스 = value가 같음
  • 데이터의 위치 찾기가 매우 편함
• 단점
  • 불필요한 저장공간을 차지함

이러한 문제점을 Hash Function을 활용하여 보완

해쉬 함수를 사용하여 보완하는 방법

해쉬함수란?

Wike 曰
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

해쉬함수 만들기 : 나머지 연산자 사용 !

function hashFun(value){
  return value % 10
}

How to use ?

let size = 5;
let hashTable = new Array(size);

function hashFunction (value) {
  // 들어온 값을 테이블의 크기로 나눠주고 나머지를 반환하면 된다.
  return value % size;
}

hashTable[hashFunction(100)] = 100;
hashTable[hashFunction(634)] = 634;
hashTable[hashFunction(15)] = 15;

console.log(hashTable); // [empty, 100, empty, 15, 634]

해쉬 테이블의 단점

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

hashFunction(1991) // 1
hashFunction(6) // 1

해결방안

미완