연결리스트와 해시테이블

해시테이블

해시테이블(hash table)은 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킵니다. 해시테이블을 구현하는 방법은 여러가지 방법이 있습니다. 이 포스트에서는 가장 간단하면서도 흔하게 사용되는 구현 방식에 대해 설명하려고 합니다.

간단한 해시테이블을 구현하기 위해서는 연결리스트(Linked List)와 해시 코드 함수(hash code function)이 있으면 됩니다.

연결리스트

연결 리스트는 데이터를 담는 '노드(Node)'들의 연속으로 이루어집니다. 이 구현체는 첫 번째 노드 관리를 용이하게 하기 위해 데이터가 없는 더미 노드(Dummy Node) 를 헤드 앞에 두는 방식을 채택했습니다.

class LinkedList {
  constructor() {
    // 실제 데이터의 시작점을 가리키기 위한 빈 노드. 
    // 이를 통해 헤드(Head) 삽입/삭제 시 발생할 수 있는 예외 처리를 단순화합니다.
    this._dummy = new LinkedList.Node(null);
    this.length = 0; // 리스트의 현재 크기를 추적하는 속성
  }

  static Node = class {
    constructor(data = null) {
      this.data = data; // 이 구현에서는 { key, value } 형태의 객체를 저장함을 전제합니다.
      this.next = null; // 다음 노드를 가리키는 포인터 (단방향)
    }
  };
// ...

_dummy 는 리스트의 논리적 시작점(실제 헤드의 이전 위치) 역할을 합니다. 실제 첫 번째 데이터는 this._dummy.next에 위치합니다. length 는 리스트의 노드 개수를 캐싱하여, 길이를 구할 때 매번 순회하지 않고 $O(1)$의 시간 복잡도로 확인할 수 있게 합니다.

삽입 연산 (Insertion Methods)

데이터를 리스트에 추가하는 기능입니다. 삽입 위치에 따라 시간 복잡도가 다릅니다.

addAtHead(data) {
    const newNode = new LinkedList.Node(data);
    newNode.next = this._dummy.next;
    this._dummy.next = newNode;
    this.length++;
}

addAtTail(data) {
    const newNode = new LinkedList.Node(data);
    let current = this._dummy;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = newNode;
 this.length++;
}

addAtHead(data) 는 리스트의 맨 앞에 노드를 추가합니다. 더미 노드의 바로 뒤(_dummy.next)에 새 노드를 연결하므로 시간 복잡도는 $O(1)$입니다.

addAtTail(data) 는 리스트의 맨 끝에 노드를 추가합니다. 현재 이 클래스는 꼬리(Tail) 포인터를 별도로 관리하지 않기 때문에, 끝을 찾기 위해 리스트 전체를 순회해야 합니다. 시간 복잡도는 $O(n)$입니다.

삭제 연산 (Deletion Methods)

조건에 맞는 노드를 리스트에서 제거하고, 끊어진 연결을 이어주는 기능입니다.

removeHead() {
    if (this._dummy.next !== null) {
      this._dummy.next = this._dummy.next.next;
      this.length--;
    }
}

removeByKey(key) {
    let prev = this._dummy;
    let current = this._dummy.next;

    while (current !== null) {
      if (current.data.key === key) {
        prev.next = current.next; // 현재 노드를 건너뛰어 연결 (삭제 효과)
        this.length--;
        return true; // 삭제 성공
      }
      prev = current;
      current = current.next;
    }

    return false; // 해당 키를 가진 노드가 없음
}

removeHead() 는 실제 첫 번째 데이터 노드를 삭제합니다. _dummy가 가리키는 대상을 두 번째 노드(_dummy.next.next)로 변경하는 방식으로 동작합니다. $O(1)$의 시간 복잡도를 가집니다.

removeByKey(key) 는 특정 key 값을 가진 노드를 찾아 삭제합니다. 단방향 연결 리스트는 이전 노드로 역추적할 수 없으므로, 탐색 시 이전 노드를 가리키는 prev 변수와 현재 노드를 가리키는 current 변수를 동시에 이동시키는 방식을 사용합니다. 최악의 경우 $O(n)$의 시간 복잡도가 소요됩니다.

탐색 및 수정 연산 (Search & Update Methods)

저장된 데이터({key, value})의 특성을 활용하여 특정 키를 기반으로 데이터를 조회하거나 값을 업데이트하는 기능입니다.

getHead() {
    return this._dummy.next; // 노드 객체 자체를 반환
}

findByKey(key) {
    let current = this._dummy.next;
    while (current !== null) {
      if (current.data.key === key) {
        return current.data; // 데이터 객체를 반환
      }
      current = current.next;
    }
    return undefined;
}

updateByKey(key, value) {
    let current = this._dummy.next;
    while (current !== null) {
      if (current.data.key === key) {
        current.data.value = value;
        return true; // 수정 성공
      }
      current = current.next;
    }
    return false; // 해당 키를 가진 노드가 없어 수정 실패
}

getHead(): 리스트의 첫 번째 실제 노드를 반환합니다. findByKey(key) 및 updateByKey(key, value): 둘 다 리스트의 처음부터 끝까지 선형 탐색(Linear Search)을 수행합니다. 원하는 key를 찾으면 해당 데이터를 반환하거나 갱신하며, 탐색에 소요되는 시간 복잡도는 $O(n)$입니다.

해시테이블

위에서 작성한 Linked List 를 활용하여 해시테이블을 구현해보곘습니다. 처음엔 키의 해시 코드를 계산해야 합니다. 키의 자료형은 보통 int, long이 됩니다. 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두개의 키가 같은 해시 코드를 가리킬 수 있다는 사실을 명심해야 합니다.

function hash(key) {
 const strKey = String(key);
 let hash = 0;
 
 for(let i = 0; i < strKey.length; i++) {
  hash = (hash * 31 + strKey.charCodeAt(i)) % this.buckets.length;
 }
 return hash;
}

그 다음엔 hash(key) % array_length와 같은 방식으로 해시코드를 이용해 배열의 인덱스를 계산합니다. 물론 앞에서도 이야기한것과 같이 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수 있다는 것을 명심해야 합니다.

hash("apple") → 3
hash("banana") → 3

예를들면, 위와 같이 apple 와 banana 는 서로 다른 인덱스를 반환하기 때문에 서로 다른 키 값을 사용했음에도 중복될 수 있는 가능성을 가지고 있습니다.

class HashMap {
  constructor(size = 16) {
    this.buckets = Array.from({ length: size }, () => new LinkedList());
    this.size = 0; // 저장된 전체 key 개수
  }
}

배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트(Linked List)가 존재합니다. 키와 값을 해당 인덱스에 저장을 합니다. 충돌에 대비해서 반드시 연결리스트를 이용해야 합니다. 연결리스트는 인덱스가 중복이 되더라도 여러 데이터를 필요한 만큼 계속 추가가 가능하며 이를 $O(1)$의 작업 시간으로 수행히 가능하기 때문입니다.

class HashMap {
  constructor(size = 16) {
    this.buckets = Array.from({ length: size }, () => new LinkedList());
    this.size = 0; // 저장된 전체 key 개수
  }

