[Hash Table 구현] Linear Probing 방식의 Hash Table을 구현해 보세요.

Linear Probing 방식의 Hash Table

hash table은 JavaScript에서 { "key" : { "innerKey" : "value" } } 와 같이 사용하는것을 지칭하는것으로 알고 있었는데, linear probing방식으로 구현해보는 과제가 주어져 일단 linear probing이 무엇인지부터 알아보아야겠다.

 

Linear Probing ?

위키디피아에 따르면 linear probing이란, 해시 테이블 의 충돌을 해결하기 위한 컴퓨터 프로그래밍 방식 , 키-값 쌍 의 컬렉션을 유지 관리 하고 주어진 키와 관련된 값을 찾기 위한 데이터 구조 라고한다.

 

세션을 듣던 중 해싱된 키값이 중복될경우 다음 해싱된 키값으로 저장하는 로직으로 설명을 들었던것을 참고하여 구현하면 될것으로 보인다.

 

Doubly Linked List

우선적으로 세션에 나온 예시에서 Java의 내장함수인 Doubly Linked List를 import하여 사용했길래 Array를 그냥 사용할까 하다가 TypeScript로 구현해보았다.

 

생각보다 많이 길어져서 접은글로 작성하였다.

 

class BidirectionalNode<E> {
  public prev: BidirectionalNode<E> | null;
  public data: E | null;
  public next: BidirectionalNode<E> | null;

  constructor(data?: E) {
    this.prev = null;
    this.data = data || null;
    this.next = null;
  }
}

export class DoublyLinkedList<E> {
  private dummyHead: BidirectionalNode<E>;
  private dummyTail: BidirectionalNode<E>;
  public size: number;

  constructor() {
    this.dummyHead = new BidirectionalNode<E>();
    this.dummyTail = new BidirectionalNode<E>();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
    this.size = 0;
  }

  /**
   * Inserts the specified element at the beginning of this list.
   *
   * @param e the element to add
   */
  addFirst(e: E): void {
    const newNode = new BidirectionalNode<E>(e);

    newNode.next = this.dummyHead.next;
    newNode.prev = this.dummyHead;
    if (this.dummyHead.next) {
      this.dummyHead.next.prev = newNode;
    }
    this.dummyHead.next = newNode;

    this.size++;
  }

  /**
   * Appends the specified element to the end of this list.
   *
   * @param e the element to add
   */
  addLast(e: E): void {
    const newNode = new BidirectionalNode<E>(e);

    newNode.next = this.dummyTail;
    newNode.prev = this.dummyTail.prev;
    if (this.dummyTail.prev) {
      this.dummyTail.prev.next = newNode;
    }
    this.dummyTail.prev = newNode;

    this.size++;
  }

  /**
   * Inserts the specified element at the specified position in this list.
   * Shifts the element currently at that position (if any) and any
   * subsequent elements to the right (adds one to their indices).
   *
   * @param index index at which the specified element is to be inserted
   * @param e e to be inserted
   * @throws IndexOutOfBoundsException
   */
  add(index: number, e: E): void {
    if (!(index >= 0 && index <= this.size)) {
      throw new Error(`Index: ${index}, Size: ${this.size}`);
    }

    const prevNode = this.getNode(index - 1);
    const newNode = new BidirectionalNode<E>(e);
    newNode.prev = prevNode;
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    if (newNode.next) {
      newNode.next.prev = newNode;
    }

    this.size++;
  }

