이전 글에서 이어집니다.

불변성 연결리스트

개요

불변성 연결리스트를 만든 거에 이어 불변성을 가지는 해시 맵을 만들 거다.
해시 충돌을 해결하기 위한 방법으로 분리 체이닝(Seperate Chaining)이 있는데, 이걸 해결하기 위해 버킷에 연결리스트를 넣는 방식으로 해볼 거다.

선수 지식

• 자료구조 - 해시맵 (블로그 글 보러가기)
• 이전 글에서 구현한 불변성 연결 리스트 (위 참고)
• 함수형 프로그래밍
• JavaScript 기초 문법, class 사용법
• Jest (단위 테스트를 원할 경우)

전체 코드 Gist

바로가기

1. 핵심 컨셉: Separate Chaining과 불변성 결합

• 해시 충돌 문제를 Seperate Chaining 방법으로 해결
  • 배열의 각 버킷을 연결 리스트로 만듦
  • 충돌이 발생하면 해당 버킷의 연결 리스트에 새로운 노드를 추가해 데이터를 체인처럼 연결
• 위 연결 리스트 역할에 ImmutableLinkedList를 사용
• 해시맵의 모든 데이터 변경 작업(put, remove)은 버킷에 있는 불변 연결 리스트를 조작해 새로운 불변 연결 리스트를 생성하고, 이 새 리스트를 포함하는 새로운 해시맵을 반환하는 방식으로 이루어짐

2. 데이터 구조 설계

다음과 같은 속성을 가진다.

• buckets 버킷 배열
  • 역할: 데이터의 실질적 저장소
  • 구조: 버킷은 ImmutableLinkedList의 인스턴스이거나, 비어있으면 null
• bucketSize 버킷 크기
  • 역할: 버킷 배열의 크기, 해시 값을 인덱스로 변환할 때 사용
• size 총 데이터 개수
  • 역할: 해시맵에 저장된 총 key-value쌍의 개수
• 버킷 노드에 저장될 데이터 형태
  • 해시맵에서는 키와 값을 모두 저장하므로 노드의 value에 다음과 같이 저장
    • { key: "key", value: "value" }

3. 핵심 기능 설계

해시함수

_hash(key)

• 역할: 문자열 key를 입력받아 buckets 배열의 특정 인덱스로 변환

put(key, value)

• 목표: key에 value를 저장, 그 결과로 새로운 해시맵 반환
• 동작
  1. 해시 함수로 인덱스 계산
  2. 키 검색 및 새 버킷 생성
  3. 새로운 해시맵 반환

remove(key)

• 목표: key에 해당하는 데이터 삭제, 그 결과로 새로운 해시맵 반환
• 동작
  1. put과 동일하게 key에 대항하는 버킷 찾기
  2. 삭제할 key를 가진 노드의 위치 찾기
  3. 해당 노드가 제거된 새로운 버킷 얻기
  4. 새로운 해시맵 반환

get(key)

• 목표: key에 해당하는 value를 찾아 반환
• 동작
  1. key에 해당하는 버킷(연결 리스트)을 찾기
  2. 버킷을 처음부터 끝까지 순회
  3. 일치하는 key를 찾으면 node.value.value를 반환
  4. 버킷이 없거나 키를 못찾으면 undefined 반환

contains(key)

• 목표: 해시맵에 해당 key가 존재하는지 true / false로 반환
• 동작
  1. get을 재활용해 호출한 결과가 undefined면 false 반환

keys()

• 목표: 해시맵 내의 모든 key들을 배열 형태로 반환
• 동작
  1. 버킷 배열 전체를 순회
  2. 각 버킷이 null이 아니면 해당 버킷을 순회하고 key를 반환할 배열에 push
  3. 모든 순회가 끝나면 키 배열을 반환

4. 구현

기초 데이터 구조

export class ImmutableHashMap {
  constructor(bucketSize = 32, size = 0, buckets = null) {
    this.bucketSize = Math.max(1, bucketSize); // 버킷 크기는 항상 양수

    // 총 데이터 개수
    this.size = size;

    // 버킷 배열 초기화 (기존 배열이 없으면 새로 생성)
    this.buckets = buckets || new Array(this.bucketSize).fill(null);

    // 해시맵 인스턴스를 동결하여 불변성 확보
    Object.freeze(this);
  }
}

먼저 해시맵의 기본 구조를 만들었다.

버킷의 총 개수의 기본값은 일단 32로 설정했다.

해시 함수

#hash(key) {
    let hashCode = 0;
    for (let i = 0; i < key.length; i++) {
      hashCode = (hashCode << 5) - hashCode + key.charCodeAt(i);
      hashCode |= 0; // 32비트 정수로 변환
    }
    return Math.abs(hashCode) % this.bucketSize; // 버킷 크기로 나눈 나머지로 해시값 계산
}

