0516 - 0522

0516

Singleton 패턴

의도

싱글턴 패턴은 클래스에 인스턴스가 하나만 있는지 확인하는 동시에 이 인스턴스에 대한 전역 접근점을 제공한다.

문제점

싱글턴 패턴은 단일 책임 원칙을 위배하지만, 두 가지 문제를 동시에 해결한다

1. 클래스에 인스턴스가 하나만 있는지 확인한다.
2. 해당 인스턴스에 대한 전역 접근점을 제공한다.

클래스에 있는 인스턴스 수를 제어하려는 가장 일반적인 이유는 일부 공유 리소스(데이터베이스 또는 파일)에 대한 액세스를 제어하기 위한 것이다.

싱글턴 패턴의 동작 방식은 다음과 같다.
객체를 생성했지만 잠시 후 새 객체를 생성하기로 결정했다면, 새 객체를 받는 대신 이미 만든 객체를 받게 된다.
생성자 호출은 항상 새 객체를 의도적으로 반환해야 하므로, 이 동작은 일반 생성자로 구현할 수 없다.

다만 전역 변수와 마찬가지로 Singleton 패턴을 사용하면 프로그램의 어느 곳에서나 일부 객체에 액세스할 수 있다. 하지만 다른 코드가 해당 인스턴스를 덮어쓰지 않도록 보호해야 한다.

해결책

싱글턴의 모든 구현에는 다음 두 단계의 공통점이 있다.

• new 연산자로 싱글턴 클래스를 사용하지 못하도록 기본 생성자를 비공개로 설정한다.
• 생성자 역할을 하는 정적 생성 메서드를 만든다. 이 메서드는 private 생성자를 호출하여 객체를 만들고 정적 필드에 저장한다. 이 메서드에 대한 다음 호출은 캐시된 객체를 반환한다.

코드가 싱글턴 클래스에 액세스할 수 있는 경우 싱글턴의 정적 메서드를 호출할 수 있다. 따라서 해당 메서드가 호출될 때마다 항상 동일한 객체가 반환된다.

실세계와 유사한 사례

정부는 싱글턴 패턴의 훌륭한 예이다. 국가는 하나의 공식 정부만 가질 수 있기에 정부를 구성하는 개인의 신원에 관계없이 X의 정부라는 제목은 담당자 그룹을 식별하는 전역 접근점이다.

구조

1. 싱글턴의 클래스는 자체 클래스의 동일한 동일한 인스턴스를 반환하는 getInstance 정적 메서드를 선언한다. 싱글턴의 생성자는 클라이언트의 코드에서 숨겨져야 한다. 메서드를 호출하는 것이 싱글턴 객체를 가져오는 유일한 방법이어야 한다.

적용 가능성

• 프로그램의 클래스에 모든 클라이언트가 사용할 수 있는 단일 인스턴스만 있어야 하는 경우 싱글턴 패턴을 사용한다. 예를 들어, 프로그램의 다른 부분에서 공유하는 단일 데이터베이스 객체이다.
• 전역 변수를 더 엄격하게 제어해야 하는 경우 싱글턴 패턴을 사용한다.

장점과 단점

장점

• 클래스에 단일 인스턴스만 있음을 확인할 수 있다.
• 해당 인스턴스에 대한 전역 점근점을 얻는다.
• 싱글턴 객체는 처음 요청될 때만 초기화된다.

단점

• 단일 책임 원칙을 위배한다.
• 여러 스레드가 여러 번 단일 객체를 만들지 않도록 다중 스레드 환경에서 패턴을 특수 처리해야 한다.
• 단위 테스트하기 어렵다.

타입스크립트로 패턴 구현

많은 개발자가 싱글턴 패턴을 안티 패턴으로 간주한다. 그렇기에 타입스크립트 코드에서 사용이 감소한다.

class Singleton {
  private static instance: Singleton;

  private constructor() {}

  public static getInstance(): Singleton {
    if (!Singleton.instance) {
      Singleton.instance = new Singleton();
    }

    return Singleton.instance;
  }

  public someBudsinessLogic() {}
}

function clientCode() {
  const s1 = Singleton.getInstance();
  const s2 = Singleton.getInstance();

  if (s1 === s2) {
    console.log("Singleton works, both variables contain the same instance.");
  } else {
    console.log("Singleton failed, variables contain different instances.");
  }
}

