JavaScript Set 내 맘대로 구현하기

 

서론

Symbol을 학습하면서 iterator 부분을 직접 코드로 작성해보고 싶어졌다.

그래서 간단한 Set을 직접 구현해서 iterator을 적용해봐야지 했다.

 

iterator 부분은 금방 구현했다. 하지만 Set을 JavaScript의 Set과 최대한 비슷하게 만들고 싶었는데 그 부분이 잘 안됐다.

갑자기 이상한 곳에 꽂혀서 이래저래 삽질한 과정을 글로 남겨보려고 한다.

 

 

자료구조로서의 Set

Set은 자료구조로서 비단 JavaScript에만 존재하는 개념은 아니다.

 

간단히 정리해 Set은 다음과 같은 특성을 갖는 자료구조이다.

1. 보관된 값들에 순서가 존재하지 않는다.
2. 각 값들은 중복되지 않는다.
3. 값의 존재 여부를 파악함에 용이하다.

Javascript에서의 Set을 간단하게 직접 구현해보기로 하자. (제대로 된 구현이 아닐 확률이 높다 ㅎㅎ)

 

구현 목표

interface ISet {
  get(element: unknown): unknown | undefined;
  has(element: unknown): boolean;
  add(element: unknown): void;
  forEach(callback: (element: unknown) => void): void;
}

 

 

위와 같이 Set의 인터페이스를 먼저 정의했다.

간단한 구현이기 때문에 remove, clear, size 같은 메서드들은 구현하지 않기로 했다.

 

최종적인 목표는 다음과 같이 정하게 되었다.

• 위의 4가지 메서드를 구현한다.
• constructor로부터 iterable을 받아 Set의 초기값으로 설정이 가능하다.
• Set 자체도 iterable한 객체로 만든다.
  • spread 연산자와 for ... of 문을 사용가능하게 한다.
• 어떤 값이던 넣을 수 있다.

---

시작하자마자 문제 발생

처음에는 간단하게 생각했다.

class MySet {
    items = {};

    has(item) {
    	return this.items.hasOwnProperty(item);
    }
    add(item) {
    	if (this.has(item)) return;
        this.items[item] = item;
    }
}

위의 코드처럼 items라는 객체를 내부적으로 관리하며 key와 value를 같은 값으로 두어 바로 접근이 가능한 구조를 생각했다.

 

이렇게 작성했을 때 간단한 경우는 문제 없이 동작한다.

 

하지만 다음의 코드를 확인해보자.

const s = new MySet();

s.add(1);
s.add('1');

s.add({ foo: 'bar' });

위와 같이 Set 안에 데이터를 추가했을 때 문제가 발생하게 된다.

1과 '1'은 다른 값이지만 Set 안에는 '1' 값 하나만 존재하고 { foo: 'bar' } 을 add하려고 할 때 에러가 발생할 것이다.

 

문제가 발생하게 되는 원인은 아래와 같다.

1. 객체의 키값으로서 1과 '1'은 같다.
2. 객체는 어떤 객체의 키 값이 될 수 없다.

이는 객체의 키 값에는 문자형의 타입(정확히는 string, symbol) 만 사용될 수 있기 때문이다.

 

즉, s.add(1)의 경우 1은 number 타입이기 때문에 string으로 형변환이 되어 items['1'] = 1 과 같은 형태가 되었을 것이다.

이는 의도치 않은 동작이다.

 

또한 객체를 고유하게 식별할 수 있는 장치가 없기에 

 

따라서 구현의 방식 자체를 다르게 생각해야 했다.

---

해결 과정

기본적인 구조는 그대로 가져가되 케이스를 나눠보기로 했다.

 

1. 키 값으로 바로 사용 가능한 타입(string) symbol은 우선 제외하고 생각했다...
2. 형변환이 필요한 타입(number, boolean, null, undefined)
3. 추가적인 식별자가 필요한 타입(object like)

