[Java/자바] 해시 테이블(HashTable) 구현

자바를 활용한 해시 테이블(HashTable) 구현하기

해시 테이블은 키-값(key-value) 쌍을 저장하며, 특정 키에 대한 값을 빠르게 검색할 수 있는 자료구조입니다. 이번에는 자바를 사용하여 해시 테이블을 구현해보겠습니다.

1. 해시 테이블 클래스 구현

우선 해시 테이블을 구현하기 위한 자바 클래스를 만들겠습니다. 이 클래스는 배열을 이용하여 각 버킷에 키-값 쌍을 저장합니다.

public class HashTable {
  private static final int SIZE = 10;
  private Entry[] table;
  public HashTable() {
    table = new Entry[SIZE];
    for (int i = 0; i < SIZE; i++) {
      table[i] = null;
    }
  } // 해시 함수 구현 
  private int hashFunction(String key) {
    return key.hashCode() % SIZE;
  }
  // 키-값 쌍 저장 
  public void put(String key, String value) {
    int index = hashFunction(key);
    if (table[index] == null) {
      table[index] = new Entry(key, value);
    } else {
      Entry current = table[index];
      while (current.getNext() != null) {
        current = current.getNext();
      }
      current.setNext(new Entry(key, value));
    }
  }
  // 키에 해당하는 값 조회 
  public String get(String key) {
    int index = hashFunction(key);
    if (table[index] == null) {
      return null;
    } else {
      Entry current = table[index];
      while (current != null) {
        if (current.getKey().equals(key)) {
          return current.getValue();
        }
        current = current.getNext();
      }
      return null;
    }
  }
  // 해시 테이블의 각 엔트리를 표현하는 내부 클래스
  private static class Entry {
    private String key;
    private String value;
    private Entry next;
    public Entry(String key, String value) {
      this.key = key;
      this.value = value;
      this.next = null;
    }
    public String getKey() {
      return key;
    }
    public String getValue() {
      return value;
    }
    public Entry getNext() {
      return next;
    }
    public void setNext(Entry next) {
      this.next = next;
    }
  }
}

위 코드에서는 해시 함수를 통해 각 키의 해시값을 구하고, 이를 기반으로 배열의 인덱스를 결정하여 값을 저장하고 조회합니다. 충돌(Collision)을 해결하기 위해 연결 리스트(LinkedList)를 사용합니다.

2. 해시 테이블 사용 예제

이제 구현한 해시 테이블을 사용하여 여러 예제를 살펴보겠습니다.

예제 1: 해시 테이블에 값 저장하기

 

public class Main {
  public static void main(String[] args) {
    HashTable hashTable = new HashTable();
    hashTable.put("apple", "사과");
    hashTable.put("banana", "바나나");
    hashTable.put("grape", "포도");
  }
}

위 예제는 해시 테이블에 세 가지 과일과 그에 해당하는 한글 이름을 저장하는 예제입니다.

예제 2: 해시 테이블에서 값 조회하기

public class Main {
  public static void main(String[] args) {
    HashTable hashTable = new HashTable();
    hashTable.put("apple", "사과");
    hashTable.put("banana", "바나나");
    hashTable.put("grape", "포도");
    String apple = hashTable.get("apple");
    System.out.println("apple: " + apple);
    // apple: 사과 
  }
}

위 예제는 해시 테이블에서 특정 키("apple")에 해당하는 값을 조회하는 예제입니다.