해시테이블

Hash Table이란 해시함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말합니다.

해시테이블은 어떤 특정한 값을 받아 해시 함수에 넣고 해시함수는 출력값을 인덱스 삼아서 데이터를 저장합니다.

해시 함수를 이용해서 key를 hash value로 매핑하고 이 hash value를 index 삼아서 slot(bucket)에 저장되는 형태입니다.
해시함수는 입력이 같으면 무조건 같은 출력을 보여줍니다.
해시함수의 대표적인 예 : SHA

하지만 hash함수에도 단점이 존재하는데 고정된 길이로 출력되기 때문에 입력값이 다르더라도 같은 결과값이 나오기도 합니다 이를 해시 충돌이라고 합니다.
충돌을 완화 하기 위해서는

해시테이블 크기를 고정하고 빈곳을 잘찾거나 분리 연결법으로 연결리스트 형태로 만들어서 크기를 유연하게 만드는 방법이 있습니다.

그러다보니 결국 충돌로 인해 연결리스트를 탐색하게되면 최악의 경우 O(n)이 될 수도 있습니다.

그리고 Map과 Object가 이런 형태로 되어있다고 합니다.

시작

ES6에서 map과 set이 새로 도입되었습니다.
맵은 키와 값을 연결한다는 점에서 객체와 비슷하고, 셋은 중복을 허용하지 않는 점만 제외하면 배열과 비슷합니다.

ES6 이전에는 키와 값을 연결하려면 객체를 사용해야 했습니다. 하지만 객체를 이런 목적으로 사용하면 여러가지 단점이 생깁니다.

1. 프로토타입 체인 때문에 의도치않은 연결이 생길 수 있습니다.

2. 객체 내의 키 값 쌍의 개수를 알아내기 복잡합니다.

Object.values(객체).length

3. 키는 반드시 문자열이나 심볼이어야 하므로 객체나 함수를 포함한 다른 자료형이 프로퍼티의 키로 쓰일 수 없습니다.

const obj = {
    1 : 'one'
}
obj.1 // Uncaught SyntaxError: Unexpected number

되는데요?

const obj = {
    1 : 'one'
}
obj[1] // 'one'

잘 되는것처럼 보이는 이유는 프로퍼티 키에 문자열이나 symbol 값 이외의 값을 지정하면 암묵적으로 문자열 타입으로 변환되기 때문입니다.

객체는 프로퍼티 순서를 전혀 보장하지 않습니다.

이건 진짜 되는데요?

const obj = {}
obj.name = 'jiwon';
obj.age = 26;
obj.sex = 'male';
for (let i in obj){
    console.log(i);
    console.log(obj[i]);
}
// name
// jiwon
// age
// 26
// sex
// male

ES2015 이후로 속성의 순서를 특정 규칙을 기반으로 정의하는 메소드가 있고, 특정 경우를 제외하고는 시간순으로 정의됩니다. 객체 내 property의 순서는 포함되어있는 property와 값의 타입에 의존합니다.

순서 보장은 간단하게만 확인하고 넘어가자면

#case 1.

const objWithIndices = {
  23: 23,
  '1': 1,
  1000: 1000
};

for (let i in objWithIndices){
    console.log(i, objWithIndices[i]);
}

정수 인덱스인 모든 속성은 전체 개체 속성 순서에서 먼저 나타나고 순서대로 정렬 됩니다.

#case 2.

Object.getOwnPropertyNames(), Reflect.ownKeys() 는 for...in 반복문 (또는 Object.keys())이 처리되는 순서와 일치합니다

Symbol과 String으로된 key는 JS엔진 구현에 따라 내엔진 내부적으로 순서를 정의해주지만 JS 공식 문서상에서도 arbitrary하다고 명시되어있습니다.

암튼 정수형 인덱스와 혼합된 객체의 순서 보장문제

그리고 delete 의 cross-browser issue 때문에 순서 보장을 원하면 Map을 쓰고 순회하는 것을 권장하고 있습니다.

Map과 Object의 set Performance 비교

Map

Map에는 아래와 같은 주요 메서드와 프로퍼티를 가지고 있습니다.

• new Map()

const map = new Map();

맵을 생성합니다.

• map.set(key, value)

map.set('1', 'one');
map.set(2, 'two');
map.set(false, 'zero');

key를 이용해서 value를 저장합니다.

• map.get(key)

console.log(map.get('1'));	//one
console.log(map.get(2));	//two
console.log(map.get(false));//zero

key에 해당하는 값을 반환합니다. 해당하는 key가 존재하지 않으면 undefined를 반환합니다.

• 그 외

map.has(key)

console.log(map.has(2));	//true
console.log(map.has(1));	//false

key가 존재하면 true, 존재하지 않으면 false를 반환
map.delete(key)

console.log(map.has(2));	//true
map.delete(2);
console.log(map.has(2));	//false

