[자료구조] 해시 테이블(Hash Table) 자료구조 알아보기 & Java 예제 코드

자료구조 중 해시 테이블(Hash Table)에 대해 알아보자.

---

 

해시 테이블(Hash Table)이란?

해시 테이블(Hash Table)은 효율적인 검색과 삽입 연산을 위해 설계된 자료구조다.

이는 키-값 쌍의 데이터를 저장하는데 사용되며, 각 키는 해시 함수를 통해 고유한 인덱스로 변환되어 배열 내에 저장된다.

 

기본 개념에 대해 살펴보면 다음과 같다.

 

• 해시 함수 : 해시 함수는 키를 해시 값으로 변환하는 함수다. 이 해시 값은 고유한 인덱스로 사용된다.
• 해시 충돌 : 서로 다른 키가 같은 해시 값을 가질 경우 해시 충돌이 발생한다. 이는 해시 함수가 충돌을 완전히 피하는 것이 불가능하기 때문에 주의해야 한다.
• 해시 테이블 : 해시 테이블은 배열로 구성되어 있으며, 각 배열 요소는 버킷 또는 슬롯이라고 불리는 데이터 저장 공간이다.
• 버킷 : 각 버킷은 하나 이상의 키-값 쌍을 저장할 수 있다. 해시 충돌이 발생할 경우 추가적인 데이터를 처리하기 위해 체이닝 또는 개방 주소법과 같은 방식을 사용한다.

 

 

해시 테이블(Hash Table)의 장점 및 단점

 

장점

1. 빠른 검색 및 삽입 : Hash Table은 해시 함수를 사용해 데이터를 저장하므로 데이터에 접근하는 데 상수 시간(O(1))이 소요된다. 따라서 매우 빠른 검색과 삽입이 가능하다.
2. 유연한 크기 조정 : Hash Table은 데이터의 개수에 따라 자동으로 크기를 조정할 수 있다. 이를 통해 메모리 공간의 효율성을 유지하면서도 높은 성능을 유지할 수 있다.
3. 다양한 용도로 활용 가능 : Hash Table은 캐싱, 데이터베이스 인덱싱, 중복 검사 등에 사용될 수 있다.

 

단점

1. 해시 충돌 : 서로 다른 키가 동일한 해시 값에 매핑될 수 있는 해시 충돌이 발생할 수 있다. 충돌이 자주 발생하면 검색 및 삽입 연산의 성능이 저하될 수 있다. 충돌을 해결하기 위해 충돌 해결 방법을 선택해야 합니다.
2. 메모리 사용량 : Hash Table은 해시 버킷과 해시 함수를 사용하기 때문에 일정한 메모리 공간을 필요로 하다. 특히 데이터의 수가 많을 경우 메모리 사용량이 증가할 수 있다.
3. 순서의 무작위성 : Hash Table은 키의 해시 값을 기반으로 데이터를 저장하기 때문에 데이터의 순서가 무작위로 보여진다. 데이터를 순차적으로 접근하는 것이 필요한 경우에는 Hash Table보다는 다른 자료구조를 고려하는 것이 좋다.

 

 

Hash Table 예시 코드(Java)

Java에서는 java.util.HashMap 클래스를 사용해 해시 테이블(Hash Table)을 구현할 수 있다.

 

import java.util.HashMap;

public class HashTableExample {
    public static void main(String[] args) {
        // Hash Table 생성
        HashMap<String, Integer> hashTable = new HashMap<>();

        // 데이터 추가
        hashTable.put("A", 1);
        hashTable.put("B", 2);
        hashTable.put("C", 3);

        // 데이터 접근
        int valueA = hashTable.get("A");
        System.out.println("Value of A: " + valueA);

        // 데이터 삭제
        hashTable.remove("B");

        // 데이터 유무 확인
        boolean containsC = hashTable.containsKey("C");
        System.out.println("Contains C: " + containsC);

        // 모든 키-값 쌍 순회
        for (String key : hashTable.keySet()) {
            int value = hashTable.get(key);
            System.out.println("Key: " + key + ", Value: " + value);
        }
    }
}