딕셔너리와 해시는 집합처럼 유일한 값(반복되지 않는 값)을 저장하기 위한 자료구조이다.

집합이 원소의 값에 초점을 두었다면 딕셔너리는 값을 [키,값] 형태로 저장한다.

해시 역시 [키,값]으로 저장하지만 자료 구조를 구현하는 방법이 조금 다르다.

딕셔너리

딕셔너리는 데이터를 [키,값]쌍으로 담아두는 자료 구조로, 키는 원소를 찾기 위한 식별자다.

집합이 [키,키], 딕셔너리가 [키,값]형태의 원소를 모아놓는 공간이라는 점에서 두 자료 구조는 비슷하다.

딕셔너리는 맵이라고도 한다.

딕셔너리 만들기

function Dictionary() {
  var items = {};
}

딕셔너리/맵에서 사용할 메소드 목록이다.

set() : 딕셔너리에 원소를 추가 remove() : 키에 해당하는 원소를 삭제 has() : 키에 해당하는 원소가 딕셔너리에 존재하면 true를 아니면 false를 반환 get() : 키에 해당하는 원소의 값을 반환 clear() : 모든 원소를 삭제 size() : 원소의 개수를 반환 keys() : 딕셔너리의 모든 키를 배열로 반환 values() : 딕셔너리의 모든 값을 배열로 반환

has와 set 메서드

this.has = function(key) {
  return key in items;
};
this.set = function(key, value) {
  items[key] = value;
};

Set의 has와 완전히 일치한다. 자바스크립트 in 연산자로 items에 key가 있는지 체크한다.

key와 value를 인자로 받아 items에 [key,value] 형태로 원소를 세팅하는 메서드로, 새로운 원소를 추가하거나 기존 원소를 수정할 수 있다.

remove 메서드

remove 역시 value 대신 key로 원소를 찾는다는 것만 다르고 나머지는 Set과 같다.

this.remove = function(key) {
  if (this.has(key)) {
    delete items[key];
    return true;
  }
  return false;
};

items에서 key 키를 가진 원소를 찾아 삭제한다.

get과 values 메서드

딕셔너리에서 어떤 원소를 찾아 그 값을 알고 싶을 때 다음과 같이 구현한다.

this.get = function(key) {
  return this.has(key) ? items[key] : undefined;
};

get 메서드는 찾는 원소가 실제로 존재하는지 확인해서 있으면 그 값을 없으면 undefined를 반환한다.

this.values = function() {
  var values = [];
  for (var k in items) {
    if (this.has(k)) {
      values.push(items[k]);
    }
  }
  return values;
};

items의 원소들을 차례로 순회하면서 has 메서드로 key 키에 해당하는 원소가 있는지 확인하고 있으면 그 값을 values 배열에 넣는다.

순회에 끝나면 values 배열을 반환한다.

clear, size, keys, getItems 메서드

this.getItems = function() {
  return items;
};

해시 테이블

Dictionary 클래스의 해시 구현이라고 할 수 있는 HashTable 클래스(HashMap)이다.

해싱은 자료 구조에서 특정 값을 가장 신속하게 찾는 방법이다.

어떤 값을 찾으려면 전체 원소에 대해 루프문을 실행했는데 해시 함수는 어떤 키에 해당하는 값의 주소를 테이블에서 찾아주는 함수 이므로

조회 속도가 매우 빠르고 간단하다.

해시 테이블 만들기

function HashTable() {
  var table = [];
}

다음 세가지 기본 메서드를 구현한다.

put(키,값) : 원소를 추가 remove(키) : 키에 해당하는 원소를 찾아 삭제 get(키) : 키에 해당하는 원소를 찾아 그 값을 반환

이를 구현하기 전에 해시 함수를 구현해야 한다.

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

key를 구성하는 각 문자의 아스키 값을 합하는 함수다.

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

key를 해시 함수에 넣고 반환된 결과 값을 테이블에서 찾아야한다.

table 배열의 position 인덱스에 value를 추가한다.

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

HashTable은 ArrayList 처럼 table 배열의 원소 자체를 삭제할 필요가 없다.

배열 전체에 원소들이 고루 분포되어 있으므로 어떤 인덱승네 값이 할당되지 않은채 기본 값 undefined가 들어 있다.

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

해시 테이블은 해시 맵과 동일한 자료구조다.

해시 집합(HashSet)은 집합의 모습을 하고 있지만 원소의 삽입/삭제나 접근시 해시 함수를 이용한다.

키-값 쌍이 아닌 값만 넣는다는것이 다르다.

비반복적인 값을 저장한다는 특징은 동일하다.

해시 테이블 간 충돌 해결

키는 다르다 값이 동일한 경우가 있다.

HashTable 인스턴스에 동일한 인덱스에는 다른 값이 들어 있어야 하기 때문에 이를 충돌이라고 한다.

Jonathan, Jamie, Sue는 동일한 해시 값 5를 갖고 있다. Sue를 제일 마지막에 추가했기 떄문에 5의 자리에 남게 된 것이다.

