[Data Structure 기초] HashTable

 

HashTable(해쉬테이블)

- key와 value를 대응시켜 저장하는 선형 데이터 구조

- key 를 통해 해당 데이터에 빠르게 접근 가능

- 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정을 Hashing이라고 함

- 병렬 프로그래밍을 지원하여 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황일 때 사용하기 적합

 

 

 

해시 충돌 해결 방법 

1. 개방 주소법(Open Address) : 충돌 시, 테이블에서 비어있는 공간의 hash를 찾아 데이터를 저장하고

 hash와 value가 1:1 관계 유지

 

  비어있는 공간 탐색 방법에 따라 분류

    - 선형 탐사법(Linear Probing) : 충돌 발생 지점부터 이후의 빈 공간을 순차적으로 탐사, 

  반복된 충돌 발생시 해당 지점 주변에 데이터가 몰리는 경우 일차 군집화 문제 발생

    - 제곱 탐사법(Quadratic Probing) : 충돌 발생 지점부터 이후의 빈 공간을 n 제곱 만큼의 간격을 투고 탐사,

  일차 군집화 문제 일부를 보완했지만 이차 군집화 문제 발생 가능성이 있음

    - 이중 해싱 (Double Hashing) : 해싱 함수를 이중으로 사용(1: 최소 해서 구할 때 / 2: 충돌 발생시 탐사 이동 간격

  구할 때), 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨

 

2. 분리 연결법(Seperate Chaining) : 해시 테이블을 연결 리스트로 구성,

 충돌 발생 시 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결

 

HashTable 시간복잡도

접근, 탐색 , 추가 , 삭제  : O(1)

 

연산
put(Object key, Object value)	key-value 쌍을 추가
get(Object key)	지정된 key에 해당하는 value를 반환
remove(Object key)	지정된 key와 해당하는 value를 제거
containsKey(Object key)	지정된 key가 Hashtable에 포함되어 있는지 여부를 반환  (있으면 true)
keys()	모든 key를 담은 Enumeration을 반환 (있으면 true)
size( )	Hashtable의 key-value 쌍의 수를 반환
clear()	Hashtable의 모든 key-value 쌍을 제거

 

//해시테이블 사용예제

import java.util.Hashtable;
import java.util.Map;
//20240227
public class hashTable {
    //해시 함수
    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);

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

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

}

 

import java.util.Hashtable;
import java.util.Map;

//20240227
//해시 테이블 - 배열로 직접 구현

class MyHashTable{
    Integer[] table;
    int elemCnt;

    MyHashTable(){}
    MyHashTable(int size){
        this.table = new Integer[size];
        this.elemCnt = 0;
    }

    public int getHash(int key){
        return key% this.table.length;
    }

    public void setValue(int key, int data){
        int idx = this.getHash(key);
        this.table[idx] = data;
        this.elemCnt++;

    }

    public int getValue(int key){
        int idx = this.getHash(key);
        return this.table[idx];
    }

    public void removeValue(int key){
        int idx = this.getHash(key);
        this.table[idx] = null;
        this.elemCnt--;
    }

    public void printHashTable(){
        System.out.println("=== Hash Table ===");
        for (int i = 0; i < this.table.length; i++) {
            System.out.println(i + " : " + this.table[i]);
        }
    }

}

public class hashTablePractice01 {
    public static void main(String[] args){
        //Test code
        MyHashTable ht = new MyHashTable(7);
        ht.setValue(1, 1);
        ht.setValue(2, 2);
        ht.setValue(3, 3);
        ht.setValue(4, 4);
        ht.setValue(5, 5);
        ht.printHashTable();

        ht.setValue(8, 6);
        ht.printHashTable();

    }

}

 

장점

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

단점

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

 

 

HashMap과 Hashtable 클래스의 차이점

- Thread-safe 여부
Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다. 그렇기에 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다.

-  Null 값 허용 여부
Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.

-  Enumeration 여부
Hashtable은 not fail-fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않는다.
HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있다.

 

 

 

 

 

관련link

https://hoehen-flug.tistory.com/35

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

https://velog.io/@realgreatcode/%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94-Hash-Table

해시테이블 HashTable

https://ittrue.tistory.com/153

[Java] 자바 HashTable 개념 정리 및 활용

https://devlog-wjdrbs96.tistory.com/253

[Java] HashMap vs Hashtable 차이는 무엇일까?