[바미] Hash tables - chaining 알고리즘 구현하기.

chaining?

해시 테이블에서 충돌이 일어나면 chaining 알고리즘을 사용하여 충돌을 해결할 수 있는데, 이 알고리즘은 연결 리스트

를 사용하여 충돌된 데이터를 저장합니다.

 

Chaining을 구현하기 위해서는 먼저 해시 테이블과 연결 리스트가 필요합니다. 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 키를 해시 함수에 입력하여 버킷 인덱스를 계산하고, 해당 버킷에 값을 저장합니다. 연결 리스트는 각 버킷에 저장되는 데이터를 연결하여 저장하는 자료구조입니다.

코드 구현

해시 함수 구현

해시 함수는 키 값을 버킷 인덱스로 변환하는 함수입니다. 이번 예제에서는 간단한 해시 함수를 구현하여 사용해보겠습니다.

function hashFunction(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % size;
}

이 해시 함수는 문자열 키를 받아서 각 문자의 아스키 코드 값을 모두 더한 후, 해시 테이블의 크기로 나눈 나머지를 반환합니다.

해시 테이블과 연결 리스트 구현

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

class ChainingHashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size);
  }

  put(key, value) {
    const index = hashFunction(key, this.size);
    if (this.table[index] == null) {
      this.table[index] = new Node(key, value);
    } else {
      let node = this.table[index];
      while (node.next != null && node.key !== key) {
        node = node.next;
      }
      if (node.key === key) {
        node.value = value;
      } else {
        node.next = new Node(key, value);
      }
    }
  }

  get(key) {
    const index = hashFunction(key, this.size);
    let node = this.table[index];
    while (node != null) {
      if (node.key === key) {
        return node.value;
      }
      node = node.next;
    }
    return null;
  }

  remove(key) {
    const index = hashFunction(key, this.size);
    let node = this.table[index];
    let prev = null;
    while (node != null) {
      if (node.key === key) {
        if (prev == null) {
          this.table[index] = node.next;
        } else {
          prev.next = node.next;
        }
        return true;
      }
      prev = node;
      node = node.next;
    }
    return false;
  }
}

앞서 구현한 해시 함수와 Node 클래스를 사용하여 ChainingHashTable 클래스를 구현했습니다.

해시 테이블의 크기를 인자로 받아서 table 변수에 새로운 배열을 할당했습니다. 이 table 배열의 각 인덱스는 연결 리스트를 구현하는 노드 객체를 참조할 수 있습니다.

put 메소드는 주어진 key와 value를 해시 함수로 인덱싱해서 table 배열의 해당 인덱스에 노드 객체로 저장합니다. 이미 해당 인덱스에 노드 객체가 존재하면, 연결 리스트의 맨 끝까지 순회하면서 key가 일치하는 노드가 있는지 검색합니다. 검색 결과 일치하는 key가 있다면 해당 노드의 value를 갱신하고, 일치하는 key가 없다면 연결 리스트의 맨 끝에 새로운 노드 객체를 추가합니다.

get 메소드는 주어진 key를 해시 함수로 인덱싱해서 table 배열의 해당 인덱스에 위치한 노드부터 순회하면서 key가 일치하는 노드를 검색합니다. 검색 결과 일치하는 key를 가진 노드가 있다면 해당 노드의 value를 반환하고, 없다면 null을 반환합니다.

remove 메소드는 주어진 key를 해시 함수로 인덱싱해서 table 배열의 해당 인덱스에 위치한 노드부터 순회하면서 key가 일치하는 노드를 검색합니다. 검색 결과 일치하는 key를 가진 노드를 찾으면 해당 노드를 삭제합니다. 만약 삭제할 노드가 연결 리스트의 맨 처음 노드라면, table 배열의 해당 인덱스에 새로운 노드 객체를 할당합니다. 삭제에 성공했다면 true를 반환하고, 실패했다면 false를 반환합니다.