  hash(key) {
    const strKey = String(key);
    let hash = 0;

    for (let i = 0; i < strKey.length; i++) {
      hash = (hash * 31 + strKey.charCodeAt(i)) % this.buckets.length;
    }

    return hash;
  }
}

해시 테이블의 기본 저장 공간인 버킷(Buckets)을 고정된 크기의 배열로 초기화합니다. 배열의 각 요소는 빈 연결 리스트 인스턴스로 채워지며, 이는 동일한 해시값을 가지는 데이터를 하나의 버킷 안에서 연결 리스트 형태로 관리하기 위함입니다. size 변수는 해시맵에 저장된 총 키의 개수를 추적합니다.

hash(key) 메서드는 임의의 키를 받아 유효한 배열 인덱스로 변환하는 해시 함수입니다. 키를 문자열로 변환한 뒤, 각 문자의 아스키코드 값에 소수 31을 곱하여 누적하는 방식을 사용합니다. 최종 해시값을 버킷 배열의 길이로 나눈 나머지를 구하여, 반환되는 인덱스가 항상 배열의 유효한 범위 내에 존재하도록 보장합니다.

데이터 삽입 및 수정 (set)

set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    const updated = bucket.updateByKey(key, value);
    if (!updated) {
      bucket.addAtTail({ key, value });
      this.size++;
    }
  }

set(key, value) 메서드는 해시맵에 새로운 데이터를 저장하거나 기존 키의 값을 갱신하는 역할을 수행합니다. 해시 함수를 통해 계산된 인덱스의 버킷(연결 리스트)을 가져온 후, 연결 리스트의 updateByKey 메서드를 호출하여 키의 존재 여부를 확인합니다. 키가 이미 존재하여 값이 갱신되었다면 작업을 종료하여 데이터의 유일성을 유지합니다.

