Algorithm

[Algorithm] 해쉬테이블(Hash Table)

hyebin Lee 2022. 1. 31. 23:19

해쉬 테이블이란?

검색하고자 하는 키 값을 입력받아서 해쉬함수를 돌려 반환받은 해쉬 코드를 배열의 인덱스로 환산하여 데이터로 접근하는 자료구조이다. 여기서 사용하는 키값은 문자열,숫자,파일데이터 등이 될 수있다.

해쉬 함수는 어떤 특정한 규칙을 이용해서 입력받은 키값으로 해쉬코드를 만들어준다.

해쉬코드의 장점

검색속도가 매우 빠른것이다.

왜 빠를까?

해쉬 함수를 이용해서 만든 해쉬코드는 정수다. 따라서 배열 공간을 고정된 크기 만큼 미리 만들놓고, 해쉬 코드를 배열 의 갯수로 나머지 연산을 해서 배열에 나눠 담는다. 해쉬코드 자체가 배열의 인덱스로 사용되기 때문에 검색 자체를 할 필요가 없이 해쉬코드로 바로 데이터에 접근이 가능하다.

효율적인 해쉬 알고리즘?

공간의 효율성을 위해 해쉬 알고리즘을 잘만드는 것이 중요하다. 알고리즘이 좋지 않으면 배열 한 방에 여러 데이터가 들어가기 때문에 충돌현상이 일어날 수 있다. 이를 collison이라고 한다.

해쉬의 장점은 속도가 빠른것이지만->O(1), collison(=충돌)이 많을 경우 최대 검색 시간이 O(n) 걸린다. 이유는 방안에 데이터를 일일히 검색을 해야하기 때문이다.

따라서 해쉬함수의 알고리즘은 입력받은 키를 가지고 골고루 잘 분배를 하느냐에 따라 효율성이 달라진다.

해쉬함수는 다른 키값으로 동일한 해쉬코드를 만들어 내기도 한다. 이유는 키값은 문자열이고 가짓수가 무한하지만 해쉬코드는 정수개만큼 제공을 못하기 때문에 알고리즘이 좋아도 중복되는 해쉬코드를 갖는다.

collision을 최소화 해야한다.

해쉬테이블로 정리하면 이렇게 된다. Pizza가 키, 100은 값이 된다!

key, value를 저장하지 말고 value만 저장하자! 이 테크닉은 array로 작업하는 것보다 빠르다

이 방법은 하나씩 찾아야 하므로 효율적이지 않는다.

따라서 hash테이블을 사용해 보자!

이렇게 해쉬 테이블을 이용할 경우

이런 식으로 쉽게 찾을 수 있게 된다.

2. 해시테이블 : Map

JS에서 해시테이블은 대표적으로 Object, Map, Set이 있다. JS에서 key-value로 이루어진 자료구조는 Object가 대표적이였지만, ES6에서 Map과 Set이 추가되었다.

2.1 Map 객체란?

주로 Object와 비교됨
key-value로 이루어진 해시 테이블
탐색은 get(), 삽입은 set()으로 한다.
key는 고유값으로써, 단 한개만 존재한다.
key 가능 자료형 : number, string, function, object, NaN

2.2 Map의 함수들

2.2.1 value 설정 : set()

let map = new Map();

let number = 0;
let str = 'string';
let obj = { a: 1 };
let fnc = () => {
    console.log('fnc');
};

map.set(number, 4); //key에 number 가능
map.set(str, 1); // key에 string 가능
map.set(obj, 2); //key에 object 가능
map.set(fnc, 3); // key에 함수 가능
map.set(number, 0); // 덮어쓰기 가능

console.log(map); // Map(4) {0 => 0, "string" => 1, {…} => 2, ƒ => 3}

2.2.2 value 얻기 : get()

//위의 코드 재사용..

map.get(str); // 1
map.get(obj); // 2
map.get('none'); // undefined  
map.get({ a: 1 }); // undefined, obj !== { a: 1 }

2.2.3 value 찾기 : has()

//위의 코드 재사용..

map.has(str); // true
map.has(obj); // true
map.has('none'); // false

2.2.4 value 삭제 : delete()

//위의 코드 재사용..

map.delete(str); // true 
map.get('none'); // false

2.2.5 value 존재유무 : size

map.size // 4
map.length // undefined

2.2.6 hash 탐색 : for-of 문

//key, value 쌍으로 출력
for (let [key, value] of map) {
  console.log(key + ' = ' + value)
}

//key만 출력
for (let key of map.keys()) {
  console.log(key)
}

//value만 출력
for (let value of map.values()) {
  console.log(value)
}

Set

중복되지 않는 리스트를 만들 때 사용.

Set() 생성

let set = new Set();

add(data) 메소드: set에 데이터 추가

set.add('a');

size 속성: set의 항목 수

set.size;

has(data) 메소드: set에 데이터가 존재하는지, true/false 반환.

set.has('a');

delete(data) 메소드: set에서 데이터 제거.

set.delete('a');

clear() 메소드: set의 모든 값 제거.

set.clear();

forEach(data, key, array) 메소드:

set을 반복할 때, data와 key는 같은 값을 가진다. set에는 key가 없기 때문.

set.forEach((value, key, array) => {
	console.log(value, key, array);
});

[...set]: set을 배열로 바꿀 때, 전개연산자 사용.

[...set];