  getNode(index: number): BidirectionalNode<E> {
    if (!(index >= -1 && index < this.size)) {
      throw new Error(`Index: ${index}, Size: ${this.size}`);
    }

    let currentNode: BidirectionalNode<E>;

    if (index < this.size / 2) {
      currentNode = this.dummyHead;

      for (let i = -1; i < index; i++) {
        if (currentNode.next) {
          currentNode = currentNode.next;
        } else {
          throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
      }
    } else {
      currentNode = this.dummyTail;

      for (let i = this.size; i > index; i--) {
        if (currentNode.prev) {
          currentNode = currentNode.prev;
        } else {
          throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
      }
    }

    return currentNode;
  }

  /**
   * Returns the element at the specified position in this list.
   *
   * @param index index of the element to return
   * @return the element at the specified position in this list
   * @throws IndexOutOfBoundsException
   */
  get(index: number): E {
    if (!(index >= 0 && index < this.size)) {
      throw new Error(`Index: ${index}, Size: ${this.size}`);
    }
    return this.getNode(index).data!;
  }

  /**
   * Replaces the element at the specified position in this list with the
   * specified element.
   *
   * @param index index of the element to replace
   * @param element element to be stored at the specified position
   * @return the element previously at the specified position
   * @throws IndexOutOfBoundsException
   */
  set(index: number, e: E): E {
    if (!(index >= 0 && index < this.size)) {
      throw new Error(`Index: ${index}, Size: ${this.size}`);
    }

    const currentNode = this.getNode(index);
    const oldData = currentNode.data;
    if (currentNode) {
      currentNode.data = e;
    }

    return oldData!;
  }

  /**
   * Removes the element at the specified position in this list.  Shifts any
   * subsequent elements to the left (subtracts one from their indices).
   * Returns the element that was removed from the list.
   *
   * @param index the index of the element to be removed
   * @return the element previously at the specified position
   * @throws IndexOutOfBoundsException
   */
  remove(index: number): E {
    if (!(index >= 0 && index < this.size)) {
      throw new Error(`Index: ${index}, Size: ${this.size}`);
    }

    const currentNode = this.getNode(index);
    if (currentNode.prev && currentNode.next) {
      currentNode.prev.next = currentNode.next;
      currentNode.next.prev = currentNode.prev;
    }

    this.size--;

    return currentNode.data!;
  }

  print(): void {
    let currNode: BidirectionalNode<E> | null = this.dummyHead;

    process.stdout.write("dummy head <-> ");

    while (currNode && currNode.next !== this.dummyTail) {
      currNode = currNode.next;
      if (currNode) {
        process.stdout.write(currNode.data + " <-> ");
      }
    }

    process.stdout.write("dummy tail\n");
  }
}

const list: DoublyLinkedList<number> = new DoublyLinkedList<number>();

// Test addFirst()
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
process.stdout.write("After addFirst(): ");
list.print(); // Expected output: 1 <-> 2 <-> 3 <-> null

// Test addLast()
list.addLast(4);
list.addLast(5);
process.stdout.write("After addLast(): ");
list.print(); // Expected output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> null

// Test add(index, element)
list.add(0, 0); // Add 0 at the beginning
list.add(6, 6); // Add 6 at the end
list.add(4, 99); // Add 99 at index 4
process.stdout.write("After add(index, element): ");
list.print(); // Expected output: 0 <-> 1 <-> 2 <-> 3 <-> 99 <-> 4 <-> 5 <-> 6 <-> null

// Test get(index)
process.stdout.write("Element at index 3: " + list.get(3)); // Expected output: 3

// Test set(index, element)
list.set(4, 100);
process.stdout.write("After set(index, element): ");
list.print(); // Expected output: 0 <-> 1 <-> 2 <-> 3 <-> 100 <-> 4 <-> 5 <-> 6 <-> null

// Test remove(index)
list.remove(0); // Remove the first element
list.remove(6); // Remove the last element
process.stdout.write("After remove(index): ");
list.print(); // Expected output: 1 <-> 2 <-> 3 <-> 100 <-> 4 <-> 5 <-> null

 

Linear Probing Hash Table 구현

TypeScript로 만든 Linked List를 import 하여 사용하는 방식으로 구현했다.

class Entry<K, V> {
  public key: K;
  public value: V;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

import { DoublyLinkedList as LinkedList } from "../SinglyLinkedList/DoublyLinkedList"; // Doubly Linked List

class ChainingHashTable<K, V> {
  private table: Array<LinkedList<Entry<K, V>>>; //buckets
  private numberOfItems: number;

  constructor(capacity: number) {
    // this.table = new LinkedList[capacity];
    this.table = new Array<LinkedList<Entry<K, V>>>(capacity);
    this.numberOfItems = 0;

    for (let i = 0; i < capacity; i++) {
      this.table[i] = new LinkedList<Entry<K, V>>();
    }
  }

  // TODO: Change hashcode -> Object.hashcode()
  private hash(key: String): number {
    let hashcode: number = 0;

    for (let i = 0; i < key.length; i++) {
      hashcode += key.charCodeAt(i);
    }

    return hashcode % this.table.length;
  }

  // TODO: when key duplicate, update value
  public put(key: K, value: V): void {
    const indexOfBucket: number = this.hash(String(key));
    const bucket: LinkedList<Entry<K, V>> = this.table[indexOfBucket];

    for (let i = 0; i < bucket.size; i++) {
      const entry: Entry<K, V> = bucket.get(i);
      if (entry.key === key) {
        entry.value = value;
        return;
      }
    }

    bucket.add(0, new Entry<K, V>(key, value));
    this.numberOfItems++;
  }

  public remove(key: K): Entry<K, V> | null {
    if (this.isEmpty()) {
      throw new Error("Hash Table is Empty!");
    }

    const indexOfBucket: number = this.hash(String(key));
    const bucket: LinkedList<Entry<K, V>> = this.table[indexOfBucket];

    for (let i = 0; i < bucket.size; i++) {
      const entry: Entry<K, V> = bucket.get(i);
      if (entry.key === key) {
        bucket.remove(i);
        this.numberOfItems--;

        return entry;
      }
    }

    return null;
  }

  public get(key: K): V | null {
    const indexOfBucket: number = this.hash(String(key));
    const bucket: LinkedList<Entry<K, V>> = this.table[indexOfBucket];

    for (let i = 0; i < bucket.size; i++) {
      const entry: Entry<K, V> = bucket.get(i);
      if (entry.key === key) {
        return entry.value;
      }
    }

    return null;
  }

  public isEmpty(): boolean {
    return this.numberOfItems === 0;
  }
}

const hashTable: ChainingHashTable<string, string> = new ChainingHashTable<string, string>(10);
hashTable.put("강호동", "010-1111-1111");
hashTable.put("유재석", "010-2222-2222");
hashTable.put("이수근", "010-3333-3333");

console.log(hashTable.get("강호동")); // "010-1111-1111"
console.log(hashTable.get("유재석")); // "010-2222-2222"
console.log(hashTable.get("이수근")); // "010-3333-3333"

 

후기

사실상 직접 구상하고 구현하는것이 아닌 이미 Java코드로 예시가 주어져있었고 그저 TypeScript로 변환하였지만, 자료구조에 대한 이해도를 높이는 느낌이 들었다.

또, 한번에 이렇게 바꾸면 되겠지 ? 하다가도 안돼는 과정을 겪으면서 class구조와 사용방법에 대해 고민하는 시간이 많았는데, 그만큼 실무에서 class에 대해 좀더 깊이있는 사용법을 익힌것같다.