만약 키가 존재하지 않는다면, 연결 리스트의 addAtTail 메서드를 사용하여 리스트의 맨 끝에 새로운 데이터를 추가하고 해시맵의 전체 size를 1 증가시킵니다. 해시 충돌이 발생하더라도 동일한 버킷의 연결 리스트에 데이터가 순차적으로 추가되므로 안전하게 저장됩니다.

데이터 조회 및 존재 여부 확인 (get, has)

get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const item = bucket.findByKey(key);
    return item ? item.value : undefined;
  }

  has(key) {
    return this.get(key) !== undefined;
  }

get(key) 메서드는 저장된 데이터를 키를 기반으로 검색합니다. 키를 해시화하여 목표 버킷을 찾은 뒤, 연결 리스트의 findByKey 메서드를 통해 내부를 탐색합니다. 일치하는 키를 가진 노드를 찾으면 그에 대응하는 값을 반환하고, 찾지 못하면 undefined를 반환합니다. 데이터 분포에 따라 탐색 속도가 결정되며, 충돌이 적을수록 시간 복잡도 측면에서 유리한 성능을 냅니다.

has(key) 메서드는 내부적으로 get(key)를 호출하여 반환값이 undefined인지 판별합니다. 이를 통해 특정 키가 해시맵에 존재하는지 여부를 불리언 형태로 반환하여 확인 과정을 단순화합니다.

데이터 삭제 및 구조 출력 (delete, print)

delete(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const removed = bucket.removeByKey(key);

    if (removed) {
      this.size--;
    }

    return removed;
  }

delete(key) 메서드는 특정 키를 가진 데이터를 해시맵에서 제거합니다. 대상 키의 버킷을 찾은 뒤 연결 리스트의 removeByKey 메서드를 실행하여 메모리상에서 해당 노드의 연결을 끊습니다. 삭제가 성공적으로 이루어지면 해시맵의 전체 size를 1 감소시키고, 작업의 성공 여부를 불리언 값으로 반환합니다.

해시 테이블에서 값을 찾는 과정

// 두 개의 다른 문자열이 내부적으로 같은 해시값을 가질 수 있음
const obj = new HashMap();

// 다음 두 문자열은 다르지만 같은 해시값을 가질 가능성이 있음
const key1 = "Aa";
const key2 = "BB";

// 자바스크립트 엔진 내부에서 이러한 문자열은 같은 해시값으로 매핑될 수 있음
obj.set(key1) = "value1";
obj.set(key2) = "value2";

console.log(obj.get(key1)); // "값 1"
console.log(obj.get(key2)); // "값 2"
// 여기서 값은 다르지만 key가 중복 될 가능성이 있다.

충돌이 자주 발생한다면, 최악의 경우의 수행 시간은 O(N)이 된다(N은 키의 개수), 하지만 일반적으로 해시에 대해 이야기할 때는 충돌을 최소화하도록 잘 구현된 경우를 가정하는데 이 경우의 탐색 시간은 O(1)입니다.

지금까지는 연결 리스트를 사용하여 해시 테이블을 구현하는 방법을 이야기 했습니다. 하지만 이진 탐색 트리를 사용하는 방법이 있는데 이 경우에는 O(logN)이 됩니다. 이 방법은 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있습니다.

JavaScript에서 Key-Value 형태를 다루는 방식은 크게 일반 객체(Object) 와 Map 객체로 나뉘며, V8 엔진은 이들을 다르게 처리합니다.

• 일반 객체 (Object): V8은 객체 속성 접근 속도를 높이기 위해 히든 클래스(Hidden Class)를 사용합니다. 그러나 속성이 동적으로 지나치게 많이 추가되거나 삭제되면, 히든 클래스 최적화가 비효율적이므로 딕셔너리 모드(Dictionary Mode) 라는 해시 테이블 구조로 전환됩니다.

• Map 및 Set: ECMAScript 표준에 따라 데이터의 '삽입 순서'를 보장해야 합니다. 이를 위해 V8은 OrderedHashTable 이라는 결정론적 해시 테이블 알고리즘을 사용하여 구현됩니다.

해시 충돌 발생 시 V8 엔진이 이를 관리하는 방법은 사용하는 자료 구조에 따라 나뉩니다. 일반 객체가 딕셔너리 모드로 동작할때에는 개방 주소법(Open Addressing) 을 사용하여 충돌을 해소합니다. 충돌이 발생하면 내부 버킷 배열에서 다른 빈 공간(슬롯)을 계산하여 데이터를 저장합니다. V8 내부적으로는 이차 탐사(Quadratic Probing) 등의 연산 방식을 사용하여 충돌 시 삽입할 다음 인덱스를 찾습니다.

