Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] ν•΄μ‹œ ν…Œμ΄λΈ”(Hash Table)

πŸ“¦[DS,Algorithm] ν•΄μ‹œ ν…Œμ΄λΈ”(Hash Table)
DataStructure Algorithm

1️⃣ ν•΄μ‹œ ν…Œμ΄λΈ”(Hash Table).

ν•΄μ‹œ ν…Œμ΄λΈ”(Hash Table)은 데이터λ₯Ό ν‚€-κ°’ 쌍(key-value pairs)으둜 μ €μž₯ν•˜λŠ” μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.

ν•΄μ‹œ ν…Œμ΄λΈ”μ€ ν•΄μ‹œ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ ν‚€λ₯Ό ν•΄μ‹œ κ°’μœΌλ‘œ λ³€ν™˜ν•˜κ³ , 이 ν•΄μ‹œ 값을 인덱슀둜 μ‚¬μš©ν•˜μ—¬ λ°°μ—΄μ—μ„œ 값을 μ €μž₯ν•˜κ±°λ‚˜ κ²€μƒ‰ν•©λ‹ˆλ‹€.

이λ₯Ό 톡해 데이터에 λΉ λ₯΄κ²Œ μ ‘κ·Όν•  수 μžˆμŠ΅λ‹ˆλ‹€.

1️⃣ ν•΄μ‹œ ν…Œμ΄λΈ”μ˜ ꡬ성 μš”μ†Œ.

  1. ν‚€(key) : 각 데이터λ₯Ό μ‹λ³„ν•˜κΈ° μœ„ν•œ κ³ μœ ν•œ μ‹λ³„μžμž…λ‹ˆλ‹€.

  2. κ°’(Value) : 킀와 μ—°κ΄€λœ λ°μ΄ν„°μž…λ‹ˆλ‹€.

  3. ν•΄μ‹œ ν•¨μˆ˜(Hash Function) : ν‚€λ₯Ό μž…λ ₯으둜 λ°›μ•„ ν•΄μ‹œ 값을 좜λ ₯ν•˜λŠ” ν•¨μˆ˜μž…λ‹ˆλ‹€. 이 ν•΄μ‹œ 값은 보톡 μ •μˆ˜μ΄λ©°, λ°°μ—΄μ˜ 인덱슀둜 μ‚¬μš©λ©λ‹ˆλ‹€.

  4. 버킷(Bucket) : ν•΄μ‹œ 값에 μ˜ν•΄ μΈλ±μ‹±λ˜λŠ” λ°°μ—΄μ˜ 각 μœ„μΉ˜μž…λ‹ˆλ‹€. 각 버킷은 ν•˜λ‚˜μ˜ ν‚€-κ°’ 쌍 λ˜λŠ” 좩돌 처리λ₯Ό μœ„ν•œ 데이터 ꡬ쑰(예: μ—°κ²° 리슀트)λ₯Ό μ €μž₯ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

2️⃣ ν•΄μ‹œ ν•¨μˆ˜μ˜ μ—­ν• .

ν•΄μ‹œ ν•¨μˆ˜λŠ” ν‚€λ₯Ό κ³ μ •λœ 크기의 ν•΄μ‹œ κ°’μœΌλ‘œ λ§€ν•‘ν•©λ‹ˆλ‹€.

이상적인 ν•΄μ‹œ ν•¨μˆ˜λŠ” ν‚€λ₯Ό κ· λ“±ν•˜κ²Œ λΆ„ν¬μ‹œν‚€κ³ , μΆ©λŒμ„ μ΅œμ†Œν™”ν•©λ‹ˆλ‹€.

3️⃣ 좩동(Collision)κ³Ό 좩돌 ν•΄κ²° 방법.

두 개 μ΄μƒμ˜ ν‚€κ°€ λ™μΌν•œ ν•΄μ‹œ 값을 κ°€μ§ˆ λ•Œ 좩돌이 λ°œμƒν•©λ‹ˆλ‹€.

ν•΄μ‹œ ν…Œμ΄λΈ”μ€ μ΄λŸ¬ν•œ μΆ©λŒμ„ μ²˜λ¦¬ν•˜κΈ° μœ„ν•œ μ—¬λŸ¬κ°€μ§€ 방법을 μ œκ³΅ν•©λ‹ˆλ‹€.

  1. 체이닝(Chaining) : 각 버킷에 μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜μ—¬ λ™μΌν•œ ν•΄μ‹œ 값을 κ°–λŠ” λͺ¨λ“  μš”μ†Œλ₯Ό μ €μž₯ν•©λ‹ˆλ‹€. 좩돌이 λ°œμƒν•˜λ©΄ ν•΄λ‹Ή λ²„ν‚·μ˜ λ¦¬μŠ€νŠΈμ— μš”μ†Œλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€.

  2. 개방 μ£Όμ†Œλ²•(Open Addressing) : 좩돌이 λ°œμƒν•˜λ©΄ λ‹€λ₯Έ 빈 버킷을 μ°Ύμ•„ 데이터λ₯Ό μ €μž₯ν•©λ‹ˆλ‹€. 이λ₯Ό μœ„ν•΄ λ‹€μ–‘ν•œ 탐사 방법(예: μ„ ν˜• 탐사, 제곱 탐사, 이쀑 ν•΄μ‹±)을 μ‚¬μš©ν•©λ‹ˆλ‹€.