1번의 경우 앞의 구조와 같이 s.add('Hello')를 실행했을 때 items = { 'Hello': 'Hello' } 로 쉽게 해결할 수 있다.

 

2번의 경우 형변환되었을 때 같은 값으로 오인하는 부분을 제어하기 위해 따로 처리한다.

true - 'true', 1 - '1' 과 같은 경우를 말하는 것이다.

 

3번의 경우 참조형 객체를 식별하기 위한 장치가 필요하기에 따로 처리한다.

 

---

 

형변환이 필요한 타입

이 타입의 값들을 key로 사용하려면 형변환이 필요하다.

하지만 형변환이 일어났을 때 기존의 string 타입의 key와 겹칠 경우 문제가 생기기 때문에 따로 관리해야한다고 생각했다.

 

처음에는 형변환이 필요한 타입의 값들만 관리하는 추가적인 객체를 만들까 했다.

그러다가 최근에 학습했던 Symbol이 생각났다.

 

Symbol과 전역 심볼 영역 을 활용하면 겹치는 문제 없이 해결할 수 있을 것 같았다.

형변환이 필요한 타입의 값은 Symbol.for 메서드를 활용해 전역심볼영역의 심볼로 변환해 그 심볼을 key값으로 사용한다.

Symbol()이 아닌 Symbol.for()을 사용하는 이유는 Symbol(true) === Symbol(true) 을 콘솔에 입력해보면 알게 될 것이다.

 

즉, 다음과 같은 구조가 될 것이다.

(실제 코드와는 다르다.)

const castedKey = Symbol.for(true);
// Symbol.for의 인자로 제공된 true는 'true'로 형변환됨

items = {
	[castedKey]: true,
	'true': 'true'
}

 

이렇게 하면 우선... 값이 같지만 타입이 다른 요소에 대한 key 값 문제를 해결할 수 있다.

 

 

---

추가적인 식별자가 필요한 타입

이 부분이 해결하는 데 가장 어려웠다.

객체는 key 값으로 사용할 수 없다 ▶︎ 고유한 식별자가 필요하다 ▶︎ 식별자는 어떻게 고유할 수 있을까? ▶︎ 식별자는 객체로부터 얻을 수 있어야하고 같은 객체면 같은 식별자여야한다. ▶︎ 어떻게 만들지?

처음에는 객체를 해싱하는 방식을 떠올렸다.

하지만 내가 원하는 결과물을 얻기는 힘들어보였다.

const s = new Set();
const v = { foo: 'bar' };

s.add(v);
s.add({foo: 'bar'});

// 내가 원한 것:: Set안에는 v { foo: 'bar' }와 { foo: 'bar' }가 있어야함.

// 하지만, Set 안에는 { foo: 'bar' } 밖에 없게 됨
// hash(v) === hash({ foo: 'bar' }) 이기 때문에 ... 어려워보임

 

 

이런저런 고민을 해보다가 답을 찾지 못하고 있었는데, [여기]서 힌트를 얻을 수 있었다!

굳이 링크를 들어가볼 필요는 없다.

 

요약하자면 객체 안에 고유한 식별자 필드를 직접 추가하는 것이다.

객체가 자체적으로 고유한 식별자를 가지고 있고 이 식별자를 우리의 Set items의 key값으로 사용하는 것이다.

즉, 해당 객체가 Set에 이미 있는 item인가를 판별하려면 해당 객체의 식별자가 items의 key값으로 존재하는 지 비교해보면 된다.

 

그럼 이 식별자를 어떻게 추가하면 좋을까?

add(element) {
	element.uniqueId = 1234;
	this.items.uniqueId = element;
}

가장 간단한 방법으로 보이기는 한다.

하지만 uniqueId라는 필드를 elemnt와 this.items에 직접 부여하는 건 위험이 크다고 생각된다.

