자료구조 - 해시 테이블(hash table)이란 무엇인가?

1. 해시와 해시 테이블(hash table)이란 무엇인가?

1) 해시 테이블이란? 

해시 함수에 의해 얻어지는 값을 해시라고 부른다. 해시 함수에 key를 줄 경우, key에 해당하는 숫자 index주소를 반환하고, 그 숫자 index에 value를 저장하는 원리로 해시 테이블을 생성한다. 해시 테이블은 키(key)와 값(value)으로 데이터를 저장하는 비선형 자료 구조로, 각 키(key)에 대해 고유한 해시 값(hash value)을 생성하고, 이 해시 값을 배열의 인덱스로 사용하여 값을 저장하고 검색하는 방식이다. 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어 에서 사용된다.

해시가 매우 빠른 데이터 검색을 할 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값(value)이 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하기 때문이다.

즉 일반 배열을 순회할 때는 O(N), 선형 시간으로 순회할 아이템이 많을 수록 찾는 시간도 오래걸려 시간복잡도가 증가하지만, 해시 테이블의 경우 O(1) 상수 시간이기 때문에 어떤 요소를 찾는데 소요되는 건 딱 1개의 스텝이라는 것이다.

💡 해시 테이블 정리
- 자료구조의 종류 중 하나 (ex. Array, Object 등)
- key와 value를 가지는 자료구조 형태
- 배열에서는 key값에 숫자만 가능하지만, Hash Table에서는 문자열 또한 Key (Map에서는 함수도 가능)Hash - Function을 통해 빠른 탐색이 가능 -> O(1)

 

2)  해시 함수란 무엇인가?

array는 인덱스 숫자로만 접근할 수 있다. string을 key로 이용할 수 없다는 의미다. 따라서 string 값을 해시 테이블에 넣어 주려면 string 자료형을 number 자료형으로 바꾸어서 해당 number 인덱스에 데이터를 저장하도록 해야 한다.

이렇게 해시 테이블의 키를 number 자료형으로 만드는 어떤 함수를 hash function, 해시 함수라고 한다. 

💡 해시 와 해시 함수 정리
- key와 연결되어 있는 value를 삽입, 삭제, 탐색하는 알고리즘 함수
- 알고리즘 함수의 종류는 많지만, 대표적으로 MDS 함수가 존재
- key가 들어오면 Random하게 주소값을 생성한 후, 해당 주소값에 key와 value를 저장
- 해시함수 과정에서 해시충돌이 일어날 수 있음

 

 

3) 해시 충돌

하지만 각기 다른 key에 대하여 해시함수가 동일한 숫자를 줄 경우 해시 충돌이 발생한다.

해결 방법으로는, 해당 index에 배열을 넣어 충돌되는 두가지를 관리한다. 찾을 때는 key를 해시 함수에 넣어 해당하는 value인 배열을 찾고, 그 배열에서 선형검색을 통해 관리한다. -> 이런 해시 충돌 때문에 선형 검색을 해야 하기 때문에 해시가 항상 상수 시간(O(1))인 것은 아니다. 하지만 평균적으로는 보통 O(1)이라고 볼 수 있다.

이 밖에도 다양한 방법이 있다.

자바스크립트로 해시테이블 구현하는 방법

 

 

2. 해시테이블 : Map

1) Map() 객체란 무엇인가?

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

let map = new Map(); // 생성자

💡 Map() 객체 정리
key-value로 이루어진 해시 테이블
탐색은 get(), 삽입은 set(), 삭제는 delete()으로 한다.
key는 고유값으로써, 단 한개만 존재한다.
key 가능 자료형 : number, string, function, object, NaN

 

2) Map()의 Method

(1) .get(' ') : 해당하는 key값을 찾아서 반환

(2) .set(key, value) : 객체 내부에 설정한 key와 value 값으로 key : value를 추가, 수정해 준다.

(3) .delete(' ') : 해당 하는 key값을 삭제한다.

(4) .clear() : 모든 key, value 지우 

(5) .has(key) :특정 key를 가지고 있는지 확인하기

(6) .entries() : [key, value]의 array를 삽입된 순서대로 가진 새로운 lterator 반환

(7) .size() : Map의 크기(배열의 length와 비슷한)

 

2) Map()의 장점 

(1) Object의 key는 기호나 문자만을 가질 수 있다. 하지만 Map은 어떠한 형태라도 key로 사용될 수 있다(함수도 가능).

const map = new Map();
const myFunction = () => console.log('I am a useful function.');
const myNumber = 666;
const myObject = {
  name: 'plainObjectValue',
  otherKey: 'otherValue'
};
map.set(myFunction, 'function as a key');
map.set(myNumber, 'number as a key');
map.set(myObject, 'object as a key');

console.log(map.get(myFunction)); // function as a key
console.log(map.get(myNumber)); // number as a key
console.log(map.get(myObject)); // object as a key

(2) Object의 경우 일반적인 방법으로는 size를 확인 할 수 없다. 하지만 Map은 가능하다.

