[자료구조] HashTable 구현

주재완·2024년 3월 20일

Java 자료구조

자료구조

목록 보기

7/10

HashTable

HashTable 자료구조는 인덱스와 데이터가 있는 배열과는 달리 값에 접근을 하기 위한 "키(key)"와 키로 접근한 "값(value)"으로 구성되어 있는 자료구조입니다.

이제껏 보아왔던 인덱스가 있는 자료들은 인덱스가 모두 0부터 시작하는 정수의 형태였습니다. 하지만 HashTable의 키는 여러가지 자료형이 될 수 있습니다. 과연 어떻게 접근을 할까요?

key로 접근하기

물론 LinkedList처럼 하나하나씩 일일이 다 비교하는 방법이 존재합니다. 하지만 이럴 경우 조회에 사용되는 시간복잡도가 O(N)이 되어서 단순 배열이나 ArrayList에 비해 좋지 않습니다.

배열처럼 조회하는데 시간복잡도가 O(1) 밖에 안걸리면서 key를 사용하는 방법이 없을까 고민하면 다음과 같은 결론이 나옵니다.

그냥 key를 배열 인덱스로, 즉 int 형으로 만들어버리자!

이 때 자바에서는 어떠한 형태든 그것을 독립적인 int형 숫자로 만들어주는 메소드가 있습니다. 바로 (Object).hashCode(), 즉 해쉬함수라 불리는 것입니다.

이 해쉬함수를 이용해서 정수형으로 바꾸고 이를 처리해서 배열의 인덱스로 만들어줍니다. 그러면 사실상 key로 접근하는데 시간복잡도는 상수배, 즉 O(1)이 나오게 됩니다.

과정을 보면 아래와 같습니다.

값을 담아둘 배열을 만듭니다.

(key, value)쌍을 하나 받으면 아래 과정을 거칩니다.

key의 hashCode()를 얻어냅니다.

이 해쉬코드는 인덱스 범위를 만족하는지 알 수 없습니다. 배열의 사이즈와 %연산을 수행하면서 배열 인덱스 범위에 해당하는 숫자로 변환해줍니다.

배열의 인덱스에 해당하는 곳에 value를 넣어줍니다.

그런데... 배열의 사이즈와 %연산을 수행하는 부분에서 분명히 나머지가 겹치는 부분이 발생할 수 있습니다. 그러면 어떻게 해결해야될까?

해시 충돌

해시 충돌(Hash Collision)은 우연히 같은 키 값을 가져서 같은 곳에 저장이 되는 것을 의미합니다. 그리고 들어가는 자료는 제한이 없는데, 저장공간은 제한이 되어 있으므로 비둘기집의 원리에 의해 결국은 분명히 충돌이 발생하게 됩니다.

물론 해쉬함수를 잘 설계해서 해쉬 충돌을 최소화 하는 것도 한가지 방법이긴 합니다만, 언젠가는 해쉬 충돌이 발생하기에 이를 처리하는 방법 역시 생각할 필요가 있습니다.

이런 충돌을 해결하는 방법에는 여러가지가 있습니다.

체이닝(Chaining)

위 그림은 보면 John Smith와 Sandra Dee의 해쉬가 겹쳐서 해쉬 충돌이 발생하는 것을 알 수 있습니다. 하지만 저장하는 방식을 보면 알 수 있듯 일단 같은 저장 주소를 가지되, 저장할 때 연결리스트의 형태로 이어붙이는 것을 확인할 수 있습니다. 이를 체이닝(Chaining)이라 합니다. 자바에서는 이와 같은 체이닝을 사용하고 있습니다.

다만, 치명적인 단점이 존재합니다. 바로 모든 해쉬가 같은 경우, 즉 모든 해쉬가 겹치는 경우 모두 한 연결리스트에 저장이 되어 사실상 값을 조회할 때 O(N)이라는 유명무실한 기능을 가지게 됩니다. 모든 해쉬가 겹치는 것이 아니더라도 해쉬 충돌이 많이 발생하면 값을 조회하는데 시간이 많이 필요하게 됨은 틀림없습니다.

그러므로 체이닝을 할 때에는 해쉬함수를 잘 설정하는 것이 중요합니다.

개방 주소법

또다른 해결 방법으로는 개방 주소법이 있습니다. 체이닝은 해쉬 충돌이 발생해도 저장 주소 그대로 두고 바로 연결리스트로 연결하는 것과 달리 개방 주소법은 아예 새로운 저장 주소로 저장합니다.

새로운 주소를 지정하는 방법에는 아래와 같이 여러가지가 있습니다.

선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

구현

여기서는 자바에서 한 것에 따라 체이닝을 사용하여 구현하였습니다.

MyHashTable class(simple)

class MyHashTable {
	// 간단하게 단일 연결리스트의 Node 클래스 만들기
	class Node {
		String key;
		String value;
		Node next;
		
		Node(String key, String value) {
			this.key = key;
			this.value = value;
			this.next = null;
		}
	}
	
	Node[] head;
	
	MyHashTable(int size) {
		this.head = new Node[size];
	}
	
	int getIdx(String key) {
		return key.hashCode() % head.length;
	}
	
	void put(String key, String value) {
		int idx = getIdx(key);
		Node node = new Node(key, value);
		Node tmp = head[idx];
		
		if(tmp == null) {
			head[idx] = node;
			return;
		} 
		
		while(true) {
			if(tmp.next == null) {
				tmp.next = node;
				break;
			}
			tmp = tmp.next;
		}
	}
	
	String get(String key) {
		int idx = getIdx(key);
		for(Node n = head[idx]; n != null; n = n.next) {
			if(n.key.equals(key)) return n.value;
		}
		return null;
	}
}

테스트

테스트는 월클들과 은근슬쩍 끼여 있는 제 이름을 대상으로 했습니다. (김민재, 손흥민, 이상혁 ~~그리고 저~~...)

??? : 이렇게 개발에도 영향을 주는 김민재 손흥민 페이커 모두 새삼 대단하게 느껴지네요...

public class MyHashTableRun {
	public static void main(String[] args) {
		MyHashTable h = new MyHashTable(4);
		h.put("Kim", "Minjae");
		h.put("Son", "Heungmin");
		h.put("Lee", "Sanghyeok");
		h.put("Joo", "Jaewan");
		System.out.println(h.get("Kim")); // Minjae
		System.out.println(h.get("Son")); // Heungmin
		System.out.println(h.get("Lee")); // Sanghyeok
		System.out.println(h.get("Joo")); // Jaewan
	}
}