해시 테이블

해시 테이블(Hash Table) 또는 해시맵(Hash Map)은 키를 값에 매핑할 수 있는 구조이다.
해시 테이블은 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1)이라는 점이다. 즉, 데이터의 양과 상관 없이 빠른 성능을 기대할 수 있다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요 기법 중 하나다.

 

 해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다.

해시 함수는 다음과 같은 특징이 있다.

1.  고정된 출력 크기: 입력 데이터의 크기와 상관없이 항상 고정된 크기의 해시 값을 출력한다.
2. 신속한 계산: 해시 값 계산이 빠르게 이루어진다.
3. 결정론적: 동일한 입력에 대해 항상 동일한 해시 값을 반환한다.
4. 충돌 회피: 서로 다른 두 입력이 같은 해시 값을 가지지 않도록 설계된다. 완벽한 충돌 회피는 불가능하지만, 좋은 해시 함수는 충돌 확률을 최소화한다.
5. 균등 분포: 해시 함수는 입력 데이터가 어떻게 분포되어 있든지 해시 값이 고르게 분포되도록 설계된다.

특징에 대한 부가설명

• 해시 함수는 임의의 크기의 입력을 고정된 크기의 출력으로 변환한다. 따라서 입력 공간은 매우 크고, 출력 공간은 상대적으로 작다. 이 경우, 비둘기집 원리에 의해 여러 입력 값이 동일한 해시 값을 가지는 상황, 즉 충돌(collision)이 발생할 수밖에 없다.
  • 비둘기집 원리는 간단한 수학적 원리이다.
     n 개의 항목을  m 개의 상자(또는 비둘기집)에 넣을 때, 만약  n > m 이면, 적어도 한 상자에는 두 개 이상의 항목이 들어가게 된다는 것이다.
• 로드팩터 (Load Factor)
  • 해시 테이블에서 중요한 개념으로, 해시 테이블의 효율성과 성능에 직접적인 영향을 미친다.
  • 해시 테이블에서 사용 중인 슬롯의 비율을 나타내는 값이다. 이는 해시 테이블의 현재 크기와 저장된 요소 수의 비율로 계산된다.
  • 만약 해시 테이블의 크기가 10이고, 7개의 요소가 저장되어 있다면 로드 팩터는 다음과 같다.
    로드 팩터 = 7 / 10 , 즉 0.7 이다.
  • 로드 팩터는 해시 테이블의 성능과 관련이 깊다. 로드 팩터가 높을수록 해시 테이블이 더 많은 요소를 포함하고 있다는 것을 의미하며, 이는 충돌의 가능성을 증가시킨다. 반대로, 로드 팩터가 낮을수록 충돌 가능성은 낮아지지만 공간 효율성이 떨어진다.
  • 해시 테이블의 로드 팩터가 특정 임계값을 초과하면, 성능 유지를 위해 해시 테이블의 크기를 증가시키는 리사이징을 수행한다. 일반적인 리사이징 전략은 다음과 같다.
    
    • 현재 해시 테이블 크기: 10
      저장된 요소 수: 8
      로드 팩터: 0.8 
      임계 로드 팩터: 0.75
      
      로드 팩터가 0.75를 초과했으므로 해시 테이블 크기를 20으로 늘리고, 모든 요소를 새로운 해시 테이블로 재해시.
       

해시 충돌에 대한 처리방법

• 개별 체이닝
  • 키의 해시값을 계산한다.
  • 해시값을 이용해 배열의 인덱스를 구한다.
  • 같은 인덱스가 있다면 연결 리스트로 연결한다. 아래 그림에서 "A" (55) pointer -> "D" (45) x 부분

• 오픈 어드레싱
  • 충돌이 일어나면 테이블 공간 내에서 탐사(Probing)를 통해 빈 공간을 찾아 해결한다.
  • 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.
  • 선형 탐사의 무제점은 해시 테이블에 저장되는 데이터가 고르게 분포되지 못한다는 것이다.
  • 또한 연속된 데이터 그룹이 생기는 '클러스터링(clustering)' 현상이 발생하는데, 테이블의 특정 위치에 데이터가 몰리게 되고 상대적으로 데이터가 거의 없는 구간이 생긴다. 이는 탐사시간을 오래걸리게 하는 문제를 야기시킨다.

 

해시맵 디자인

설명은 주석 참조

public class MyHashMap {
    static class Node {
        int key, val;
        Node next;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    final Node[] nodes = new Node[1000000];