key 값에 해당하는 값을 삭제

map.clear()

맵 안의 모든 요소 제거

map.size()

console.log(map.size); // 2
map.clear();
console.log(map.size); // 0

요소의 개수를 반환합니다.

WeakMap

WeakMap은 다음 차이점을 제외하면 Map과 완전히 같다.

• 키는 반드시 객체여야 합니다.
• WeakMap의 키는 가비지 콜렉션에 포함될 수 있습니다.
• WeakMap은 이터러블이 아니며 clear() 메서드도 있습니다.

일반적으로 자바스크립트는 코드 어딘가에서 객체를 참조하는 한 그 객체를 메모리에 계속 유지합니다. 예를 들어 map의 키인 객체 obj가 있으면 자바스크립트는 map이 존재하는 한 o를 계속 메모리에 유지합니다. 하지만 WeakMap은 그렇지 않습니다. 따라서 이터러블이 될 수 없습니다. 가비지 콜렉션중인 객체를 노출할 위험이 너무 크기 때문입니다.

let person = { name: "jiwon" };

let map = new Map();
map.set(person, "hi");

person = null;

for(let obj of map.keys()){
  console.log(obj);
}

console.log(map.size);

예제를 보면 지금 person이 null을 참조해도 map의 key로 사용되기 때문에 카비지 컬렉터의 대상ㅇ이 안되고 있습니다.
keys를 통해 해당 값을 가져오는 것도 가능합니다.

let person = { name: "jiwon" };

let map = new WeakMap();
map.set(person, "hi");

person = null;

for(let obj of map.keys()){
  console.log(obj);
}

console.log(map.size);

그러나 WeakMap은 그렇지 않습니다.
person이 null이 되는 순간 person을 나타내는 객체는 메모리에서 지워집니다.

때문에 이런 특징으로 인해 객체 인스턴스 전용 키를 저장하기에 알맞습니다.

Set

Set은 중복을 허용하지 않는 값을 모아놓은 특별한 컬렉션 입니다.
키가 없는 값이 저장됩니다.
셋의 장점은 아주 단순합니다. 추가하려는 것이 set에 이미 있다면 아무일도 일어나지 않습니다.

set의 주요 메서드는 다음과 같스빈다.
new Set(iterable)

• 이터러블 객체를 전달받으면 그 값을 복사해서 셋에 넣어줍니다.

set.add(value)

• 값을 추가하고 set자신을 반환합니다.

set.delete(value)

• 값을 제거합니다. 호출 시점에 셋 내에 값이 있어서 제거에 성공하면 true를 아니면 false를 반환합니다.

set.has(value)

• 셋 내에 값이 존재하면 true를 아니면 false를 반환합니다.

set.clear()

• map.clear()처럼 set을 비웁니다.

set.size

• set에 값이 몇개 있는지 세어줍니다.

const visitor = new Set();

const jiwon = {name:'park jiwon', id: '1q2w3e4r'};
const jitwo= {name:'park jiwon', id: '1q2w3e4r'};
const jithree = {name:'park jiwon', id: 'qwerqwer'};


const dog1 = 'choco';
const dog2 = 'choco';
const dog3 = 'cream'

visitor.add(jiwon);
visitor.add(jitwo);
visitor.add(jithree);
visitor.add(dog1);
visitor.add(dog2);
visitor.add(dog3);

console.log(visitor.size);

WeakSet

WeakSet도 Set과 유사합니다. 하지만 객체만 저장할 수 있다는 점이 다릅니다. 원시값은 저장할 수 없습니다.
Set 내의 객체는 도달 가능할 때만 메모리에서 유지됩니다. 즉 가비지 컬렉션의 대상이 됩니다.

Set 의 메소드 중 size나 keys()처럼 반복작업 관련 메서드는 사용할 수 없습니다.

WeakMap과 마찬가지로 이터러블이 아니므로 용도는 매우적고 실제로는 객체가 셋안에 존재하는지 안하는지를 알아보는 것 뿐이라고 해도 과언이 아닙니다.

const visitor = new WeakSet();

let jiwon = {name:'park jiwon', id: '1q2w3e4r'};
let jitwo= {name:'park jiwon', id: '1q2w3e4r'};
let jithree = {name:'park jiwon', id: 'qwerqwer'};
let tom = {name:'tom', id:'12341234'};

visitor.add(jiwon);
visitor.add(jitwo);
visitor.add(jithree);

console.log(visitor.has(jiwon)); //true

console.log(visitor.has(tom)); //false

출처 및 참조

• https://www.stefanjudis.com/today-i-learned/property-order-is-predictable-in-javascript-objects-since-es2015/
• https://jsdev.kr/t/loop/5457/2
• https://medium.com/@wdjty326/javascript-es6-map-vs-object-performance-%EB%B9%84%EA%B5%90-7f98e30bf6c8