위와 같이 구현했다.
최대한 해시 충돌을 줄이기 위해 각 문자를 ASCII 코드로 변환하고, 비트 연산을 통해 해시 코드를 계산한다.
이후 버킷 크기로 나눈 나머지를 반환한다.

put(key, value)

put(key, value) {
    // 1. 해시 함수로 인덱스 계산
    const index = this.#hash(key);

    // 2. 키 검색 및 새 버킷 생성

    // 2-1. 현재 인덱스의 버킷을 가져오고, 없으면 빈 리스트를 사용
    const currentBucket = this.buckets[index] || new ImmutableLinkedList();

    // 2-2. 버킷 안에서 기존에 동일한 키가 있는지 검색
    let existingNodeIndex = -1;
    let currentNode = currentBucket.head;
    let currentIndex = 0;
    while (currentNode !== null) {
      if (currentNode.value.key === key) {
        existingNodeIndex = currentIndex;
        break;
      }
      currentNode = createNode.next;
      currentIndex++;
    }

    // 2-3. 키 존재 여부에 따라 분기 처리
    let bucketForAppend;
    let newSize;

    if (existingNodeIndex > -1) {
      // 키가 이미 존재할 경우 (값 업데이트):
      // 기존 노드를 제거한 새로운 리스트를 준비
      // 해시맵의 전체 크기는 변하지 않음
      bucketForAppend = currentBucket.remove(existingNodeIndex);
      newSize = this.size;
    } else {
      // 새로운 키일 경우 (값 추가):
      // 현재 버킷을 그대로 사용하고, 해시맵의 전체 크기를 1 증가
      bucketForAppend = currentBucket;
      newSize = this.size + 1;
    }

    // 2-4. 준비된 버킷에 새로운 key value 쌍을 추가해 최종 버킷 완성
    const newBucket = bucketForAppend.append({ key, value });

    // 3-1. 기존 버킷 배열을 shallow copy하여 새로운 배열을 만듦
    const newBuckets = this.buckets.slice();

    // 3-2. 새로운 배열의 해당 인덱스 위치를 위에서 만든 새 버킷으로 교체
    newBuckets[index] = newBucket;

    // 3-3. 새로운 버킷 배열과 새로운 크기를 사용해 완전히 새로운 ImmutableHashMap 인스턴스를 생성
    return new ImmutableHashMap(this.bucketSize, newSize, newBuckets);
}

동작 1: 해시함수로 인덱스 계산

• key를 해시함수에 넣어 인덱스를 결정한다.

동작 2: 키 검색 및 새 버킷 생성

• 2-1.
  • 해당 인덱스에 이미 버킷(연결 리스트)이 있는지 확인
  • 있으면 currentBucket에 할당하고, null이면 비어있는 ImmutableLinkedList를 새로 만들어 할당한다.
• 2-2.
  • currentBucket을 순회하며 추가하려는 key가 이미 있는지 확인한다.
  • 있으면 existingNodeIndex에 해당 노드의 위치를 저장한다.
• 2-3.
  • 키가 존재하면 값을 업데이트하는 경우이므로 기존 노드가 제거된 새로운 연결 리스트를 반환한다.
  • 키가 존재하지 않으면 새로운 값을 추가하는 경우이므로 현재 버킷을 그대로 bucketForAppend에 할당한다. 그리고 새로운 데이터를 추가하는 것이기 때문에 size를 하나 늘린다.
• 2-4.
  • 그러고는 새로운 연결 리스트(newBucket)을 만들어 반환한다.

동작 3: 새로운 해시맵 반환

• 3-1.
  • 불변성의 핵심으로 원본 버킷 배열을 수정하지 않고 복사한다.
• 3-2.
  • 방금 만든 새로운 버킷 배열 (newBuckets)의 인덱스 위치에 새로운 버킷을 할당한다.
• 3-3.
  • 완전히 새로운 해시맵 인스턴스를 생성해 반환한다.

동작 설명이 너무 길어졌는데, 이걸 요약하면 아래와 같다.

1. 복사본을 하나 만든다
2. 그 복사본에서 바꿀 부분만 딱 고친다
3. 이 복사본을 새로운 버전이라고 하고 돌려준다

remove(key)

remove(key) {
    // 1. key에 해당하는 버킷 찾기
    const index = this.#hash(key);
    const bucket = this.buckets[index];

    // 버킷 자체가 없으면 키도 존재할 수 없으므로 원본을 그대로 반환
    if (!bucket) {
      return this;
    }

    // 2. 삭제할 key를 가진 노드의 인덱스 찾기
    let nodeIndexToRemove = -1;
    let currentNode = bucket.head;
    let currentIndex = 0;
    while (currentNode !== null) {
      if (currentNode.value.key === key) {
        nodeIndexToRemove = currentIndex;
        break; // 찾았으면 루프 종료
      }
      currentNode = currentNode.next;
      currentIndex++;
    }

    if (nodeIndexToRemove === -1) {
      // 삭제할 노드가 없으면 원본 해시맵 반환
      return this;
    }

    // 3. 해당 노드가 제거된 새로운 버킷 얻기
    let newBucket = bucket.remove(nodeIndexToRemove);
    if (newBucket.head === null) {
      // 버킷이 비어있으면 해당 인덱스의 버킷을 null로 설정
      newBucket = null;
    }

    // 4. 새로운 해시맵 반환
    const newBuckets = this.buckets.slice();
    newBuckets[index] = newBucket;
    return new ImmutableHashMap(this.bucketSize, this.size - 1, newBuckets);
}