    public void put(int key, int value) {
        // 해싱 결과를 인덱스로 지정
        int index = key % nodes.length;
        // 해당 인덱스에 노드가 없으면 신규 생성 후 종료 함
        if (nodes[index] == null) {
            nodes[index] = new Node(key, value);
            return;
        }

        // 인덱스에 노드가 존재한다면 연결 리스트로 처리
        Node node = nodes[index];
        while (node != null) {
            // 동일한 키가 있다면 값을 업데이트하고 종료
            if (node.key == key) {
                node.val = value;
                return;
            }

            // 다음 노드가 없다면 종료
            if (node.next == null) break;

            // 다음 노드로 진행
            node = node.next;
        }
        // 마지막 노드 다음으로 연결
        node.next = new Node(key, value);
    }

    public int get(int key) {
        // 해싱 결과를 인덱스로 지정
        int index = key % nodes.length;
        // 인덱스에 노드가 존재하지 않으면 - 1
        if (nodes[index] == null) return - 1;

        // 인덱스에 노드가 존재한다면 일치하는 키 탐색
        Node node = nodes[index];
        while (node != null) {
            // 동일한 키가 있다면 값을 리턴
            if (node.key == key) {
                return node.val;
            }

            // 다음 노드로 진행
            node = node.next;
        }
        // 인덱스를 모두 순회해도 일치하는 키가 없다면 - 1
        return -1;
    }

    public void remove(int key) {
        // 해싱 결과를 인덱스로 지정
        int index = key % nodes.length;
        // 해당 인덱스에 노드가 없다면 종료
        if (nodes[index] == null) return;
        //첫 번째 노드일 때의 삭제 처리
        Node node = nodes[index];
        // 일치하는 키가 있다면
        if (node.key == key) {
            // 다음 노드가 없으면 해당 인덱스는 null 처리
            if (node.next == null) {
                nodes[index] = null;
            // 다음 노드가 있다면 다음 노드를 해당 인덱스로 지정
            } else {
                nodes[index] = node.next;
            }
        }

        Node prev = node;
        while (node != null) {
            // 일치하는 키가 있다면
            if (node.key == key) {
                // 이전 노드의 다음에 현재 노드의 다음을 연결하고 리턴
                prev.next = node.next;
                return;
            }
            // 노드 한 칸씩 이동
            prev = node;
            node = node.next;
        }
    }
}

 

Test Code

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class MyHashMapTest {
    @Test
    public void testPutAndGet() {
        MyHashMap map = new MyHashMap();
        map.put(1, 10);
        map.put(2, 20);
        map.put(3, 30);

        assertEquals(10, map.get(1));
        assertEquals(20, map.get(2));
        assertEquals(30, map.get(3));
        assertEquals(-1, map.get(4));  // key 4가 없을 경우
    }

    @Test
    public void testUpdateValue() {
        MyHashMap map = new MyHashMap();
        map.put(1, 10);
        map.put(1, 15);  // key 1 의 값 없데이트

        assertEquals(15, map.get(1));
    }

    @Test
    public void testRemove() {
        MyHashMap map = new MyHashMap();
        map.put(1, 10);
        map.put(2, 20);
        map.put(3, 30);

        map.remove(2);
        assertEquals(-1, map.get(2));  // key 2 지우기
        assertEquals(10, map.get(1));
        assertEquals(30, map.get(3));

        map.remove(1);
        assertEquals(-1, map.get(1));  // key 1 지우기

        map.remove(3);
        assertEquals(-1, map.get(3));  // key 3 지우기
    }

    @Test
    public void testRemoveNonExistingKey() {
        MyHashMap map = new MyHashMap();
        map.put(1, 10);
        map.put(2, 20);

        map.remove(3);  // key 3이 존재하지 않는 경우 기존 키에 영향을 미치지 않아야 한다.
        assertEquals(10, map.get(1));
        assertEquals(20, map.get(2));
    }

    @Test
    public void testCollisionHandling() {
        MyHashMap map = new MyHashMap();
        int hashTableSize = 1000000;

        // These keys will collide if the hash table size is 1000000
        map.put(1, 10);
        map.put(1 + hashTableSize, 20);
        map.put(1 + 2 * hashTableSize, 30);

        assertEquals(10, map.get(1));
        assertEquals(20, map.get(1 + hashTableSize));
        assertEquals(30, map.get(1 + 2 * hashTableSize));
    }
}