셋(Set)이란?

셋(Set)은 데이터의 중복을 허용하지 않는 자료구조이다.

셋은 순서를 갖지 않을 수 있기 때문에, 특정 위치의 원소에 접근하는 것은 일반적으로 셋의 주요 작업이 아니다. 대신, 항목의 존재 여부를 확인하거나 항목을 추가하거나 제거하는 작업에 초점을 맞춘다.

셋의 특징은 유일성이다. 셋 내의 각 항목은 고유하고, 동일한 항목을 여러 번 추가하려고 한다면 셋에는 한 번만 저장하게 된다.

해시 테이블(Hash Table)과 셋(Set)

해시 테이블과 셋은 기본적으로 다른 개념의 자료구조이지만, 실제로 구현에서는 해시 테이블을 기반으로 한 셋을 많이 사용하게 되므로 이를 해시 셋(Hast Set)이라고 부르기도 한다.

해시 테이블 (Hash Table)

해시 테이블은 키-값 쌍을 저장하는 자료구조이다. 주요 연산은 키를 사용하여 값을 추가, 삭제, 검색하는 것이다. 해시 함수를 사용해서 키를 해시 코드로 변환하고, 이 해시 코드를 인덱스로 사용하여 값을 저장하거나 검색한다.

해시 함수 (Hash Function)

• 키를 입력으로 받아서 정수형의 해시 코드를 반환한다.
  좋은 해시 함수는 키를 고르게 분포시켜서 해시 충돌을 최소화한다.

해시 충돌 (Hash Collision)

• 두 개 이상의 키가 동일한 해시 코드를 가질 때 발생한다.

해시 테이블의 장점

• 평균적으로 O(1)의 시간 복잡도로 데이터의 삽입, 삭제, 검색이 가능하다.
• 키-값 쌍의 저장 및 검색이 빠르므로, 딕셔너리, 캐시 등 다양한 애플리케이션에서 사용된다.

해시 테이블의 단점

• 해시 충돌을 관리하려면 추가적인 메모리나 연산이 필요할 수 있다.

해시 테이블의 추상 자료형

• 데이터 삽입 - set(key, value)
• 데이터 참조 - get(key)
• 데이터 제거 - remove(key)

import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class HashData {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}

class HashTable {
  constructor() {
    this.arr = [];
    for (let i = 0; i < 10; i++) {
      this.arr[i] = new DoublyLinkedList();
    }
  }

  hashFunction(number) {
    return number % 10;
  }

  set(key, value) {
    this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
  }

  get(key) {
    let currentNode = this.arr[this.hashFunction(key)].head;
    while (currentNode != null) {
      if (currentNode.data.key == key) {
        return currentNode.data.value;
      }
      currentNode = currentNode.next;
    }
    return null;
  }

  remove(key) {
    let list = this.arr[this.hashFunction(key)];
    let currentNode = list.head;
    let deletedIndex = 0;
    while (currentNode != null) {
      if (currentNode.data.key == key) {
        return list.deleteAt(deletedIndex);
      }
      currentNode = currentNode.next;
      deletedIndex++;
    }
    return null;
  }
}

export { HashTable };

해시 셋 (Hash Set)

해시 셋은 해시 테이블을 기반으로 한 셋의 구현이다.
해시 셋에서는 값 자체가 키로 사용되며, 중복된 값을 허용하지 않는다.
해시 함수를 사용하여 값의 해시 코드를 계산하고, 이를 인덱스로 사용하여 데이터를 저장하거나 검색한다.

셋의 추상 자료형

• 데이터 삽입 - add(data)
• 데이터 체크 - isContain(data)
• 데이터 제거 - remove(data)
• 셋 비우기 - clear()
• 셋이 비었는지 체크 - isEmpty()
• 모든 데이터 출력 - printAll()

import { HashTable } from './HashTable.mjs';

class HashSet {
  constructor() {
    this.hashTable = new HashTable();
  }

  add(data) {
    if (this.hashTable.get(data) == null) {
      this.hashTable.set(data, -1);
    }
  }

  isContain(data) {
    return this.hashTable.get(data) != null;
  }

  remove(data) {
    this.hashTable.remove(data);
  }

  clear() {
    for (let i = 0; i < this.hashTable.arr.length; i++) {
      this.hashTable.arr[i].clear();
    }
  }

  isEmpty() {
    let empty = true;

    for (let i = 0; i < this.hashTable.arr.length; i++) {
      if (this.hashTable.arr[i].count > 0) {
        empty = false;
        break;
      }
    }

    return empty;
  }

  printAll() {
    for (let i = 0; i < this.hashTable.arr.length; i++) {
      let currentNode = this.hashTable.arr[i].head;
      while (currentNode != null) {
        console.log(currentNode.data.key);
        currentNode = currentNode.next;
      }
    }
  }
}

export { HashSet };