const plainObjMap = {};
plainObjMap['someKey1'] = 1;
plainObjMap['someKey2'] = 1;
...
plainObjMap['someKey100'] = 1;

console.log(Object.keys(plainObjMap).length) // 100, Runtime: O(n)

const map = new Map();
map.set('someKey1', 1);
map.set('someKey2', 1);
...
map.set('someKey100', 1);

console.log(map.size) // 100, Runtime: O(1)

(3) 시간복잡도에서 처리 시간이 굉장히 빠르다.

(4) Object의 반복문을 실행시키려면 힘들다. 하지만 Map은 반복문을 아주 편리하게 사용 할 수 있다.

const plainObjMap = {};
plainObjMap['someKey1'] = 1;
plainObjMap['someKey2'] = 2;
plainObjMap['someKey3'] = 3;

for (let key of Object.keys(plainObjMap)) {
  const value = plainObjMap[key];
  console.log(`${key} = ${value}`);
}
// someKey1 = 1
// someKey2 = 2
// someKey3 = 3

const map = new Map();
map.set('someKey1', 1);
map.set('someKey2', 2);
map.set('someKey3', 3);

for (let [key, value] of map) {
  console.log(`${key} = ${value}`);
}
// someKey1 = 1
// someKey2 = 2
// someKey3 = 3

(5) 순서의 보장 Object에서는 키의 순서를 보장하지 않는다.

(6) Object에는 미리 정의된 prototype이 있기 때문에 key가 충돌할 위험이 있다. 하지만 Map을 사용할 때는 그런 걱정을 할 필요가 없다.

const plainObjMap = new Map();
plainObjMap['someKey1'] = 1;
plainObjMap['someKey2'] = 2;
plainObjMap['toString'] = 3; // Oops, native property

const map = new Map();
map.set('someKey1', 1);
map.set('someKey2', 2);
map.set('toString', 3); // No problem for Map

- 'toString'은 JavaScript 엔진이 이미 정의한 내장 함수로 예약된 속성이다. 따라서 이렇게 'toString'을 키로 사용하면 Object의 내장 속성이 덮어써질 수 있습니다. Map은 프로토타입을 상속하지 않으므로 'toString'과 같은 예약된 이름을 키로 사용해도 문제가 발생하지 않는다

 

 

3. 해시테이블 : Map과 Set의 차이

1)Map의 특징

• 데이터와 키를 같이 저장할 수 있는 자료구조이다.
• 키와 값 [key, value] 으로 이루어진 데이터를 저장하고 관리한다.
• 본래 key 삽입 순서를 기억한다
• 어떤 value(객체와 원시값*)든 key 혹은 value로 사용될 수 있다 (key의 타임에 제약이 없음)
• 순서는 유지되지 않는다
• 삽입 순서로 요소를 반복한다. 루프는 각 반복에 대해 for...of 루프의 [key, value] 배열을 반환한다
• Key에는 중복된 값이 입력될 수 없다
• Value에는 중복이 허용된다
• NaN 도 key로 쓸 수 있다

❗ Key equality는 sameValueZero 알고리즘을 기반으로 한다
❗ 뛰어난 검색 속도를 가지고 있다는 장점이 있다
❗ 인덱스가 따로 존재하지 않아서 iterator를 사용한다

 

2)Set의 특징

• 중복이 존재할 수 없는 자료구조이다. 어떤 값이라도 그 Set 콜렉션 내에서 유일하다
• 모든 값들은 고유해서 새로운 값을 추가하거나 변경하면 값 비교가 이루어진다
• 인덱스를 사용하지 않는다
• 인덱스 매개변수가 없다
• 집합에 빗대어 생각할 수 있다
• 원시값과 객체 참조 모두 유일한 값을 저장할 수 있다
• 삽입 순서대로 요소를 순회한다
• NaN 과 undefined 도 Set 에 저장할 수 있다

❗ 조회에 있어서 Array 에 비해 훨씬 빠르다
Array는 배열, 무언가를 나열할 수 있기 때문에 다양한 타입이 오기도 하고 중복되는 같은 값이 올 수 있다. Set은 중복되지 않은 값들을 모아둔 집합이다. 중복된 것들을 제거한 Set이 조회에 있어서 훨씬 빠르다고 할 수 있다.
❗ (Map과 마찬가지로) 인덱스가 따로 존재하지 않기 때문에 iterator를 사용한다
Set의 value에 반복 작업 하기 위해서 for...of나 forEach를 사용한다.

 

 

4. 해시테이블 알고리즘 예제 풀어보기

1. 폰켓몬

function solution(nums) {
    let half = nums.length/2
    let answer = new Set(nums);
    return answer.size > half ? half : answer.size
}

프로그래머스

2. 전화번호 목록

