[코딩 테스트] 8일차: 해시 테이블

해시 테이블

해시 테이블은 키-값 쌍을 저장하는 자료구조로, 빠른 검색, 삽입, 삭제 작업을 지원합니다. 해시 함수(hash function)를 사용하여 키를 해시 값으로 변환하고, 이 해시 값을 인덱스로 사용하여 배열에 값을 저장합니다.

해시 테이블의 주요 개념

• 해시 함수: 키를 해시 값으로 변환하는 함수
• 해시 값: 해시 함수에 의해 생성된 값
• 버킷: 해시 값에 대응하는 저장 공간
• 충돌 해결: 동일한 해시 값을 가진 여러 키를 처리하는 방법

충돌 해결 방법

• 체이닝(Chaining): 각 버킷에 연결 리스트를 사용하여 충돌을 해결
• 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 버킷을 찾아 값을 저장

해시 테이블 구현

체이닝을 이용한 해시 테이블 구현

JavaScript에서의 체이닝을 이용한 해시 테이블 구현

class HashTable {
  constructor(size = 50) {
    this.buckets = new Array(size);
    this.size = size;
  }

  // 해시 함수
  hash(key) {
    let hashValue = 0;
    for (let char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.size;
  }

  // 키-값 쌍 저장
  set(key, value) {
    const index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    this.buckets[index].push([key, value]);
  }

  // 키에 대한 값 반환
  get(key) {
    const index = this.hash(key);
    if (!this.buckets[index]) {
      return null;
    }
    for (let [k, v] of this.buckets[index]) {
      if (k === key) {
        return v;
      }
    }
    return null;
  }

  // 키-값 쌍 삭제
  delete(key) {
    const index = this.hash(key);
    if (!this.buckets[index]) {
      return null;
    }
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true;
      }
    }
    return false;
  }
}

const ht = new HashTable();
ht.set("name", "Alice");
ht.set("age", 25);
console.log(ht.get("name")); // "Alice"
console.log(ht.get("age")); // 25
ht.delete("name");
console.log(ht.get("name")); // null

Python에서의 체이닝을 이용한 해시 테이블 구현

class HashTable:
    def __init__(self, size=50):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    # 해시 함수
    def hash(self, key):
        hash_value = sum(ord(char) for char in key)
        return hash_value % self.size

    # 키-값 쌍 저장
    def set(self, key, value):
        index = self.hash(key)
        for i, kv in enumerate(self.buckets[index]):
            k, v = kv
            if key == k:
                self.buckets[index][i] = (key, value)
                break
        else:
            self.buckets[index].append((key, value))

    # 키에 대한 값 반환
    def get(self, key):
        index = self.hash(key)
        for k, v in self.buckets[index]:
            if key == k:
                return v
        return None

    # 키-값 쌍 삭제
    def delete(self, key):
        index = self.hash(key)
        for i, kv in enumerate(self.buckets[index]):
            k, v = kv
            if key == k:
                del self.buckets[index][i]
                return True
        return False

ht = HashTable()
ht.set("name", "Alice")
ht.set("age", 25)
print(ht.get("name")) # "Alice"
print(ht.get("age")) # 25
ht.delete("name")
print(ht.get("name")) # None

오픈 어드레싱을 이용한 해시 테이블 구현

JavaScript에서의 오픈 어드레싱을 이용한 해시 테이블 구현

class HashTable {
  constructor(size = 50) {
    this.buckets = new Array(size);
    this.size = size;
  }

  // 해시 함수
  hash(key) {
    let hashValue = 0;
    for (let char of key) {
      hashValue += char.charCodeAt(0);
    }
    return hashValue % this.size;
  }

  // 키-값 쌍 저장
  set(key, value) {
    let index = this.hash(key);
    while (this.buckets[index] && this.buckets[index][0] !== key) {
      index = (index + 1) % this.size;
    }
    this.buckets[index] = [key, value];
  }

  // 키에 대한 값 반환
  get(key) {
    let index = this.hash(key);
    while (this.buckets[index]) {
      if (this.buckets[index][0] === key) {
        return this.buckets[index][1];
      }
      index = (index + 1) % this.size;
    }
    return null;
  }

  // 키-값 쌍 삭제
  delete(key) {
    let index = this.hash(key);
    while (this.buckets[index]) {
      if (this.buckets[index][0] === key) {
        this.buckets[index] = undefined;
        return true;
      }
      index = (index + 1) % this.size;
    }
    return false;
  }
}

const ht = new HashTable();
ht.set("name", "Alice");
ht.set("age", 25);
console.log(ht.get("name")); // "Alice"
console.log(ht.get("age")); // 25
ht.delete("name");
console.log(ht.get("name")); // null

Python에서의 오픈 어드레싱을 이용한 해시 테이블 구현

class HashTable:
    def __init__(self, size=50):
        self.size = size
        self.buckets = [None] * size

    # 해시 함수
    def hash(self, key):
        hash_value = sum(ord(char) for char in key)
        return hash_value % self.size

    # 키-값 쌍 저장
    def set(self, key, value):
        index = self.hash(key)
        while self.buckets[index] is not None and self.buckets[index][0] != key:
            index = (index + 1) % self.size
        self.buckets[index] = (key, value)

    # 키에 대한 값 반환
    def get(self, key):
        index = self.hash(key)
        while self.buckets[index] is not None:
            if self.buckets[index][0] == key:
                return self.buckets[index][1]
            index = (index + 1) % self.size
        return None

    # 키-값 쌍 삭제
    def delete(self, key):
        index = self.hash(key)
        while self.buckets[index] is not None:
            if self.buckets[index][0] == key:
                self.buckets[index] = None
                return True
            index = (index + 1) % self.size
        return False

ht = HashTable()
ht.set("name", "Alice")
ht.set("age", 25)
print(ht.get("name")) # "Alice"
print(ht.get("age")) # 25
ht.delete("name")
print(ht.get("name")) # None

연습 문제

문제 1: 가장 빈번하게 등장하는 요소 찾기

주어진 배열에서 가장 빈번하게 등장하는 요소를 찾는 프로그램을 작성하세요.

JavaScript

function mostFrequent(arr) {
  let hashTable = new HashTable();
  let maxCount = 0;
  let mostFrequentElement;

  for (let elem of arr) {
    let count = hashTable.get(elem) || 0;
    count++;
    hashTable.set(elem, count);

    if (count > maxCount) {
      maxCount = count;
      mostFrequentElement = elem;
    }
  }

  return mostFrequentElement;
}

let arr = [1, 3, 2, 1, 4, 1, 3, 2, 3, 3];
console.log(mostFrequent(arr)); // 3

Python

def most_frequent(arr):
    hash_table = HashTable()
    max_count = 0
    most_frequent_element = None

    for elem in arr:
        count = hash_table.get(elem) or 0
        count

 += 1
        hash_table.set(elem, count)

        if count > max_count:
            max_count = count
            most_frequent_element = elem

    return most_frequent_element

arr = [1, 3, 2, 1, 4, 1, 3, 2, 3, 3]
print(most_frequent(arr)) # 3

결론

이번 글에서는 코딩 테스트 준비를 위해 해시 테이블에 대해 배웠습니다. 이를 통해 해시 테이블의 개념과 충돌 해결 방법(체이닝, 오픈 어드레싱), 그리고 해시 테이블 구현 방법을 익힐 수 있었습니다. 다음 글에서는 정렬 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!