4️⃣ ν•΄μ‹œ ν…Œμ΄λΈ”μ˜ μ‹œκ°„ λ³΅μž‘λ„.

  • 검색(Search) : O(1)(평균), O(n)(μ΅œμ•…)
  • μ‚½μž…(Insertion) : O(1)(평균), O(n)(μ΅œμ•…)
  • μ‚­μ œ(Deletion) : O(1)(평균), O(n)(μ΅œμ•…)

μ΅œμ•…μ˜ 경우 μ‹œκ°„ λ³΅μž‘λ„λŠ” ν•΄μ‹œ 좩돌둜 인해 λͺ¨λ“  μš”μ†Œκ°€ ν•˜λ‚˜μ˜ 버킷에 μ €μž₯될 λ•Œ λ°œμƒν•©λ‹ˆλ‹€.

κ·ΈλŸ¬λ‚˜, 쒋은 ν•΄μ‹œ ν•¨μˆ˜μ™€ 좩돌 ν•΄κ²° 방법을 μ‚¬μš©ν•˜λ©΄ ν‰κ· μ μœΌλ‘œ O(1)의 μ„±λŠ₯을 μœ μ§€ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

5️⃣ ν•΄μ‹œ ν…Œμ΄λΈ”μ˜ μž₯점과 단점.

μž₯점

  • λΉ λ₯Έ 검색, μ‚½μž…, μ‚­μ œ μ„±λŠ₯(ν‰κ· μ μœΌλ‘œ O(1))
  • ν‚€λ₯Ό μ‚¬μš©ν•˜μ—¬ 데이터에 λΉ λ₯΄κ²Œ μ ‘κ·Ό κ°€λŠ₯

단점

  • ν•΄μ‹œ ν•¨μˆ˜μ˜ μ„±λŠ₯에 의쑴
  • 좩돌 처이 ν•„μš”
  • λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ 증가할 수 있슴(특히 체이닝을 μ‚¬μš©ν•˜λŠ” 경우)

πŸ’» ν•΄μ‹œ ν…Œμ΄λΈ”μ˜ κ΅¬ν˜„ 예제.

μ•„λž˜λŠ” Javaμ—μ„œ κ°„λ‹¨ν•œ ν•΄μ‹œ ν…Œμ΄λΈ”μ„ κ΅¬ν˜„ν•œ μ˜ˆμ œμž…λ‹ˆλ‹€.


// HashTable
import java.util.LinkedList;

class HashTable {
  private class HashNode {
    String key;
    String value;
    HashNode next;

    public HashNode(String key, String value) {
      this.key = key;
      this.value = value;
    }
  }

  private LinkedList<HashNode>[] buckets;
  private int numBuckets;
  private int size;

  public HashTable() {
    numBuckets = 10; // λ²„ν‚·μ˜ 초기 크기
    buckets = new LinkedList[numBuckets];
    size = 0;

    for (int i = 0; i < numBuckets; i++) {
      buckets[i] = new LinkedList<>();
    }
  }

  private int getBucketIndex(String key) {
    int hashCode = key.hashCode();
    int index = hashCode % numBuckets;
    return index < 0 ? index * -1 : index;
  }

  public void put(String key, String value) {
    int bucketIndex = getBucketIndex(key);
    LinkedList<HashNode> bucket = buckets[bucketIndex];

    for (HashNode node : bucket) {
      if (node.key.equals(key)) {
        node.value = value;
        return;
      }
    }

    bucket.add(new HashNode(key, value));
    size++;
  }

  public String get(String key) {
    int bucketIndex = getBucketIndex(key);
    LinkedList<HashNode> bucket = buckets[bucketIndex];

    for (HashNode node : bucket) {
      if (node.key.equals(key)) {
        return node.value;
      }
    }
    return null;
  }

  public String remove(String key) {
    int bucketIndex = getBucketIndex(key);
    LinkedList<HashNode> bucket = buckets[bucketIndex];

    HashNode prev = null;
    for (HashNode node : bucket) {
      if (node.key.equals(key)) {
        if (prev != null) {
          prev.next = node.next;
        } else {
          bucket.remove(node);
        }
        size--;
        return node.value;
      }
      prev = node;
    }
    return null;
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }
}

// Main
public class Main {
  public static void main(String[] args) {
    HashTable hashTable = new HashTable();
    hashTable.put("one", "1");
    hashTable.put("two", "2");
    hashTable.put("three", "3");

    System.out.println("Value for key 'one': " + hashTable.get("one"));
    System.out.println("Value for key 'two': " + hashTable.get("two"));
    System.out.println("Removing key 'one': " + hashTable.remove("one"));
    System.out.println("Contains key 'one': " + (hashTable.get("one") != null));
  }
}

/*
좜λ ₯
Value for key 'one': 1
Value for key 'two': 2
Removing key 'one': 1
Contains key 'one': false
*/