넣은 값이 사라져버리는 자료 구조는 있을 수 없으므로 모든 원소가 포함되게 하려면 충돌이 발생했을 때 어떤 특별한 처리를 해줘야 한다.

이러한 처리 방법으로 체이닝, 선형 탐사, 이중 해싱 세 가지가 있다.

체이닝

체이닝은 테이블의 인덱스 별로 연결 리스트를 생성해 그 안에 원소를 저장하는 기법이다.

충돌을 해결하는 가장 단순한 방법이고, HashTable 인스트스 외에 메모리가 추가적으로 소용된다는 단점이 있다.

체이닝과 선형 탐사법에서는 put,get, remove 메소드를 재정의해야 하고, 방법에 따라 구현 코드는 달라진다.

우선 체이닝 기법으로 구현하려면 LinkedList에서 원소를 새로운 헬퍼 클래스로 표현해야한다.

이 클래스를 ValuePair 라고 명명하고 HashTable 내에 구현한다.

var ValuePair = function(key, value) {
  this.key = key;
  this.value = value;
  this.toString() = function() {
    return `[${this.key}-${this.value}]`;
  };
};

put 메서드

this.put = function(key, value) {
  var position = loseloseHashCode(key);
  if (table[position] == undefined) {
    table[position] = new LinkedList();
  }
  table[position].append(new ValuePair(key, value));
};

새 원소가 들어갈 위치에 이미 다른 원소가 차지하고 있는지 확인한다.

없다면 새로운 LinkedList 인스턴스를 생성한다.

get 메서드

this.get = function(key) {
  var position = loseloseHashCode(key);
  if (table[position] !== undefined) {
    var current = table[position].getHead();
    while (current.next) {
      if (current.element.key === key) {
        return current.element.value;
      }
      current = current.next;
    }
    if (current.element.key === key) {
      return current.element.value;
    }
  }
  return undefined;
};

먼저 원소의 존재 여부를 확인하고 없는 원소면 undefined를 반환한다.

원소가 있으면 LinkedList 인스턴스이므로 순회하면서 원소를 찾는다.

remove 메서드

this.remove = function(key) {
  var position = loseloseHashCode(key);
  if (table[position] !== undefined) {
    var current = table[position].getHead();
    while (current.next) {
      if (current.element.key === key) {
        table[position].remove(current.element);
        if (table[position].isEmpty()) {
          table[position] = undefined;
        }
        return true;
      }
      current = current.next;
    }
  }
  if (current.element.key === key) {
    table[position].remove(current.element);
    if (table[position].isEmpty()) {
      table[position] = undefined;
    }
    return true;
  }
  return false;
};

LinkedList 인스턴스를 순회하면서 current가 찾는 원소라면 remove 메서드로 삭제한다.

만약 지운 연결리스트가 비어있다면 position 인덱스 자리는 undefined로 바꾼다.

성공적으로 삭제하면 true 아니면 false를 반환한다.

선형 탐색법

새 원소 추가 시 인덱스가 이미 점유된 상태라면 인덱스 + 1을 찾아보고 인덱스 + 1도 있다면 인덱스 + 2를 찾아보는 식으로 충돌을 피한다.

put 메서드

this.put = function(key, value) {
  var position = loseloseHashCode(key);
  if (table[position] !== undefined) {
    table[position] = new ValuePair(key, value);
  } else {
    var index = ++position;
    while (table[index] !== undefined) {
      index++;
    }
    table[index] = new ValuePair(key, value);
  }
};

먼저 해시 함수로 인덱스를 찾고 이 인덱스에서 다른 원소가 있는지 체크한다.

다른 원소가 없다면 ValuePair의 인스턴스를 넣는다

이미 들어간 상태라면 비어 있는 인덱스를 찾기 위해 index 변수를 만들어 position + 1을 한다.

그리고 다시 원소가 있는지 확인하고 있다면 index를 증가시켜 반복한다.

get 메서드

this.get = function(key) {
  var position = loseloseHashCode(key);
  if (table[position] !== undefined) {
    if (table[position].key === key) {
      return table[position].value;
    } else {
      var index = position + 1;
      while (table[index] === undefined || table[index].key !== key) {
        index++;
      }
      if (table[index].key === key) {
        return table[index].value;
      }
    }
  }
  return undefined;
};

먼저 키의 존재 여부를 판단한다 존재한다면 찾는 테이블의 인덱스의 키와 동일한지 비교하고 같다면 반환하면 된다.

아니라면 다음 위치를 반복해서 찾는다.

remove 메서드

remove 메서드는 get 메서드와 동일하다

if (table[index].key === key) {
  table[index] === undefined;
}

원소를 삭제하는 행위는 배열 값을 undefined로 바꾸는 것이다.

해시 함수 개선

좋은 해시 함수는 원소 삽입과 조회 속도가 빠르고 충돌 확률이 낮아야 한다.

var djb2HashCode = function(key) {
  var hash = 5381;
  for (var i = 0; i < key.length; i++) {
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
};