clientCode();

실행 결과

0517

JS 복습

자바스크립트 특징

• 자바스크립트는 HTML, CSS와 함께 웹을 구성하는 요소 중 하나로 웹 브라우저에서 동작하는 유일한 프로그래밍 언어다.
• 개발자가 별도의 컴파일 작업을 수행하지 않는 인터프리터 언어다. 대부분의 모던 JS 엔진은 인터프리터와 컴파일러의 장점을 결합해 비교적 처리 속도가 느린 인터프리터의 단점을 해결했다. 하지만 JS는 런타임에 컴파일되며 실행 파일이 생성되지 않고 인터프리터 도움 없이 실행할 수 없기 때문에 컴파일러 언어라고 할 수는 없다.
• 자바스크립트는 명령형, 함수형, 프로토타입 기반 객체지향 프로그래밍을 지원하는 멀티 패러다임 프로그래밍 언어다.
• 타입을 사전에 정의하지 않는 동적 타이핑 언어

컴파일러 언어

• 코드가 실행되기 전 단계인 컴파일 단계에 소스코드 전체를 머신 코드로 변환한 후 실행한다.
• 실행 파일을 생성한다.
• 컴파일 단계와 실행 단계가 분리되어 있어 명시적인 컴파일 단계를 거치고, 명시적으로 실행 파일을 실행한다.
• 실행에 앞서 컴파일은 단 한번 수행된다.
• 컴파일과 실행 단계가 분리되어 있으므로 코드 실행 속도가 빠르다.

인터프리터 언어

• 코드가 실행되는 단계인 런타임에 문 단위로 한 줄씩 중간 코드인 바이트코드로 변환한 후 실행한다.
• 실행 파일을 생성하지 않는다.
• 인터프리트와 실행 단계가 분리되어 있지 않고, 한 줄씩 바이트코드로 변환하고 즉시 실행한다.
• 코드가 실행될 때마다 인터프리트 과정이 반복 수행된다.
• 인터프리트와 실행 단계가 분리되어 있지 않으므로 코드 실행 속도가 비교적 느리다.

스코프란

모든 식별자는 자신이 선언된 위치에 의해 유효한 범위, 즉 다른 코드가 변수 자신을 참조할 수 있는 범위가 결정되는데, 이를 스코프라고 한다.

식별자가 유효한 범위

• 자바스크립트 엔진이 식별자를 검색할 때 사용하는 규칙
• 스코프가 없다면 같은 이름을 갖는 변수는 충돌을 일으키므로 프로그램 전체에서 하나밖에 사용할 수 없다.

스코프 체인

• 스코프는 함수의 중첩에 의해 계층적 구조를 갖는다.
• 스코프가 계층적으로 연결된 것을 스코프 체인이라고 한다.
• 변수를 참조할 때 JS 엔진은 스코프 체인을 통해 변수를 참조하는 코드의 스코프에서 시작하여 상위 스코프 방향으로 이동하며 선언된 변수를 검색한다.

렉시컬 스코프

함수를 어디서 정의했는지에 따라 함수의 상위 스코프를 결정한다. 함수 정의가 평가되는 시점에 상위 스코프가 정적으로 결정되기 때문에 정적 스코프라 부른다. 함수가 호출된 위치는 상위 스코프 결정에 어떠한 영향도 주지 않는다.

생성자 함수

new 연산자와 함께 호출하여 인스턴스를 생성하는 함수.

객체 리터럴에 의한 객체 생성의 문제점

• 동일한 프로퍼티를 갖는 객체를 여러 개 생성해야 하는 경우 매번 같은 프로퍼티를 기술해야 하기 때문에 비효율적이다.
• 생성자 함수에 의한 객체 생성 방식은 프로퍼티 구조가 동일한 객체 여러 개를 간편하게 생성할 수 있다.

생성자 함수의 인스턴스 생성 과정

생성자 함수의 역할은 인스턴스를 생성하는 것과 생성된 인스턴스를 초기화 하는 것