get(key)

get(key) {
    // 1. key에 해당하는 버킷 찾기
    const index = this.#hash(key);
    const bucket = this.buckets[index];

    // 버킷이 없으면 undefined 반환
    if (!bucket) {
      return undefined;
    }

    // 2. 버킷을 순회하며 일치하는 key 찾고 값 반환
    let currentNode = bucket.head;
    while (currentNode !== null) {
      if (currentNode.value.key === key) {
        return currentNode.value.value; // 일치하는 key의 value 반환
      }
      currentNode = currentNode.next; // 다음 노드로 이동
    }

    // 3. 일치하는 key가 없으면 undefined 반환
    return undefined;
  }

contains(key)

contains(key) {
    return this.get(key) !== undefined; // get 메서드를 사용하여 존재 여부 확인
}

keys()

keys() {
    // 결과를 담을 빈 배열
    const allKeys = [];

    // 모든 버킷을 순회
    for (const bucket of this.buckets) {
      if (bucket) {
        // 각 버킷의 노드를 순회
        let currentNode = bucket.head;
        while (currentNode !== null) {
          // 노드의 key를 배열에 추가
          allKeys.push(currentNode.value.key);
          currentNode = currentNode.next; // 다음 노드로 이동
        }
      }
    }
    return allKeys; // 모든 키를 담은 배열 반환
}

🧪 테스트

테스트 계획

ImmutableHashMap은 키-값 쌍을 관리하며, 모든 연산은 새로운 해시맵을 반환해야 한다. ImmutableLinkedList를 내부적으로 사용하므로, 충돌 처리 시 연결 리스트의 동작도 간접적으로 테스트된다.

테스트 대상	테스트 시나리오	입력값	기대 결과	핵심 검증 코드 (Jest)
constructor	기본값으로 해시맵 생성	new ImmutableHashMap()	bucketSize 32, size 0인 인스턴스 생성	expect(map.bucketSize).toBe(32); expect(map.size).toBe(0);
put	새 키-값 추가	map.put('key1', 'value1')	key1이 추가된 새 해시맵 반환, size 1 증가	const newMap = map.put('key1', 'value1'); expect(newMap.get('key1')).toBe('value1'); expect(newMap.size).toBe(1); expect(map.size).toBe(0);
	기존 키의 값 수정	map.put('key1', 'value1'); newMap.put('key1', 'updated')	key1의 값이 수정된 새 해시맵 반환, size는 불변	const updatedMap = newMap.put('key1', 'updated'); expect(updatedMap.get('key1')).toBe('updated'); expect(updatedMap.size).toBe(1);
	해시 충돌 발생 시 처리	// key1, key2가 같은 해시 인덱스를 가짐 map.put('key1', 'v1').put('key2', 'v2')	두 키 모두 정상적으로 저장 및 조회되어야 함	expect(newMap.get('key1')).toBe('v1'); expect(newMap.get('key2')).toBe('v2'); expect(newMap.size).toBe(2);
remove	존재하는 키 제거	map.put('key1', 'value1') newMap.remove('key1')	key1이 제거된 새 해시맵 반환, size 1 감소	const removedMap = newMap.remove('key1'); expect(removedMap.contains('key1')).toBe(false); expect(removedMap.size).toBe(0);
	존재하지 않는 키 제거	map.remove('nonexistent')	원본과 동일한 해시맵 인스턴스 반환	const sameMap = map.remove('nonexistent'); expect(sameMap).toBe(map);
get	존재하는 키의 값 조회	map.put('key1', 'value1')	'value1' 반환	expect(newMap.get('key1')).toBe('value1');
	존재하지 않는 키 조회	map.get('nonexistent')	undefined 반환	expect(map.get('nonexistent')).toBeUndefined();
contains	존재하는 키 확인	map.put('key1', 'value1')	true 반환	expect(newMap.contains('key1')).toBe(true);
	존재하지 않는 키 확인	map.contains('nonexistent')	false 반환	expect(map.contains('nonexistent')).toBe(false);
keys	모든 키 조회	map.put('a',1).put('b',2)	['a', 'b'] 또는 ['b', 'a'] 배열 반환	const keys = newMap.keys(); expect(keys).toHaveLength(2); expect(keys).toContain('a'); expect(keys).toContain('b');
	빈 맵에서 키 조회	map.keys()	빈 배열 [] 반환	expect(map.keys()).toEqual([]);