• Set 외부에서 element의 uniqueId를 쉽게 변경/조회할 수 있다.
• element라는 객체가 원래 uniqueId라는 필드를 가지고 있을 수도 있다.
• Set.add('uniqueId') -> Set.add(1234) 를 수행하면 값이 덮어쓰일 것이다.

기존 속성에 영향을 주지 않으며 숨김처리된 속성… 을 생각해보니 심볼을 다시 적용해볼 수 있을 것 같다.

• 객체의 고유한 식별자에 대한 심볼인 UNIQUE_SYMBOL을 미리 생성해둔다.
• 이 UNIQUE_SYMBOL을 Set 안에 추가하고자 하는 객체의 속성으로 정의한다.
• (Symbol.for(식별자) - UNIQUE_SYMBOL이 추가된 원본 객체) key-value쌍을 this.items에 추가한다.

위와 같은 플로우로 MySet의 items와 그 안에 있는 item 들에 대해 새롭게 정의한 타입은 다음과 같다.

const UNIQUE_SYMBOL = Symbol.for('__unique');

type TSetItems = {
	[key: symbol]: TSetItem;
}

type TSetItem = {
	[UNIQUE_SYMBOL]?: string;
    // 이 string이 객체의 고유식별자
}

 

이를 바탕으로 add, has 함수를 다시 정의했다.

식별자를 만들기 위한 id 값은 그냥.. 간단하게 만들어서 사용했다. 이 부분이 중요하진 않다고 생각해서.

(실제 코드는 element의 타입에 따른 조건부 처리가 되어 있어 조금 더 복잡하다. 조건 처리부분은 밑의 코드에선 제외했다.)

const UNIQUE_SYMBOL = Symbol.for('__unique');

const generateId = (function () {
	let uniqueNumber = 1;
	const prefix = "__unique-";
    
	return () => prefix + uniqueNumber++;
})();

class MySet {
 // .... 
  add(element) {
    if (this.has(element)) return;

    const generatedKey = generateId();
    Object.defineProperty(element, UNIQUE_SYMBOL, {
      value: generatedKey,
    });

    Object.defineProperty(this.#items, Symbol.for(generatedKey), {
      value: element,
    });
  }
  
  has(element) {
    const key = Symbol.for(element[UNIQUE_SYMBOL]);
    return this.items.hasOwnProperty(key);
  }
}

 

위의 코드를 토대로 

1. 키 값으로 바로 사용 가능한 타입(string)
2. 형변환이 필요한 타입(number, boolean, null, undefined)
3. 추가적인 식별자가 필요한 타입(object like)

이 3가지에 경우 맞게 코드를 조금씩 수정하여 문제를 해결할 수 있었다.

---

간단하게 도식화

s.add({ foo: 'bar' })

s.add(true) // boolean

s.add('true') // string

s.add({ foo: 'bar' }) // 새로운 객체이기에 중복으로 인식되지 않음.

---

결론

이런 저런 고민을 하면서 Set을 직접 구현해가는 과정을 글로 정리해보았다.

모든 코드를 글로 담기엔 어려워 일부만 요약해서 담았다.

 

막상 다 만들고 나니까 이게 무슨 혼종인가? 싶기도 하다.

hash function과 해싱 쪽을 조금 더 고민했다면 더 좋은 답이 나올 수도 있지 않았을까하는 생각이 든다.

 

혹시 코드가 궁금한 사람이 있다면 아래의 Github 링크를 통해 확인하실 수 있다!

https://github.com/KimKwon/frontend-basic/blob/main/content/Set/index.ts

GitHub - KimKwon/frontend-basic: FE, JS 관련 지식을 정리해요.

실제로 사용하기 위함도 아니고 학습 목적으로 이런저런 삽질을 한 코드이다.

즉, 엄청나게 구린 코드일 수도 있다는 것이다!

그러니 이 글을 보시는 분들은 그냥 이런 삽질을 하는 사람도 있네 정도로만 보고 넘어가시길 바란다 :)

 

틀린 부분이나 문제가 될 부분이 있다면 언제든 말씀해주세요!