선형 자료구조 - 해시 테이블(Hash Table)

해시 테이블(Hash Table) = 해시 맵, 해시 표

• 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조
  • 해시 함수(Hash Function)를 사용해 키를 특정 인덱스로 변환하여, 데이터를 효율적으로 저장하고 검색
• 해싱
  • 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

 

사용 예시:

• 데이터베이스 인덱싱
• 캐시(Cache) 구현
• 집합(Set)과 맵(Map)과 같은 데이터 구조의 내부 구현

 

장점:

• 빠른 데이터 접근: 평균적으로 **O(1)**의 시간 복잡도로 데이터를 검색할 수 있어, 매우 빠른 데이터 접근을 제공

 

단점:

• 충돌 관리 필요: 해시 함수가 이상적으로 작동하지 않거나 충돌이 많이 발생할 경우 성능이 저하될 수 있음
• 메모리 사용량: 키와 값을 저장하기 위해 추가적인 메모리 공간이 필요

 

 

해시 테이블 구조

• 키: 해시 테이블 접근을 위한 입력 값
• 해시 함수: 키를 해시 값으로 매핑하는 연산
• 해시 값: 해시 테이블의 인덱스
• 해시 테이블: 키-값을 연관시켜 저장하는 데이터 구조

 

 

해시 충돌 (Hash Collision)

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
  • 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우
• 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음

 

 

 

해시 충돌 해결 방법 (1)

개방 주소법 (Open Address)

• 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
• hash와 value가 1:1 관계 유지
• 비어있는 공간 탐색 방법에 따라 분류
  • 선형 탐사법, 제곱 탐사법, 이중 해싱

 

개방 주소법 - 선형 탐사법

• Linear Probing
• 빈 공간을 순차적으로 탐사하는 방법
  • 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
• 일차 군집화 문제 발생
  • 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생

 

개방 주소법 - 제곱 탐사법

• Quadratic Probing
• 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
  • 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
• 일차 군집화 문제 일부 보완
• 이차 군집화 문제 발생 가능성

개방 주소법 - 이중 해싱

• Double hashing
• 해싱 함수를 이중으로 사용
  • 해시함수 1: 최초 해시를 구할 때 사용
  • 해시함수 2: 충돌 발생 시, 탐사 이동 간격을 구할 때 사용
• 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨

 

 

해시 충돌 해결 방법 (2)

분리 연결법 (Separate Chaining)

• 해시 테이블을 연결 리스트로 구성
• 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결
• 하나의 키 값에 대해 동일한 해시 위치에 여러 개의 데이터들이 있을 수도 있음 (1:1 관계 유지 X )

 

시간 복잡도

• 검색(Search): 평균적으로 O(1), 최악의 경우 O(n)
• 삽입(Insert): 평균적으로 O(1), 최악의 경우 O(n)
• 삭제(Delete): 평균적으로 O(1), 최악의 경우 O(n)

 

 

평균적인 경우: 해시 테이블의 강력한 장점은 대부분의 연산이 상수 시간 O(1) 내에 수행

• 이는 해시 함수가 키를 고르게 분포시켜, 충돌이 거의 발생하지 않는 경우에 해당

최악의 경우: 최악의 경우는 모든 키가 동일한 해시 값을 가지는 경우

• 이 경우, 해시 테이블의 모든 요소가 하나의 버킷에 저장되며, 리스트 형태로 저장된 데이터를 순차적으로 검색해야 하므로 시간 복잡도가 O(n)으로 증가

 

 

 

해시 테이블 구현

Java 코드

// 기본 해시 테이블 사용 방법
Hashtable<String, Integer> ht = new Hashtable<>();

ht.put("key1", 10);
ht.put("key2", 20);
ht.put("key3", 30);

for (Map.Entry<String, Integer> item : ht.entrySet()) {
    System.out.println(item.getKey() + " - " + item.getValue());
}

 

 

ht.entreySet() 함수로 키 값에 대응되는 데이터 entry들을 뽑아서  

Map의 Entry로 뽑은 데이터를 받고, for each문을 통해 출력함

Hashtable은 Map 인터페이스를 이용해 만들었기 때문에 Map으로 받아주면 됨 (Map 특징 中 순서X)

 

 

해시 함수 생성 후 해시 충돌 구현 코드

// 선형 자료구조 - 해시 테이블

import java.awt.*;
import java.util.Hashtable;
import java.util.Map;

public class Main {
    // 해시 함수
    public static int getHash(int key) {
        return key % 5;
    }

    public static void main(String[] args) {
        // 기본 해시 테이블 사용 방법
        Hashtable<String, Integer> ht = new Hashtable<>();

        ht.put("key1", 10);
        ht.put("key2", 20);
        ht.put("key3", 30);
        //해시 충돌 시 기존 key3 데이터 사라짐
        ht.put("key3", 50);

        for (Map.Entry<String, Integer> item : ht.entrySet()) {
            System.out.println(item.getKey() + " - " + item.getValue());
        }

        // 해시 충돌 케이스 (해시 함수 사용)
        Hashtable<Integer, Integer> ht2 = new Hashtable<>();
        ht2.put(getHash(1), 10);
        ht2.put(getHash(2), 20);
        ht2.put(getHash(3), 30);
        ht2.put(getHash(4), 40);
        ht2.put(getHash(5), 50);


        System.out.println("== 충돌 전 ==");
        for (Map.Entry<Integer, Integer> item : ht2.entrySet()) {
            System.out.println(item.getKey() + " - " + item.getValue());
        }

        System.out.println("== 충돌 후 ==");
        ht2.put(getHash(6), 60);
        for (Map.Entry<Integer, Integer> item : ht2.entrySet()) {
            System.out.println(item.getKey() + " - " + item.getValue());
        }
    }
}