Hash Table (hash map)

• 배열과 해시 함수를 사용하여 map을 구현한 자료구조
• 보통 상수 시간 데이터에 접근하기 때문에 빠름

Map

• key-value의 pair들을 저장하는 ADT
• key는 중복 할 수 없다
• associative array, dictionary 라고도 한다
• 사용처
  • 전화번호 - 이름
  • 투표, 후보리스트 - 득표수

Hash function

• 임의의 크기를 가지는 타입의 데이터를 고정된 크기를 가지는 타입으로 데이터를 변환 시키는 함수
  ex Array -> ArrayList
• 임의의 데이터를 정수로 변환

해시 충돌(Hash Collision)

서로 다른 키가 동일한 해시 값을 가지는 경우 발생

체이닝(Chaining)

체이닝은 해시 충돌이 발생할때, 해당 인덱스에서 링크드리스트로 연결하여 저장하는 방법입니다.

Index	Value
0
1
2
3	A -> B -> C
4

오픈 어드레싱(Open Addressing)

오픈 어드레싱은 해시 충돌이 발생할 때, 해시 값을 재조정하여 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다.
예시) C 인덱스 0 할당 -> 충돌
다음 빈 슬롯(1)에 저장 -> 충돌
다음 빈 슬롯(2)에 저장

Index	Value
0	A
1	B
2	C
3
4

동작

저장

1. 키 값을 넣고 해시 함수로 해시 값을 생성
2. 인덱스 값 계산, index = 해시값 % 해시테이블의 크기
3. 계산된 인덱스 위치에 데이터(키-값 쌍)를 저장
4. 동일한 해시값(= 동일한 인덱스)을 가지는 키들이 여러 개 있을 경우, 체이닝(연결 리스트)이나 오픈 어드레싱 등의 방법으로 충돌을 해결합니다.

예시

key: "apple"
해시 함수 결과: hash("apple") = 12
해시테이블 크기: 10
인덱스 계산: 12 % 10 = 2
인덱스 2에 "apple"의 데이터 저장

Index	Value
0
1
2	("apple", Value)
3
4
5
6
7
8
9

검색

1. 키 값을 넣고 해시 함수로 해시 값을 생성
2. 생성된 해시 값으로 index 계산
3. 이 인덱스에서 키와 매칭되는 값을 검색

삭제

1. 키 값을 넣고 해시 함수로 해시 값을 생성
2. 생성된 해시 값으로 index 계산
3. 이 인덱스에서 키와 매칭되는 값을 삭제
4. 해시 충돌로 인한 데이터 처리
   (링크드 리스트, 오픈어드레스 방식으로 대응했다면 더미 데이터를 넣어줌)

체이닝 삭제 예시

초기 상태

Index	Value
0
1
2
3	A -> B -> C
4

"B" 데이터 삭제 후
-> "B"가 삭제되어 연결 리스트에서 제거

Index	Value
0
1
2
3	A -> C
4

오픈어드레스 삭제 예시

"B" 데이터 삭제 후
-> "삭제됨"으로 마킹, 더미데이터를 체워 줍니다.

Index	Value
0	A
1	(삭제됨)
2	C
3
4

해시 테이블 구현

import java.util.LinkedList;

class HashTable<K, V> {
    // 해시테이블의 배열 크기
    private static final int SIZE = 16;
    private LinkedList<Entry<K, V>>[] table;

    // Entry 클래스는 키와 값을 저장
    private static class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

  
    public HashTable() {
        table = new LinkedList[SIZE];
    }

    // 해시함수
    private int hash(K key) {
        return Math.abs(key.hashCode() % SIZE);
    }

    // 값을 저장하는 메소드
    public void put(K key, V value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }

        // 동일한 키가 존재하는지 확인하고, 존재하면 업데이트
        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        // 키가 존재하지 않으면 새로 추가
        table[index].add(new Entry<>(key, value));
    }

    // 값을 가져오는 메소드
    public V get(K key) {
        int index = hash(key);
        if (table[index] == null) {
            return null;
        }

        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null; // 키가 없으면 null 반환
    }

    // 키에 해당하는 값을 삭제
    public void remove(K key) {
        int index = hash(key);
        if (table[index] != null) {
            table[index].removeIf(entry -> entry.key.equals(key));
        }
    }

    // 해시테이블을 출력
    public void display() {
        for (int i = 0; i < SIZE; i++) {
            if (table[i] != null) {
                for (Entry<K, V> entry : table[i]) {
                    System.out.println("Key: " + entry.key + ", Value: " + entry.value);
                }
            }
        }
    }
}