[자료구조] 해시 테이블 (Hash Table)

0904

---

1. 해시 테이블의 이론과 목적

해시 테이블(Hash Table) : 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조

기본 연산으로는

• 탐색
• 삽입
• 삭제

가 있습니다.

2. 해시테이블의 충돌과 해결

해시테이블에서 가장 문제가 되는 점은 바로 충돌(Collision) 입니다.
충돌에 대해 이해하기 위해서는 먼저 적재율(Load Factor) 에 대해 알고 있어야 합니다.

• 적재율 : 해시테이블의 크기 대비 키의 개수

해시 테이블은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우에는 반드시 충돌이 발생하게 됩니다.

따라서 이와같은 충돌을 해결하기 위한 방법에는 다음과 같은 방법들이 있습니다.

• 해시 테이블의 구조 개선

• 해시 함수 개선

3. 충돌 해결

3.1. 해시 테이블의 구조 개선

해시 테이블의 구조 개선을 위한 대표적인 방법에는 Chaining이라는 방법이 있습니다.

체이닝(Chaining) : 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법

위의 그림은 aa와 cc가 서로 같은 해시를 가리켜 충돌이 난 상황을 가리킵니다.

이 때는 cc를 aa의 뒤에 연결함으로써 충돌을 처리할 수 있습니다.

체이닝을 통해 해시테이블을 구현했을 때의 시간 복잡도는 어떻게 될까요??

• 삽입 : 연결리스트에 추가하기만 하면 되기 때문에 상수시간인 O(1) 이 걸립니다.

• 탐색, 삭제 : 최악의 경우 키 값의 개수인 k에 대해 O(k) 가 걸리게 됩니다.

4. 장단점

4.1. 장점

• key값으로 value에 접근할 수 있어 시간복잡도가 O(1) 로 빠르다.

4.2. 단점

• 정렬된 데이터가 필요하거나
• 키에 대한 검색이 필요할 때
• 데이터의 키가 유일하지 않을 때

해시테이블에 적합하지 않습니다.

5. 활용 문제 풀어보기

package study_02;

import java.util.Enumeration;
import java.util.Hashtable;

public class HashTableTest2 {
	public static void main(String args[]) {
		Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
		ht.put("a", 1);
		ht.put("b", 2);
		ht.put("c", 3);
		ht.get("a");
		ht.get("b");
		System.out.println(ht.get("c"));// 1.
		System.out.println(ht);// 2.
	}
}

1. 위의 실행 결과는?
2. 위의 실행 결과는?

import java.util.Enumeration;
import java.util.Hashtable;


public class testHashtable {
	public static void main(String args[]) {
		Hashtable<String, Integer> ht = new Hashtable<String, Integer>();

		ht.put("abc", 1);
		ht.put("abc1", 2);
		ht.put("abc2", 3);


		Enumeration en = ht.keys();

		while(en.hasMoreElements()) {
			String key = en.nextElement().toString();
			System.out.println(key + " : "+ht.get(key));
		}
	}
}

3. 위의 실행 결과는?

---