1. 암묵적으로 빈 객체가 생성되고, this에 빈 객체가 바인딩 된다. 생성자 함수 내부의 this가 생성자 함수가 생성할 인스턴스를 가리키는 이유가 바로 이것이다.
2. 코드가 한 줄씩 실행되어 this에 바인딩되어 있는 인스턴스를 초기화한다.
3. 인스턴스가 바인딩된 this가 암묵적으로 반환된다.

constructor : 함수 선언문, 함수 표현식, 클래스
non-constructor : 화살표 함수, 메서드 축약표현

프로토타입

객체를 생성할 때, 일반적으로 프로퍼티의 값은 인스턴스마다 다르지만, 메서드는 모든 인스턴스가 동일한 내용의 메서드를 사용하므로 단 하나만 생성하여 모든 인스턴스가 공유해서 사용하는 것이 바람직하다. 모든 인스턴스가 동일한 메서드를 중복 소유하는 것은 메모리를 불필요하게 낭비하고, 인스턴스를 생성할 때마다 메서드를 생성하므로 퍼포먼스에 악영향을 준다. 자바스크립트에서는 프로토타입을 기반으로 상속을 구현한다.

• 생성자 함수가 생성할 모든 인스턴스가 공통적으로 사용할 프로퍼티나 메서드를 프로토타입에 미리 구현해 두면 인스턴스는 별도의 구현 없이 상위 객체인 프로토타입의 자산을 공유하여 사용할 수 있다.
• 프로토타입 객체는 생성자 함수가 평가되어 함수 객체를 생성하는 시점에 더불어 생성된다.
• 프로토타입을 상속받은 하위 객체는 상위 객체의 프로퍼티를 자신의 프로퍼티처럼 자유롭게 사용할 수 있다.
• 모든 객체는 [[prototype]]이라는 내부 슬롯을 가지며, 이 내부슬롯의 값은 프로토타입의 참조다.

프로토타입에서 상속을 구현하는 방법

• JS는 객체의 프로퍼티에 접근하려고 할 때 해당 객체에 접근하려는 프로퍼티가 없다면 [[Prototype]] 내부 슬롯의 참조를 따라 자신의 부모 역할을 하는 프로토타입의 프로퍼티를 순차적으로 검색한다.
• 이를 프로토타입 체인이라 한다. 프로토타입 체인은 자바스크립트가 객체지향 프로그래밍의 상속을 구현하는 메커니즘이다.

this 바인딩

this는 자신이 속한 객체 또는 자신이 생성할 객체를 가리키는 자기 참조 변수
this를 통해 자신이 속한 객체 또는 자신이 생성할 인스턴스의 프로퍼티나 메서드를 참조할 수 있다.
자바스크립트의 this는 함수가 호출되는 방식에 따라 this에 바인딩될 값이 동적으로 결정된다.

일반 함수 this 바인딩

일반 함수로 호출된 모든 함수 내부의 this에는 전역 객체가 바인딩된다.
-> 메서드 내에서 정의한 중첩 함수 또는 콜백 함수가 일반 함수로 호출될 때는 this가 전역 객체를 바인딩하는 것은 문제가 있다.

• 중첩 함수나 콜백 함수는 외부 함수를 돕는 헬퍼 함수의 역할을 하는데, 외부 함수인 메서드와 중첩 함수 또는 콜백 함수의 this가 일치하지 않는다.
• 이를 일치시키기 위해 두 가지 방법이 있다. Function.prototype.bind 메서드를 사용하거나, 화살표 함수를 사용한다.

메서드 this 바인딩

메서드로 호출된 함수 내부의 this에는 메서드를 호출한 객체가 바인딩된다.

생성자 this 바인딩

생성자 함수 내부의 this에는 생성자 함수가 생성할 인스턴스가 바인딩된다.

Function.prototype.call/apply/bind this 바인딩

Function.prototype.call/apply/bind 메서드는 첫 번째 인수로 전달한 특정 객체를 호출한 함수의 this에 바인딩한다.

• call/apply 메서드의 대표적인 용도는 arguments 같은 유사 배열 객체에 배열 메서드를 사용하는 경우
• bind 메서드의 대표적인 용도는 메서드 내부의 중첩 함수나 콜백 함수의 this가 불일치하는 문제를 해결

이벤트 핸들러 this 바인딩

이벤트를 바인딩한 DOM 요소를 가라킨다.

