해시테이블

Direct-Address Table (직접 주소화 테이블)

Direct-Address Table은 키(key)를 배열의 인덱스로 그대로 사용하는 방식

데이터를 (key, value) 형태로 저장할 때, key가 배열의 인덱스로 사용된다.

예시:

key: 출석번호, value: 이름

(3, 홍길동)

특징

• O(1)의 시간 복잡도로 검색 가능
• 구현이 간단하고 빠름

한계점

1. 공간 낭비
   • key가 드물게 존재하거나 크기가 크면 테이블 크기도 매우 커져야 함
     예) 학번을 key로 쓸 경우 → 200만 개 크기의 배열 필요
2. key는 정수만 가능
   • 문자열 등은 배열 인덱스로 사용 불가 → 해시 함수로 변환해야 함

이러한 단점을 해결한 구조가 Hash Table입니다.

Hash Table (해시 테이블)

Hash Table은 key를 해시 함수를 통해 배열 인덱스로 변환한 후 데이터를 저장하는 구조

1. Hash Function
   • key를 정수 index로 변환
   • index = h(key) 형태
2. Bucket (슬롯)
   • 테이블의 각 위치를 버킷(bucket)이라고 부름
   • 동일한 index에 여러 데이터가 저장될 수도 있음 → 충돌 발생 가능

예시:

(2022397, 홍길동) → h(2022397) = 7
(2022399, 김첨지) → h(2022399) = 0

충돌 (Collision)

다른 key가 같은 해시값을 가질 경우 충돌이 발생

해결 방법:

• Open Addressing
• Separate Chaining
• 보통은 언어에서 제공하는 HashMap, Dictionary 등을 사용

Hash Table vs List

연산	Hash Table	List
검색	O(1)	O(n)
삽입	O(1)	O(n)
삭제	O(1)	O(n)

 

Hash Table은 공간을 많이 쓰고, 정렬이 불가능하다는 단점도 존재

Java에서 해시 테이블 사용

HashMap 선언

Map<Integer, String> map = new HashMap<>();

 

Map<Integer, String> map = new HashMap<>() {{
    put(123456, "String");
}};

주요 연산

map.put(1, "A");          // 삽입
map.get(1);               // 조회
map.replace(1, "B");      // 수정
map.remove(1);            // 삭제
map.containsKey(1);       // 존재 여부 확인

 

HashMap에 사용자 정의 클래스 사용하기

Value에 클래스 사용

class Edge {
    int dest, weight;
    Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }
}

Map<Integer, Edge> graph = new HashMap<>();
graph.put(1, new Edge(3, 5));

Key에 클래스 사용

key로 사용하려면 반드시 equals()와 hashCode()를 오버라이드해야 합니다.

class Point {
    int x, y;

    Point(int x, int y) {
        this.x = x; this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Point) {
            Point p = (Point)obj;
            return this.x == p.x && this.y == p.y;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

사용 예시:

Map<Point, Integer> map = new HashMap<>();
map.put(new Point(1, 2), 5);
map.containsKey(new Point(1, 2)); // true

 

HashMap vs ArrayList

항목	HashMap	ArrayList
정렬	불가능	가능
순서	없음	유지됨
메모리 효율	낮음	높음
접근 속도	빠름 (key 기반)	빠름 (index 기반)

 

• key로 빠르게 데이터를 조회해야 하면 HashMap
• 순서 유지, 정렬이 필요하면 ArrayList 또는 TreeMap