# 7. 딕셔너리와 해시

정의

집합과 마찬가지로 유일한 값을 저장하기 위한 자료구조입니다. 집합이 원소의 값에 초점을 두었다면, 딕셔너리(Map)은 값을 [key, value] 형태로 저장합니다. 해시 역시 [key, value]으로 저장하지만 자료 구조를 구현하는 방법이 조금 다릅니다.

딕셔너리

Map, 딕셔너리는 데이터를 [key, value] 쌍으로 담아두는 자료구조로 key는 원소를 찾기 위한 식별자가 됩니다. 집합이 [key, key], 딕셔너리가 [key, value]를 모아놓은 공간이라는 점에서 두 자료구조는 비슷합니다. Set과 마찬가지로 ES6에는 Map 클래스에 대한 구현 명세가 수록되어 있습니다.

형태

class Map {
  constructor() {
    this.items = {};
  }
  
  has(key) {
    return key in this.items;
  }
  
  set(key, value) {
    this.items[key] = value;
  }
  
  remove(key) {
    if(this.has(key)) {
      delete this.items[key];
      return true;
    }
    return false;
  }
  
  get(key) {
    return this.has(key) ? this.items[key] : undefined;
  };
  
  getItems() {
    return this.items;
  }
  
  clear() {
    this.items = {};
  }
  
  size() {
    return Object.keys(this.items).length;
  }
  
  keys() {
    return Object.keys(this.items);
  }
  
  values() {
    var values = [];
    for (var k in this.items) {
      if ( this.has(k)) {
        values.push(this.items[k]);
      }
    }
    return values;
  }    
}

해시 테이블

해싱은 자료구조에서 특정 값을 가장 신속하게 찾는 방법이다. 반복문을 실행하여 해당 값을 확인하여 찾는 거 보다 해시 함수는 어떤 키에 해당하는 값의 주소를 테이블에서 찾아주는 함수로 조회 속도가 매우 빠르고 간단합니다. 가장 흔한 형태의 해시 함수는 '루즈 루즈(lose lose)해시 함수' 라고 하는데 키를 구성하는 문자의 아스키 코드 값을 단순히 더한 것 입니다.

key	Hash Func	Hash value	Hash Table
Gandalf	71+97+110+100+97+108+102	685
...	...	...	[399]johnsnow@email.com
John	74+111+104+110	399
...	...	...	[645]tyrion@email.com
...	...	...	[685]gandalf@email.com
Tyrion	84+121+114+105+111+110	645

해시 테이블 만들기

자료구조는 우선 배열을 활용하여 나타낸다.

class HashTable {
  constructor() {
    this.table = [];
  }

  loseloseHashCode(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37;
  }

  put(key, value) {
    let position = this.loseloseHashCode(key);
    console.log(`${position} - ${key}`);
    this.table[position] = value;
  }

  get(key) {
    return this.table[this.loseloseHashCode(key)];
  }

  remove(key) {
    this.table[this.loseloseHashCode(key)] = undefined;
  }
}

let hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrino@email.com');
// '19 - Gandalf'
// '29 - John'
// '16 - Tyrion'
console.log(hash.get('Gandalf'));
console.log(hash.get('Loiane'));
// 'gandalf@email.com'
// undefined
hash.remove('Gandalf');
console.log(hash.get('Gandalf'));
// undefined

해시 테이블과 해시 집합 비교

해시 집합은 집합의 모습을 하고 있지만, 원소의 삽입/삭제나 접근 시 해시 함수를 이용합니다. key-value가 아닌 value 값만 넣는다는 것이 다릅니다. 유일한 값, 비 반복적인 값을 저장한다는 특징은 해시 집합이나 집합이나 동일합니다.
ex) 영어 사전은 표제어만 모두 해시 집합에 넣을 수 있습니다. '표제어'란 문서의 최상단에 표시되는 제목을 뜻합니다

해시 테이블 간 충돌 해결

key는 다른데 value가 같은 경우가 있습니다. HashTable 인스턴스에서 동일한 인덱스에는 다른 값이 들어 있어야 하기 때문에 이를 충돌이라고 합니다.