화살표 함수로 정의한 이벤트 핸들러 내부의 this는 상위 스코프의 this를 가리킨다. 화살표 함수는 함수 자체의 this 바인딩을 갖지 않는다.

0518

리액트 애플리케이션에 리덕스 적용

import { createStore } from "redux";
import rootReducer from "./modules";
import { Provider } from "react-redux";

const store = createStore(
  rootReducer,
  window.__REDUX_DEVTOOLS_EXTENSION__ && window.__REDUX_DEVTOOLS_EXTENSION__()
);

const root = ReactDOM.createRoot(document.getElementById("root"));
root.render(
  <Provider store={store}>
    <App />
  </Provider>
);

1. index.js에서 스토어를 생성하여 첫 번째 인자로 리듀서를 전달한다.
2. 두 번째 인자는 리덕스 tools를 사용하기 위해 전달하는 것이다.
3. 리액트 컴포넌트에서 스토어를 사용할 수 있도록 App 컴포넌트를 Provider 컴포넌트로 감싸 준다. store를 props로 전달해 주어야 한다.

스토어를 store/configureStore.js로 따로 빼서 구성에만 집중할 수도 있다.

컨테이너 컴포넌트 만들기

리덕스 스토어에 접근하여 원하는 상태를 받아 오고, 액션도 디스패치해 줄 컴포넌트

import { connect } from "react-redux";
import Counter from "../components/Counter";
import { decrease, increase } from "../modules/counter";

const CounterContainer = ({ number, increase, decrease }) => {
  return (
    <Counter number={number} onIncrease={increase} onDecrease={decrease} />
  );
};

const mapStateToProps = (state) => ({
  number: state.counter.number,
});
const mapDispatchToProps = (dispatch) => ({
  increase: () => {
    dispatch(increase());
  },
  decrease: () => {
    dispatch(decrease());
  },
});

export default connect(mapStateToProps, mapDispatchToProps)(CounterContainer);

• 컴포넌트를 리덕스와 연동하려면 connect 함수를 사용해야 한다.
• connect(mapStateToProps, mapDispatchToProps)(연동할 컴포넌트)
• mapStateToProps는 리덕스 스토어 안의 상태를 컴포넌트의 props로 넘겨주기 위해 설정하는 함수이다.
• mapDispatchToProps는 액션 생성 함수를 컴포넌트의 props로 넘겨주기 위해 사용하는 함수이다.
• 두 함수에서 반환하는 객체 내부의 값들은 컴포넌트의 props로 전달된다. 각각 스토어의 상태인 state와 스토어 내장 함수 dispatch를 파라미터로 받아 온다.
• connect를 호출하고 나면 또 다른 함수를 반환하는데, 여기에 컴포넌트를 파라미터로 넣어 주면 리덕스와 연동된 컴포넌트가 만들어 진다.
• connect 함수 내부에 익명 함수 형태로 선언해도 문제가 되지 않고, 오히려 코드가 깔끔해질수도 있다.

export default connect(
  (state) => ({
    number: state.counter.number,
  }),
  (dispatch) => ({
    increase: () => dispatch(increase()),
    decrease: () => dispatch(decrease()),
  })
)(CounterContainer);

액션을 디스패치하기 위해 각 액션 생성 함수를 호출하고 dispatch로 감싸는 작업이 번거로울 경우, 리덕스에서 제공하는 bindActionCreators 유틸 함수를 사용하면 간편하다.

export default connect(
  (state) => ({
    number: state.counter.number,
  }),
  (dispatch) =>
    bindActionCreators(
      {
        increase,
        decrease,
      },
      dispatch
    )
)(CounterContainer);

더 간편한 방법은 mapDispatchToProps에 해당하는 파라미터를 함수 형태가 아닌 액션 생성 함수로 이루어진 객체 형태로 넣어 주는 것이다.
이를 객체 형태로 넣어 주면 connect 함수가 내부적으로 bindActionCreators 작업을 대신해 준다.

export default connect(
  (state) => ({
    number: state.counter.number,
  }),
  {
    increase,
    decrease,
  }
)(CounterContainer);

redux-actions

redux-actions를 사용하면 액션 생성 함수를 더 짧은 코드로 작성할 수 있다.
그리고 리듀서를 작성할 때도 switch/case 문이 아닌 handleActions라는 함수를 사용하여 각 액션마다 업데이트 함수를 설정하는 형식으로 작성해 줄 수 있다.

