해시(Hash) 개념과 코딩테스트에서 활용하기

📖  목차

 

코딩테스트 문제를 풀다보면 가장 기본적으로 나오는 기출 형태인 해시.
매번 검색해보고 해결법을 찾아보긴했지만 이번 기회에 개념을 확실히 잡고자 개념과 활용법에 대해 정리하기로 해보았다.

 

Hash, Hash Function, Hash Table

먼저 제일 큰 개념의 해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 index로 주소삼아 key와 함께 값을 저장하는 자료구조이다. 단순하게 key - value로 이루어진 자료구조라고 생각하면 된다.

키를 해시함수를 사용하여 매핑한다고 했는데, 이때 원하는 값을 효율적으로 찾을 수 있게 하기 위해 저장하는 위치를 잘 골라야 하는데 해시함수는 key를 고정된 길이의 해시로 변경해주는 역할을 한다.

정리하자면,

hash는 색인 또는 인덱스
hash function은 key->hash로 만들어 주는 함수
hash table은 hash를 주소로 삼아 데이터를 저장하는 자료구조이다.

 

---

 

Hash Table

정리한것에 따라 주로 코딩테스트에서 사용되는 것은 해시테이블이고, 해시테이블에 대해 공부해보자.

위에서 해시테이블이란 key - value로 이루어진 자료구조라고 설명했다.
이때 key는 무언가를 찾기 위한 검색어, value는 검색어로 나온 결과라고 생각하면 되고 쉽게 전화번호부를 예시로 들면 이름이 key, 전화번호가 value인 셈이다.

 

시간복잡도

해시테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 탐색 모두 O(1)의 시간복잡도를 가지고 있다.

 

사용 목적

그렇다면, 어떤 코딩테스트 문제를 만났을 때 해시를 사용해야할까?

- 빠르게 값을 찾아야하는 경우
- string을 기반으로 정보를 기록하고 관리해야할때

 

문제점

해시충돌(같은 index를 바라보게 되면 하나의 칸에 여러 값이 몰리는 해시충돌이 발생한다.)
해시충돌 해결법

1. 선형탐사법 충돌이 발생하면 옆으로 한 칸 이동한다.
   최악의 경우 O(n)시간이 걸림
2. 제곱탐사법 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 이동
3. 이중해싱 충돌이 발생하면 다른 해시 함수 이용
4. 분리 연결법 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

 

자바스크립트 활용

객체

const table = {};
table["key"] = 100;
table["key2"] = "hello";
console.log(table["key"])    //100
table["key"] = 486;
console.log(table["key"])    //486
delete table["key"];
console.log(table["key"])    //undefined

Map

key값으로 object나 array 등 복잡한 값으로 넣을 수 있다.
get, set등 편리하게 제공되는 기능이 있다.

• .set(key, value) : 추가
• .get(key) : 조회
• .delete(key) : 삭제
• .keys() : key object 반환
• .values() : value object 반환
• .clear() : map 초기화

example

const table = new Map();
table.set("key", 100);
table.set("key2", "hello");
console.log(table['key']);    //undefined
console.log(table.get('key'));    //100

const object = {a:1};
table.set(object, "A1");    //object, array등 복잡한 key값이 가능
console.log(table.get(object));    //A1

table.delete(object);
console.log(table.get(object));    //undefined

console.log(table.keys());    //{ 'key', 'key2' }
console.log(table.values());    //{ 100, 'Hello' }

table.clear();
console.log(table.values());    //{ }

Set

set은 key와 value가 동일하게 들어가며 중복이 제거된다.
map처럼 제공되는 편리한 기능들이 있다.

• .add(key) : key와 value가 동일하게 들어간다.
• .has(key) : key라는 값이 존재하는지 여부
• .delete(key) : 삭제
• .clear() : 초기화

example

const table = new Set();
table.add('key');
table.add('key2');
console.log(table.has('key'));    //true
console.log(table.has('key3'));    //false

table.delete('key2');
console.log(table.has('key2'));    //false

table.add('key3');
console.log(table.size);    //2
table.clear();
console.log(table.size);    //0

참고
https://www.youtube.com/watch?v=zFL29ydL9D8