Map 와 Set 에서는 해시충돌을 해결할때 체이닝(Chaining) 을 사용하여 충돌을 해결합니다. 연속된 하나의 1차원 배열(Flat Array) 내부에서 인덱스 번호를 사용해 다음 충돌 요소의 위치를 가리키는 방식(Array-based Chaining)으로 체이닝을 구현합니다.

동적 배열

동적 배열은 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다. 통상적으로 배열이 가득 차는 순간, 배열의 크기를 두 배로 늘린다. 크기를 두 배 늘리는 시간은 O(N)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간으로 계산 했을 때 여전히 O(1)이 된다.

JavaScript에서 배열은 해시 테이블 기반 객체입니다. JavaScript에서 배열은 특별한 형태의 객체입니다. 내부적으로는 키가 문자열인 해시 테이블과 유사하게 구현되어 있으며, 배열의 인덱스는 문자열 키로 변환이 됩니다.

• 밀집 배열(Dense Arrays): 인덱스가 연속적이고 동일한 타입의 요소를 가진 배열은 C언어와 비슷한 연속적인 메모리 블록에 저장됩니다. 이것이 ArrayList와 가장 유사한 구현 방식입니다.

// 배열 생성
const arr = [];

// 요소 추가 - 내부적으로 크기가 자동으로 조정됨
for (let i = 0; i < 1000; i++) {
  arr.push(i);
}

// 중간에 요소 삽입 - 모든 후속 요소가 이동해야 함
arr.splice(1, 0, 'new item');

// 임의의 인덱스에 값 할당 - 필요하면 배열 크기가 자동으로 확장됨
arr[5000] = 'far away'; // 인덱스 1000~4999는 비어있는 희소 배열이 됨

희소 배열(Sparse Arrays) 은 일부 인덱스 위치에만 값이 있고 많은 위치가 비어 있는 배열입니다. 인덱스가 불연속적이거나 큰 간격이 있는 배열은 해시 테이블과 유사한 구조로 구현됩니다.

실제 값이 있는 요소만 메모리에 저장됩니다. 비어 있는 인덱스는 메모리를 차지하지 않습니다. 하지만 희소 배열의 경우 밀집 배열에 비해 접근 시간이 더 오래 걸릴 수 있습니다. 일반적인 배열은 O(1) 시간 복잡도로 요소에 접근할 수 있지만, 희소 배열은 해시 테이블 조회가 필요하므로 최악의 경우 O(logn) 또는 그 이상이 될 수 있습니다.

반면 밀집 배열(Dense Array) 는 연속된 메모리 블록에 데이터를 저장합니다. 이 메모리 주소는 다음과 같은 간단한 공식으로 계산이 됩니다.

요소의 메모리 주소 = 배열의 시작 주소 + (인덱스 * 요소 크기)

이 계산은 단순한 산술 연산이기 때문에 O(1)의 시간 복잡도를 가집니다. 이와 반대되는 희소 배열의 접근 방식에 대해서 이야기 해보겠습니다.

희소 배열은 해시 테이블과 유사한 방식으로 구현이 된다고 하였던 이유는 인덱스에 대한 접근 방식 또한 유사하기 때문입니다.

1. 인덱스를 해시 함수를 이용하여 해시 값으로 변환합니다.
2. 해시 테이블에서 해시 값에 해당하는 버킷 위치를 결정합니다.
3. 버킷에서 키(인덱스)와 일치하는 항목을 검색합니다.
4. 출동리 있는 경우 추가 검색을 수행합니다.

이 과정은 단순 산술 연산보다 훨씬 복잡하며, 최악의 경우 O(n), n은 전체 배열의 길이 시간이 걸릴 수 있습니다.(실제로는 대부분의 경우 O(1)에 가깝지만, 해시 충돌이 많을 경우 성능이 저하됩니다) 밀집배열과 희소배열의 성능 차이는 아래의 결과와 같습니다.