import { handleAction } from "redux-actions";
import { createAction } from "redux-actions";

const CHANGE_INPUT = "todos/CHANGE_INPUT";
const INSERT = "todos/INSERT";
const TOGGLE = "todos/TOGGLE";
const REMOVE = "todos/REMOVE";

export const changeInput = createAction(CHANGE_INPUT, (input) => input);

let id = 3;
export const insert = createAction(INSERT, (text) => ({
  id: id++,
  text,
  done: false,
}));

export const toggle = createAction(TOGGLE, (id) => id);

export const remove = createAction(REMOVE, (id) => id);

const initialState = {
  input: "",
  todos: [
    { id: 1, text: "리덕스 기초 배우기", done: true },
    { id: 2, text: "리액트와 리덕스 사용하기", done: false },
  ],
};

const todos = handleAction(
  {
    [CHANGE_INPUT]: (state, { payload: input }) => ({
      ...state,
      input,
    }),
    [INSERT]: (state, { payload: todo }) => ({
      ...state,
      todos: [...state.todos, todo],
    }),
    [TOGGLE]: (state, { payload: id }) => ({
      ...state,
      todos: state.todos.map((todo) =>
        todo.id === id ? { ...todo, done: !todo.done } : todo
      ),
    }),
    [REMOVE]: (state, { payload: id }) => ({
      ...state,
      todos: state.todos.filter((todo) => todo.id !== id),
    }),
  },
  initialState
);

export default todos;

• createAction 함수를 사용해서 액션 객체를 만들 경우 첫 번째 인자로 type, 두 번째 인자로 payload를 생성할 함수를 선언해서 전달해 주면 된다.

const myAction = createAction(MY_ACTION, (text) => text);
myAction("hello world"); // { type: MY_ACTION, payload: 'hello world' }

• handleActions 함수의 첫 번째 파라미터에는 각 액션에 대한 업데이트 함수를 넣어 주고, 두 번째 파라미터에는 초기 상태를 넣어 준다.
• 액션 함수는 액션에 필요한 추가 데이터를 모두 payload라는 이름으로 사용하기 때문에 객체 비구조화 할당 문법으로 payload 이름을 새로 설정해주면 어떤 값을 의미하는지 더 쉽게 파악할 수 있다.

Immer

리듀서에서 상태를 업데이트할 때는 불변성을 지켜야 하기 때문에 spread 연산자와 배열의 내장 함수를 활용했다. 그러나 객체의 깊이가 깊어질수록 불변성을 지키기가 까다로워진다. 따라서 모듈의 상태를 설계할 때는 객체의 깊이가 너무 깊어지지 않도록 주의해야 한다.

하지만 상황에 따라 상태 값들을 하나의 객체 안에 묶는 것이 코드의 가독성을 높이는 데 유리하며, 나중에 컴포넌트에 리덕스를 연동할 때도 더욱 편리하다.
객체의 구조가 복잡해지거나 객체로 이루어진 배열을 다룰 경우, immer를 사용하면 훨씬 편리하게 상태를 관리할 수 있다.

const todos = handleAction(
  {
    [CHANGE_INPUT]: (state, { payload: input }) =>
      produce(state, (draft) => {
        draft.input = input;
      }),
    [INSERT]: (state, { payload: todo }) =>
      produce(state, (draft) => {
        draft.todos.push(todo);
      }),
    [TOGGLE]: (state, { payload: id }) =>
      produce(state, (draft) => {
        const todo = draft.todos.find((todo) => todo.id === id);
        todo.done = !todo.done;
      }),
    [REMOVE]: (state, { payload: id }) =>
      produce(state, (draft) => {
        const index = draft.todos.findIndex((todo) => todo.id === id);
        draft.todos.splice(index, 1);
      }),
  },
  initialState
);

• immer를 사용한다고 해서 모든 업데이트 함수에 immer를 적용할 필요는 없다. 일반 자바스크립트로 처리하는 것이 더 편할 때는 immer를 적용하지 않아도 된다.
• 예를 들어 위 코드에서 TOGGLE을 제외한 업데이트 함수들은 immer를 쓰지 않는 코드가 오히려 더 짧기 때문에 이전 형태를 유지하는 것도 무방하다.

