[Algorithm] 04. 해시테이블 (Hash Table)

해시테이블 (Hash Table)

 

해시테이블(Hash Table)은 빠른 탐색을 위해 key-value 쌍으로 데이터를 저장하는 자료구조이다.

해시 함수 h에 키 값을 입력 받아 얻은 해시값 h(k)을 위치로 사용하여 데이터를 저장한다.

 

 

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

 

직접 주소화 테이블(Direct-address Table)이란 key 값이 k인 데이터를 index k 위치에 저장하는 방식이다.

// key = 출석번호, value = 이름                      // key = ID, value = 이름
   
person[2024] = "박서준"                              person["Id1"] = "박서준"
person[2025] = "임영웅"                              person["Id2"] = "임영웅"
person[2030] = "최재림"                              person["Id3"] = "최재림"
person[2031] = "이호광"                              person["Id4"] = "이호광"

 

그러나 Direct-addres Table을 사용하면 불필요한 공간 낭비와 key 값으로 문자열이 불가하다는 문제가 발생한다.

 

 

💡  해시 테이블 (Hash Table)

 

해시테이블(Hash Table)은 key-value 쌍으로 데이터 저장하는 자료구조로 "h(k)는 키 k의 해시값이다"라고 표현한다.

모든 데이터에 대해 key 값은 무조건 존재해야 하며, 중복되는 key 값이 있어서는 안된다.

(key, value) 데이터를 저장할 수 있는 각 공간을 slot 또는 bucket 이라고 한다.

 

저장, 삭제, 검색의 시간 복잡도는 $O(1)$이지만 collision으로 인하여 $O(n)$이 될 수도 있다.

또한, 데이터가 저장되기 전에 저장 공간이 확보되므로 공간 효율성은 떨어진다.

	Hash Table	Linked List	Array
access	$O(1)$	$O(n)$	$O(1)$
insert	$O(1)$	$O(1)$	$O(n)$
append	$O(1)$	$O(1)$	$O(1)$
delete	$O(1)$	$O(1)$	$O(n)$

 

 

💡  해시 맵 (Hash Map)

 

자바에서 해시테이블(Hash Table)은 Map 인터페이스와 HashMap 구현 클래스를 이용해서 사용한다.

 

 

📍  HashMap 선언

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

// 선언과 동시에 초기화
Map<Integer, String hashtable = new HashMap<>() {{
    put(2024, "박서준");
    put(2025, "임영웅");
}};

 

 

📍  HashMap 연산

// key-value 쌍 추가
hashtable.put(2030, "최재람");

// key에 해당하는 value에 접근
hashtable.get(2024);

// key에 해당하는 value 수정
hashtable.replace(2030, "최재림");

// key-value 쌍 제거
hahstable.remove(2030);

// 해당 key 존재 여부 확인
hashtable.contatinsKey(2024)

 

 

💡  커스텀 클래스

 

value에 단일 값이 아닌 여러 값의 조합을 넣어야 할 경우가 발생하면 클래스를 직접 정의하여 사용한다.

 

 

📍  커스텀 클래스 생성

 

가중치가 있는 그래프의 간선을 저장하는 경우, key (출발 노드) - value (도착 노드와 가중치) 의 조합이 될 것이다.

// 도착 노드와 가중치의 조합을 클래스로 표현
class Edge {
    public int dest;
    public int weight;
    
    public Edge(int dest, int weight) {
    	this.dest = dest;
        this.weight = weight;
    }
}

// 클래스를 이용해 HashMap에 저장
Map<Integer, Edge> graph = new HashMap<>() {{
    put(1, new Edge(3, 5));   // 1 -> 3으로 가는 가중치 5의 간선
    put(2, new Edge(1, 1));   // 2 -> 1으로 가는 가중치 1의 간선
}};

 

 

📍  Key로 사용하는 커스텀 클래스

 

HashMap의 key로 사용할 클래스에는 equals() 메소드와 hashCode() 메소드를 오버라이드 해주어야 한다.

오버라이드 하지 않으면 필드에 어떤 값이 저장되었는지에 상관 없이 모든 오브젝트를 다른 것으로 인식한다.

따라서 contains() 같은 해시값을 기반으로 한 메소드들이 정상적으로 동작하지 않는다.

 

class Point {
    public int x;
    public int y;
    
    public point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Point) {
            Point other = (Point)obj;
            return other.x == this.x && other.y == this.y;
        }
        return false;
    }

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

 

equals() 는 파라미터로 받은 오브젝트가 자신과 같은지 리턴하고 hashCode() 는 해시코드를 리턴한다.

 

이렇게 구현한 클래스는 다음과 같이 사용할 수 있다.

Map<point, Integer> s = new HashMap<>();

s.put(new point(1, 2), 5);
s.put(new point(3, 4), 3);

 

 

💡  해시 셋 (Hash Set)

 

Hash Set은 Hash Table과 유사하지만 key-value 쌍이 아닌 key 만을 저장하는 자료구조이다.

 

 

📍  HashSet 선언

Set<String> hashset = new HashSet<>();

// 선언과 동시에 초기화
Set<String> hashset = new HashSet<>() {{
    add("박서준");
    add("최재림");
}};

 

 

📍  HashSet 연산

// key 추가
hashset.add("임영웅");

// key 제거
hashset.remove(2024);

// 해당 key 존재여부 확인
hashset.containsKey("박서준");

 

 

📍  커스텀 클래스 생성

 

HashMap과 마찬가지로 HashSet에도 단일값이 아닌 여러 값의 조합을 추가해야 하는 경우가 있다.

이때도 마찬가지로 클래스를 생성하여 값을 저장하고 키로 사용하는 클래스는 메소드를 오버라이드 해주어야 한다.

 

 

💡  코딩테스트에서의 활용

 

📍  key-value 쌍의 의미가 강한 경우

 

파이썬의 딕셔너리는 해시가능한(hashable) 자료형과 데이터의 순서쌍이 담긴 자료구조이다.

만약 데이터 간의 관계성을 갖게 되는 문제 상황을 마주하면, 딕셔너리를 통해 표현이 가능하다.

두 가지 이상의 정보를 한 번에 저장해야 한다면, 리스트를 사용하는 것 보다 딕셔너리로 한 번에 묶는 것이 좋다.

 

 

📍  containsKey 메서드를 통한 빠른 데이터 검색

 

리스트는 특정 위치의 데이터를 찾기 위해 $O(n)$의 시간복잡도가 발생하지만 HashMap은 $O(1)$이 소요된다.

반복문을 통해 사용하기 보다는 HashMap의 contatinsKey 메소드를 사용하면 즉각적으로 확인이 가능하다.

 

 

📍  메모리 제한에 걸리지 않는 경우

 

HashMap은 시간복잡도를 줄이기에는 용이하지만, 그만큼 메모리 사용량이 증가한다.