// Map() 이용해서 풀이
function solution(phone_book) {
    let answer = new Map()
    phone_book.forEach((val)=> answer.set(val, true))
    
    for(let val of answer){
        for(let i = 0; i < val[0].length; i++){
            const search = val[0].slice(0,i)
            if(answer.get(search)) return false;
        } 
    }    
    return true;
}

// Set() 이용해서 풀이
function solution(phone_book) {
    let answer = new Set(phone_book)
    
    for(let val of answer){
        for(let i = 0; i < val.length; i++){
            const search = val.slice(0,i)
            if(answer.has(search)) return false;
        } 
    }    
    return true;
}

// 일반 객체 해시로 풀이
function solution(phoneBook) {
  const table = {};

  for (const number of phoneBook) {
    table[number] = true;
  };

  for (const number of phoneBook) {
    for (let i = 1; i < number.length; i += 1) {
      const prefix = number.slice(0, i);
      if (table[prefix]) return false;  
    };
  };

  return true;
}

프로그래머스

 

✅ 알고리즘 풀이 후 알게된 점

1) for in은 열거 가능한 객체 속성을 순회, for문은 일반적인 반복작업(횟수 등), for of문은 iterable(반복가능한) 객체에 사용 가능하다(배열, 문자열, Map, Set 객체)

• for...in 반복문 : 객체의 속성들을 순회하는 데 사용
• for문 : 일반적인 반복 작업(반복 횟수를 알고 있을 때 사용됩니다. 예를 들어, 배열의 인덱스를 순회하거나 특정 작업을 여러 번 반복해야 할 때, 시작값과 종료값을 알고 있을 때, 객체 속성을 직접 순회하지 못한다)
• for...of 반복문을 사용하여 Map 객체를 순회할 때, val은 [key, value] 형태의 배열로 반환된다. 따라서, solution 함수에서도 for...of 반복문을 사용하여 answer 객체를 순회하면 val은 [key, value] 형태의 배열이 되어 결과적으로 배열로 반환된다.
• for...of 반복문은 ES6에서 도입된 새로운 반복문으로, 반복 가능한(iterable) 자료구조에 사용. 배열, 문자열, Map, Set 등과 같이 iterable한 자료구조에만 사용할 수 있다. (객체의 속성들을 순회하지 않음)

Iterable | JavaScript로 만나는 세상

 

2) 자바스크립트에서 해시 테이블은 Object, Map(), Set()를 이용해 유사하게 사용 가능하다.

일반 객체와 Map(), Set()의 차이점은 순서를 보장할 수 있고 순회가 편리하다, size를 알 수 있다는 점이 큰 것 같다.

보통 단순하고 간략한 작업은 Set()을 이용해서 간단히 처리 가능하고, 복잡한 작업일 경우 Map()을 사용하면 편리하다.

Set은 value의 중복을 허용하지 않고, Map은 key의 중복을 허용하지 않고 value의 중복은 허용된다.

해시 테이블의 사용 쓰임이자 목적은 대부분 1. 중복 제거와 2. 값을 빠르게 찾기 위해 유용하게 쓸 수 있을 것 같다는 생각이 든다.

 

3)❗그렇다면 자바스크립트 객체는 해시 테이블일까? 객체는 곧 해시 테이블인가? 라는 의문이 들었다.

자바스크립트 객체는 해시 테이블과 유사한 방식으로 구현되어 있지만, 엄밀히 말하면 자바스크립트 객체는 해시 테이블이 아니다. 자바스크립트 엔진은 객체의 속성을 관리하기 위해 해시 테이블과 비슷한 데이터 구조를 사용하지만, 내부적인 동작 방식과 최적화된 구현은 엔진마다 다를 수 있다.

ECMAScript 2015(ES6)부터 도입된 Map, Set, WeakSet, WeakMap과 같은 데이터 구조들은 해시 테이블을 기반으로 구현되었다. 이러한 데이터 구조들은 객체보다 다양한 용도로 사용할 수 있으며, 특히 키-값 쌍을 저장하고 검색하는 데에 더 효율적이다. V8 엔진의 경우 키를 저장하는 방식에 대한 최적화 사항을 개선하여 성능을 높였다는 것이 언급되어 있다.

따라서 자바스크립트 객체와 해시 테이블 사이에는 유사성이 있지만 완전히 같지는 않으며, ECMAScript 2015에서 도입된 데이터 구조들은 내부적으로 해시 테이블을 사용하여 구현되었다.

MDN에 따르면 데이터 크기가 크거나, entry들을 추가하거나 삭제하는 빈도가 더 높을 수록 object보다 Map을 사용하는 것이 좋다. 위의 상황에서는 object보다 Map이 더 나은 성능을 보이기 때문이다. 그 외에도 Map은 직접 iteration이 가능하다는 점, key order를 갖는다는 점 size를 알 수 있다는 점 등 이점이 많다.

+ V8엔진 공식문서 hash table관련 문서

Optimizing hash tables: hiding the hash code · V8

 

4) 암호화에도 사용되는 해시 함수

[자료구조] 해시테이블 with JavaScript