Hooks를 사용해서 컨테이너 컴포넌트 만들기

리덕스 스토어와 연동된 컨테이너 컴포넌트를 만들 때 connect 함수를 사용하는 대신 react-redux에서 제공하는 Hooks를 사용할 수도 있다.

import Counter from "../components/Counter";
import { useSelector, useDispatch } from "react-redux";
import { decrease, increase } from "../modules/counter";

const CounterContainer = () => {
  const number = useSelector((state) => state.counter.number);
  const dispatch = useDispatch();

  return (
    <Counter
      number={number}
      onIncrease={() => dispatch(increase())}
      onDecrease={() => dispatch(decrease())}
    />
  );
};

export default CounterContainer;

• useSelector Hook을 사용하면 connect 함수를 사용하지 않고도 리덕스의 상태를 조회할 수 있다. 여기서 상태 선택 함수는 mapStateToProps와 형태가 똑같다.
• useDispatch를 사용하면 컴포넌트 내부에서 스토어의 내장 함수 dispatch를 사용할 수 있게 해 준다. 컨테이너 컴포넌트에서 액션을 디스패치해야 한다면 이 Hook을 사용하면 된다.
• 컴포넌트가 리렌더링될 때마다 onIncrease 함수와 onDecrease함수가 새롭게 만들어 지고 있다. 컴포넌트 성능을 최적화해야 한다면 useCallback으로 액션을 디스패치하는 함수를 감싸 주는 것이 좋다.

const CounterContainer = () => {
  const number = useSelector((state) => state.counter.number);
  const dispatch = useDispatch();
  const onIncrease = useCallback(() => dispatch(increase()), [dispatch]);
  const onDecrease = useCallback(() => dispatch(decrease()), [dispatch]);

  return (
    <Counter number={number} onIncrease={onIncrease} onDecrease={onDecrease} />
  );
};

export default CounterContainer;

• useDispatch를 사용할 때는 이렇게 useCallback과 함께 사용하는 것이 좋다.

useStore를 사용하여 리덕스 스토어 사용하기

useStore 훅을 사용하면 컴포넌트 내부에서 리덕스 스토어 객체를 직접 사용할 수 있다.

const store = useStore();
store.dispatch({ type: "SAMPLE" });
store.getState();

• useStore는 컴포넌트에서 정말 어쩌다가 스토어에 직접 접근해야 하는 상황에만 사용해야 한다.

connect 함수와의 주요 차이점

컨테이너 컴포넌트를 만들 때 connect 함수를 사용해도 좋고, useSelector와 useDispatch를 사용해도 좋다.
하지만 connect 함수를 사용하여 컨테이너 컴포넌트를 만들었을 경우, 해당 컨테이너 컴포넌트의 부모 컴포넌트가 리렌더링될 때 해당 컨테이너 컴포넌트의 props가 바뀌지 않았다면 리렌더링이 자동으로 방지되어 성능이 최적화 된다.

반면 useSelector를 사용하여 리덕스 상태를 조회했을 때는 최적화 작업이 자동으로 이루어지지 않으므로, 성능 최적화를 위해서는 React.memo를 컨테이너 컴포넌트에 사용해 주어야 한다.

0519

해쉬 테이블

해쉬 구조

• Hash Table : 키에 데이터를 저장하는 데이터 구조
  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 밪바꾸는 기법)
• 해쉬 : 임의 값을 고정 길이의 문자열로 변환하는 것
• 해싱 함수 : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값 또는 해쉬 주소 : Key를 해싱 함수로 연산해서 얻은 값
• 슬롯 or 버킷 : 한 개의 데이터를 저장할 수 있는 공간

해쉬 테이블의 장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 데이터가 있는지(중복) 확인이 쉽다.
• 단점
  • 일반적으로 저장 공간이 좀 더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시

충돌(Collision) 해결 알고리즘

• 해쉬 테이블의 가장 큰 문제는 충돌의 경우이다.
• 해시 함수는 입력값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결과값이 나오는 경우가 있다. 이것을 해시 충돌이라고 표현하며, 충돌이 적은 해시 함수가 좋은 해시함수다.
• 적재율이란 해시 테이블의 크기에 대한 키의 개수의 비율을 뜻한다. 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이다.

seperate Chaining 기법