성능 테스트 시작...
===== 밀집 배열 테스트 =====
밀집 배열 생성: 0.011ms
밀집 배열 랜덤 접근: 14.28ms
밀집 배열 순차 접근: 0.019ms
===== 희소 배열 테스트 =====
희소 배열 생성: 67.088ms
희소 배열 존재 요소 접근: 78.018ms
희소 배열 무작위 접근: 24.5ms
희소 배열 순차 접근 (처음 1000개): 0.028ms
===== 객체(해시 테이블) 테스트 =====
객체 생성: 33.315ms
객체 존재 키 접근: 103.308ms
객체 무작위 키 접근: 93.199ms
===== 메모리 사용량 분석 =====
밀집 배열 (1000개 요소) 메모리: ~8000 bytes
희소 배열 (10000000개 인덱스, 100000개 실제 요소) 메모리: ~800000 bytes
객체 (100000개 키) 메모리: ~800000 bytes
성능 테스트 완료!

밀집 배열의 경우 접근하는 인덱스에 대한 값에 대한 계산이 단순한 산술 연산이기 때문에 O(1)을 보장하지만 희소 배열의 경우 그렇지 않습니다. 희소배열의 경우 해시 값을 계산하는 과정에서 오버헤드, 어떤 처리를 하기 위해 안정성들을 고려하고 크기가 조정될 때 마다 재해싱 하는 과정으로 인해 부가적인 시간이 발생할 가능성이 높습니다.

배열의 크기를 늘리는 상환 입력 시간은 왜 O(1)이 되는가

상환 입력 시간(Amortized Time Complexity) 은 자료구조나 알고리즘의 연산이 최악의 경우 가끔 비효율적으로 동작하더라도, 전체 연산들의 평균적인 시간 복잡도를 분석하는 방식입니다.

이 배열의 크기를 늘릴 때 마다 얼마나 많은 원소를 복사해야 하는지 역으로 계산해 볼 수 있습니다. 배열의 크기를 K로 늘리면 그 전체 배열의 크기는 K의 절반이었을 것이므로 K/2 만큼의 원소를 복사해야 합니다.

따라서 N개의 원소를 삽입하기 위해서 복사해야 하는 원소의 총 개수는 N/2 + N/4 + N/8 + ... + 2 + 1 이 되므로 N 보다 작은 경우가 보장이 됩니다.

문자열

많은 프로그래밍 언어에서 문자열(String)은 불변(immutable) 객체 입니다. 이는 문자열이 한 번 생성되면 그 내용을 변경할 수 없다는 것을 의미합니다. 따라서 문자열을 조작하는 모든 작업(결합, 삽입, 삭제 등)은 새로운 문자열 객체를 생성하게 됩니다.

JavaScript에서도 문자열도 불변 객체입니다. 문자열을 변경하는 어떤 연산도 실제로는 새 문자열을 반환합니다.

let str = "Hello";
str += " World"; // 새로운 문자열 "Hello World"가 생성됨

이 코드는 "Hello"와 " World"를 결합한 새 문자열을 생성하고, 변수 str이 이 새 문자열을 참조하도록 합니다. 원래 "Hello" 문자열은 변경되지 않습니다. 이러한 방법의 단점을 자세한 예시를 이용해 설명해보겠습니다.

function joinWords(words: string) {
  let sentence = '';
  for (const w of words) {
    sentence = sentence + w;
  }
  return sentence;
}

문자열의 길이가 x라고 하고 같은 n 개의 문자열이 주어졌다고 가정 해보겠습니다. 두 개의 문자열을 이어붙일 때마다 두 개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야 합니다.

이 경우 처음에는 x개, 2x개, 3x개 ... nx개의 문자를 복사해야 합니다. 따라서 총 수행 시간은 O(x+2x+...+nx) 이므로 O(xn^2) 가 되므로 굉장히 비효율적이기 때문에 StringBulider를 사용하여 이 문제를 해결하고자 하는 것입니다.

JavaScript에서는 StringBulider 클래스가 없지만 비슷한 패턴을 구현하는 여러 방법이 있습니다.

const parts = [];
for (let i = 0; i < 1000; i++) {
    parts.push(`Item ${i}`);
}
const result = parts.join(""); // 모든 부분을 하나의 문자열로 결합

이 방법은 많은 문자열을 결합할 때 가장 효율적인 방법 중 하나입니다. 배열에 추가하는 작업은 O(1)에 가까운 시간 복잡도를 가지며, join() 연산은 모든 문자열을 한 번에 결합합니다.

let result = "";
for (let i = 0; i < 10; i++) {
    result += `Item ${i}`;
}

이 방법은 반복 횟수가 많아지면 성능이 크게 저하되기 때문에, 이유는 앞서 설명 했습니다. 길이가 짧을 경우에만 사용해야 합니다.