[자료구조]해시테이블(HashTable) 이란?

1. 해시테이블(HashTable) 이란?

해시테이블(HashTable)은 데이터를 키-값(key-value) 쌍으로 저장하는 자료구조 입니다.

해시테이블은 해시함수를 이용해 키를 해시값으로 변환한 후,

이 해시값을 인덱스로 사용해 배열의 특정 위치에 값을 저장하는 방식으로 동작합니다.

 

 

해시테이블(HashTable) 에 키와 값을 넣는 과정

1. key의 해시코드를 계산

2. 해시코드를 이용해 배열의 index를 구함

3. 키와 값을 해당 index에 저장(충돌에 대비해 배열의 각 index에는 키와 값으로 이루어진 연결리스트 사용)

 

 

해시(hash) 함수

해시함수는 입력된 키를 규칙에 따라 해시코드로 변환하는 함수입니다.

잘 만들어진 해시 함수는 다음과 같은 특징을 가집니다.

• 균등 분포: 키가 고르게 분포되어 충돌을 최소화
• 효율성: 해시함수의 계산이 빠르고 효율적

 

 

2. 충돌

해시함수가 서로 다른 키를 동일한 해시코드로 변환할때 발생하는 문제를 충돌(Collision)이라고 합니다.

해시테이블은 충돌을 처리하기 위해 여러가지 기법을 사용합니다.

 

체이닝(Chaining)

같은 해시값을 가진 키-값 쌍들을 연결리스트(linked list)로 저장합니다.

 

개방주소법(Open Addressing)

충돌이 발생하면 다른 빈 자리를 찾아 데이터를 저장합니다.

대표적인 방법으로 선형 탐사(linear probing), 이차 탐사(quadratic probing), 이중 해싱(double hashing) 등이 있습니다.

 

 

충돌(collision)이 발생하는 경우

1. 키(key)는 다른데 해시코드(hashCode)가 같은 경우

2. 해시코드(hashCode)는 다른데 index가 같은 경우

 

 

 

3. 해시테이블의 장단점

장점

• 평균적으로 매우 빠른 검색, 삽입, 삭제 속도를 가집니다.
• 특정 키로 데이터에 직접 접근할 수 있어 효율적입니다.

단점

• 해시 함수가 비효율적일 경우 충돌이 많이 발생하여 성능이 저하될 수 있습니다.
• 저장된 데이터의 순서가 없으며, 데이터의 순차적 접근이 어렵습니다.

 

 

4. 시간 복잡도

데이터의 검색, 삽입, 삭제가 평균적으로 O(1)의 시간복잡도를 가집니다.

하지만 데이터의 충돌이 자주 발생하여 최악의 경우 수행시간은 O(N)이 됩니다. (N=키의 개수)

 

 

 

5. Java에서 해시테이블

5.1. 해시테이블 기능들을 구현해보기

1. 키를 입력받음

2. 입력받은 키를 해시 알고리즘을 통해 해시코드로 만듦

     입력받은 문자열의 각 아스키값을 더해 해시코드로 만드는 방법 사용

// getHashCode
c(99) + o(111) + d(100) + e(101) = 411
b(98) + e (101) + e (101) = 300
...

 

* 아스키코드

대문자 A = 65

소문자 a = 97

 

 

3. 해시코드를 이용해 배열의 index를 구함

hashCode % size(배열크기)  나머지를 index로 사용

배열의 크기가 3 인 경우

// convert to index(hash code)
411 % 3 = 0
300 % 3 = 0
...

 

 

4. 코드

import java.util.LinkedList;

public class HashTable {
    // node: HashTable 에 저장할 데이터를 담음
    class Node {
        String key;
        String value;

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

        String value(){
            return value;
        }
        void value(String value){
            this.value = value;
        }
    }

    // data를 저장할 LinkedList 배열
    LinkedList<Node>[] data;

    public HashTable(int size) {
        this.data = new LinkedList[size];
    }

    // key를 받아서 hashCode를 반환
    int getHashCode(String key) {
        int hashcode = 0;
        for(char c : key.toCharArray()) {
            hashcode += c; // char 문자 c 가 아스키코드로 변환되어 더해짐
        }
        return hashcode;
    }

    // hashcode 를 index로 변환
    int convertToIndex(int hashcode){
        return hashcode % data.length;
    }

    // index 로 배열방을 찾은 이후, 배열방에 node가 여러개 존재하는 경우
    // 검색키로 해당 node를 찾아오는 함수
    Node searchKey(LinkedList<Node> list, String key){
        if(list == null) return null;
        for(Node node : list) {
            if(node.key.equals(key)) {
                return node;
            }
        }
        return null;
    }

    // data 를 받아서 저장
    public void put(String key, String value){
        int hashcode = getHashCode(key);
        int index = convertToIndex(hashcode);
        System.out.println("key:" + key + ", hashcode:"+ hashcode +", index:"+index);
        LinkedList<Node> list = data[index];
        if(list == null) {
            list = new LinkedList<Node>();
            data[index] = list;
        }
        // 배열방에 기존 key로 노드를 가지고 있는지 받아온다.
        Node node = searchKey(list, key);
        if(node == null) { // 없으면
            list.addLast(new Node(key, value));
        } else {// 있으면 해당 값을 대체하여 중복키를 처리
            node.value(value);
        }

    }

    // 키로 data를 가져옴
    public String get(String key){
        int hashcode = getHashCode(key);
        int index = convertToIndex(hashcode);
        LinkedList<Node> list = data[index];
        Node node = searchKey(list, key);
        return node == null ? "Not Found" : node.value;
    }

}

 

 

실행

import com.data.hash.HashTable;

public class Main {

    public static void main(String[] args) {
        hashTableTest();
    }

    public static void hashTableTest(){
        HashTable h = new HashTable(3);
        h.put("code", "Have a good day");
        h.put("bee", "You look great today");
        h.put("king", "You can do it");
        h.put("apple", "You're almost there");
        h.put("code", "I'm so proud of you"); // 중복키

        System.out.println(h.get("code"));
        System.out.println(h.get("bee"));
        System.out.println(h.get("king"));
        System.out.println(h.get("apple"));
        System.out.println(h.get("banana")); // 없는 데이터
    }
}

 

 

 

5.2. 자바 HashTable 클래스 사용하기

자바에서 HashTable 클래스와 HashMap 클래스를 사용해 해시테이블을 구현할 수 있습니다.

HashTable은 동기화(synchronized)가 되어 있어 멀티스레드 환경에서 안전하지만, HashMap은 동기화 되지 않아 단일 스레드 환경에서 성능이 더 좋습니다.

 

import java.util.Hashtable;

public class Main {
    public static void main(String[] args) {
        Hashtable<String, Integer> table = new Hashtable<>();
        
        // 데이터 삽입
        table.put("apple", 10);
        table.put("banana", 20);
        
        // 데이터 검색
        int value = table.get("apple");
        System.out.println("apple의 값: " + value);
        
        // 데이터 삭제
        table.remove("banana");
    }
}

 

 

 

---

참고자료

위키백과 - 해시 테이블

youtube - 엔지니어 대한민국님

chat gpt