• 해쉬 테이블 저장공간 외의 공간을 활용하는 기법으로 한 버킷 당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다.
• 충돌이 일어나면, 링크드 리스트나 트리를 사용해서 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
• 해시 충돌이 일어나더라도 링크드 리스트로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있다.
• 하지만 메모리 문제를 야기하여, 테이블의 부하율에 따라 선형적으로 성능이 저하된다. 따라서 부하율이 작을 경우에는 open addressing 방식이 빠르다.

Open addressing

• 버킷 당 들어갈 수 있는 엔트리는 하나이지만, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법
• 부하율이 높을수록(테이블에 저장된 데이터의 밀도가 높을수록) 성능이 급격히 저하된다.
• Linear Probing은 선형으로 순차적 탐색을 해서 다음 slot을 찾는 방법이다. 해시 함수로 나온 값에 이미 다른 값이 저장되어 있다면, 해당 해시값에서 고정 폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스한다.
• 해시 충돌이 해시 값 전체에 균등하게 발생할 때 유용한 방법이다.

빈번한 충돌을 개선하는 방법

1. 해쉬 함수를 재정의
2. 해쉬 테이블 저장공간을 확대

리사이징

Seperate changing의 경우, 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 리스트의 길이가 늘어나기 때문에, 성능이 떨어져 버킷의 개수를 늘려줘야 한다. 또한 Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장해야 한다.

보통 두 배로 확장하는데, 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다.

해쉬 함수와 키 생성 함수

• 유명한 해쉬 함수들이 있는데 제일 대표적으로 SHA 함수가 있다.
• 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능하다.

시간 복잡도

• 일반적인 경우(충돌이 없는 경우)는 O(1)
• 최악의 경우(충돌이 모두 발생하는 경우)는 O(n)
• 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1)이라고 말할 수 있다.
• 검색에서 16개의 배열에 데이터를 저장하고, 검색하면 O(n)
• 16개의 데이터 저장공간을 가진 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

JS에서의 해시 테이블

JS의 object는 해시 테이블일까?

정확히 말하면 JS의 객체는 해시 테이블이 아니다.
V8 엔진을 포함한 대부분의 JS 엔진은 해시 테이블과 유사하지만 높은 성능을 위해 일반적인 해시 테이블보다 나은 방법으로 객체를 구현한다.

JS는 클래스 없이 객체를 생성할 수 있으며, 객체가 생성된 이후라도 동적으로 프로퍼티와 메서드를 추가할 수 있다.
이는 사용하기 편리하지만 성능 면에서는 클래스 기반 객체보다 생성과 프로퍼티 접근에 비용이 더 많이 드는 비효율적인 방식이다.
따라서 V8 자바스크립트 엔진에서는 프로퍼티에 접근하기 위해 히든 클래스라는 방식을 사용해 C++ 객체의 프로퍼티에 접근하는 정도의 성능을 보장한다.

히든 클래스는 자바와 같이 고정된 객체 레이아웃(클래스)과 유사하게 동작한다.

JS로 해시 테이블 구현하기

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }

    return hash;
  }

  set(key, value) {
    const address = this._hash(key);

    if (!this.data[address]) {
      this.data[address] = [];
    }

    // If there is already a data in the address, push it in the same array.
    // This will happen in case of hash collision (enough data, less memory space).
    this.data[address].push([key, value]); // Time complexity = O(1)
    return this.data;
  }

  get(key) {
    const address = this._hash(key);
    const currentBucket = this.data[address];

    // In case of hash collision this will have length more than 1.
    if (currentBucket) {
      // Time Complexity = O(1) most often. In worst case (hash collision) it will be O(n)
      for (let i = 0; i < currentBucket.length; i++) {
        if (currentBucket[i][0] === key) {
          return currentBucket[i][1];
        }
      }
    }
  }
}

const myHashTable = new HashTable(50);
myHashTable.set("has_garden", true);
console.log(myHashTable.get("has_garden")); // true

myHashTable.set("house_number", 54);
console.log(myHashTable.get("house_number")); // 54

myHashTable.set("street_name", "Main Street");
console.log(myHashTable.get("street_name")); // 'Main Street'

reference
Hash Table Implementation in JavaScript · GitHub
자료구조 | 해시 테이블 hash table