2022-07-27

배열, 집합, 해시 테이블을 한 번에!

배열, 집합, 해시 테이블의 동작 원리와 구현까지 한 번에 알아보자!

배열(Array)

배열은 일반적으로 동일한 유형의 요소를 연속된 메모리 공간에 순차적으로 저장하는 선형 자료구조다.
일반적으로 배열은 길이를 지정해 생성하지만, 자바스크립트의 경우 배열은 유사 객체로 동작하기 때문에,
요소 개수만큼 길이가 커지는 특성이 있다. 튜플(Tuple)은 배열과 동일하지만 불변하는 성질을 가진 자료구조다.

장단점

• 장점: 배열은 인덱스를 사용해 상수 시간으로 요소에 접근할 수 있는 장점이 있다.
• 단점: 배열 중간에 요소를 삽입하거나 삭제 시 요소의 이동(shifting)이 발생하므로 시간 효율이 떨어진다.

사용 사례

• 스택, 큐, 힙, 그래프, 트리 등을 배열을 활용해 표현할 수 있다.
• 동적 프로그래밍에 데이터 저장 테이블로 사용될 수 있다.
• 행렬을 표현하고 조작하는데 사용될 수 있다.

집합(Set)

집합은 중복이 허용되지 않는 고유한 요소의 모음이다. 해시 테이블, 트리 또는 기타 데이터 구조를 사용하여 구현된다.
평균적으로 O(1) 조회시간을 제공하도록 설계되고 필요에 따라 순회하며 요소를 검색할 수 있다.

사용 사례

• 집합은 고유한 요소만 허용하므로 데이터 모음에서 중복을 제거하는 데 사용할 수 있다.
• 합집합, 교집합, 차이와 같은 집합 연산을 수행하는 데 사용할 수 있다.

해시 테이블(Hash Table)

해시 테이블은 해시 맵이라고도 하며 요소가 키-값 쌍으로 구성된 자료구조다.
상황에 따라 다르지만 O(1)의 룩업이 가능해 요소를 저장하고 검색하는 빠르고 효율적인 자료구조다.
해시 함수를 통해 해시 키를 생성하게 되는데, 키가 고르게 분산되도록 신중하게 설계해야 한다.
키가 고르게 분산되지 않으면 해시 충돌이 자주 발생하게 되어 비효율적인 동작이 발생한다.
해시 충돌을 해결하는 여러 가지 방법 중 보편적으로 분리 연결법을 통해 해결한다.
분리 연결법은 충돌이 발생하면 배열에 값을 저장하는 방법이다.
이러한 경우로 해시가 항상 상수 시간의 접근을 보장하지 않는다는 것을 알 수 있다.

해시 함수란 임의의 데이터를 암호화해 해시 키를 생성을 수행하는 함수다.

구현 코드

const defaultHashTableSize = 30

class HashTable {
  constructor() {
    this.buckets = Array.from({ length: defaultHashTableSize }, () => null)
  }

  hash(key) {
    // 각 문자의 UTF 코드로 합산하여 키 값을 생성한다.
    const hash = Array.from(key).reduce((acc, cur) => acc + cur.charCodeAt(), 0)
    // 해시 테이블의 사이즈로 제한하기 위해서 나머지 연산 활용.
    return hash % this.buckets.length
  }

  set(key, value) {
    const keyHash = this.hash(key)
    if (this.buckets[keyHash] !== null) {
      // 충돌이 발생하면 분리 연결법으로 해결한다.
      this.buckets[keyHash] = [...this.buckets[keyHash], [key, value]]
      return
    }
    this.buckets[keyHash] = [[key, value]]
  }

  get(key) {
    // 분리연결법으로 배열에 저장되었을 때 값을 받아오기 위해 find로 처리.
    return (
      this.buckets[this.hash(key)].find((item) => item[0] === key)[1] ?? null
    )
  }

  delete(key) {
    const keyHash = this.hash(key)
    if (this.buckets[keyHash] !== null) {
      const isHas = this.buckets[keyHash].find((item) => item[0] === key)
      if (isHas) {
        this.buckets[keyHash] = this.buckets[keyHash].filter(
          (item) => item[0] !== key
        )
      }
    }
  }
}

참조

누구나 자료 구조와 알고리즘 - 길벗