해쉬 테이블 (해시 테이블/hash table) 완전정복+(Java)

해쉬 테이블(hash table)

해쉬 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성되는 자료구조 이다.

해쉬 테이블의 해쉬 함수는 키 값을 받아 그 키의 해쉬값(hash coding 또는 hash value)을 리턴한다.

간단한 해쉬테이블을 시각적으로 표시했을 때, 아래와 같은 그림으로 표시할 수 있다.

 

 

(Author: Jorge Stolfi, 원본: http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg)

해쉬 테이블의 장점은 상수 시간에 탐색이 가능한 것이다.

대신 다른 특징(혹은 단점?)은 순차적인 접근을 지원하지 않는 것이다.

따라서 이러한 특징에 맞는 상황에서 사용되어야 할 것이다.

추가적으로 해쉬 테이블의 특징을 좀 더 알아보자.

- 사용할 키와 해쉬 함수를 잘 선택하여 테이블에 균등하게 항목이 배분되도록 해야 한다.

- 다른 키값에 대해 같은 해쉬값(같은 테이블로 매핑되는 경우)을 가지는 경우 충돌(collision)이라고 한다.

- 충돌 해결 방법에는 여러가지가 있으며 대표적인 방법(책에 설명된)은

  연쇄 해쉬 테이블(chained hash table)과 개방 주소지정 해쉬 테이블(open-addressed hash table)이 있다.

위키피디아에 따르면 해쉬 테이블은 탐색 트리(search tree)나 다른 lookup 구조의 테이블보다 효율적이라고 한다.

이런 이유로 아래와 같은 곳에서 사용이 된다. (참조: http://en.wikipedia.org/wiki/Hash_table#Uses )

- Associative arrays (프로그래밍 랭귀지의 데이터 타입 같은 것. 예를 들면 Python 의 Dictionary 타입?)

- Database indexing

- Caches

- Sets

- Object representation

- Unique data representation

위키피디아에 상세한 설명이 되어 있으니, 해쉬 테이블에 대한 더 많은 정보를 원한다면 방문해 보기 바란다.

http://en.wikipedia.org/wiki/Hash_table

앞으로 나올 용어에 대해서 간단히 설명하면 다음과 같이 사용할 것이다.

n : 테이블의 항목 갯수

m : 버킷의 갯수

a : 부하 계수(load factor). a = n / m

해쉬 테이블 인터페이스

해쉬 테이블에 필요한 인터페이스는 간단한 편이다.

Data Insert, Remove, Lookup 정도?

중요한 건 키 값을 같이 넘겨주는 것이다.

해쉬 함수(hash function)

 

 

해쉬 함수 h 는 키값 k 를 받아 테이블 위치 x 에 매핑하는 함수이다.

k 의 값은 보통 정수임을 가정한다.

k 가 정수가 아니더라도 어렵지 않게 정수로 바꿀 수 있다.

(물론 k 가 같은 값이 나오지 않게 잘 바꿔야 하겠다)

책에서는 간단한 방법 2가지를 제시한다.

- 나눗셈 방법(devision method)

 

으로 표현할 수 있다. 일반적으로 m 의 값으로는 2의 제곱수는 피해서

2의 제곱수에 가깝지 않은 소수를 m 으로 선택한다.

- 곱셈 방법(multiplication method)

 

k*A 한 다음 여기에서 소수 부분만 택하여 m 을 곱한값에서 정수 부분만 택한값을 사용한다.

( A 값은 저렇게 하면 효율적이라고 Donald Knuth 란 분이 이야기 했나 보다. )

이것들은 간단한 방법들이니 좀 더 효율적인 해쉬 함수를 원한다면,

좀 더 공부가 필요하겠다.

충돌 해결(Collision resolution)

출동 해결 방법에는 여러가지가 있다.

좀 더 자세한 건 역시 위키피디아! ( http://en.wikipedia.org/wiki/Hash_table#Collision_resolution )

- 연쇄 해쉬 테이블(Sererate Chaining)

 

 

(Author: Jorge Stolfi, http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_LL.svg )

위 그림과 같이 한 버킷을 링크트 리스트로 구성하는 방법이다.

- 개방 주소지정 해쉬 테이블(Open addressing)

 

 

(Author: Jorge Stolfi,http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_SP.svg )
그림이 좀 헷갈려 보이긴 하지만, 위와 같은 충돌 발생시 다른 버킷에 저장하는 방식이다.

여기서 잠깐, 다른 버킷은 어떻게 선택하는가?

잘 알려진 방법으로는 다음과 같은 3가지 방법이 있다.

1. 선형 조사(Linear probing) : 다음 버킷을 조사. 주클러스터링 현상으로 과다한 조사 발생 가능성 있음.

2. 2중 조사(Quadratic probing) : i^2 번째의 버킷을 조사. 부클러스터링 현상으로 과다한 조사 발생 가능성 있음.

   (i 는 현재까지 조사한 위치의 갯수)

3. 2중 해싱(Double hashing): 해쉬 함수와 보조 해쉬 함수의 결과를 더하는 것이다.

2중 조사와 다른 점은, 키 값에 따라 다음 조사위치가 고정된 것이 아니라 달라진다는 것이다.

수식으로 표현하지면 위와 같다. 그러나 어떤 위치가 두 번 조사되기 전에 모든 위치들이

조사됨을 보장하기 위해 다음의 두 절차 중 하나를 따라야 한다.

a. m이 2의 제곱수이고 h2 가 항상 홀수를 리턴한다.

b. m이 소수이고 h2는 항상 m보다 작은 양수를 리턴해야 한다.

결론

여기에 적은 것은 해쉬 테이블의 일부분일 뿐이다.

이 글에서는 해쉬 테이블의 핵심만 기억하도록 하자.

해쉬 테이블의 정의, 좋은 해쉬 함수가 필요하다는 거, 그리고 충돌 해결이 필요하다는 거 정도?

역시 중요한 것은 실제로 적절한 곳에 사용하는 것이겠지...

해쉬 테이블에 대한 깊이 있는 이해를 위해서는 좀 더 공부가 필요하겠다.

 

(2012.7.2 추가)

Double Hashing이 항상 좋은 것은 아니다.

예를 들면 Double Hashing 함수에서 i 값이 증가 할 때, 그 interval 이 커서

cache 문제가 발생할 수 있다고 한다.

(참고: http://en.wikipedia.org/wiki/Double_hashing )

또한, 인터넷을 검색해서 적절한 second hash function 의 샘플을

찾지를 못하겠다. 나중에 꼭 쓸일이 있게되면 연구해 봐야겠다.

(2012.7.3)

굳이 인터넷을 검색하지 않아도,

책에 적절한 Double Hashing 의 적절한 샘플이 있었다.

(어젠 책이 없는 관계로...)

 

이 식에서 아래와 같은 방법의 해쉬 함수를 사용할 수 있다.

 

 

 

 

 

 

 

원문

http://azza.tistory.com/120

 

 

 

 

 

 

 

 

 

JAVA

 

 

1.

 

 

해쉬 테이블(hash table)

: 여러 개의 통을 만들어 두고 키값을 이용하여 데이터를 넣을 통 번호를 계산하는 자료구조

　키값을 가지고 데이터를 넣을 통의 번호를 계산해서 넣습니다

 

HashMap<String, Integer> hashtable = new HashMap<String, Integer>();  
: 16개의 통으로 구성된 해쉬 테이블을 생성합니다.

HashMap<String, Integer> hashtable = new HashMap<String, Integer>(100);
: 100개의 통으로 구성된 해쉬 테이블을 생성합니다.

-> HashMap : 해쉬 테이블로 사용할 수 있는 클래스, String : 키의 타입, Integer : 데이터 타입

 

＊데이터 넣기
hashtable.put("이햄", new Integer(95));
: 키값("이햄")으로 통번호를 계산하여 그 통에 키 값과 데이터(95)를 넣습니다.

 

＊데이터 찾기
Integer num = hashtable.get("이햄");
: 키값("이햄")으로 통번호를 계산하고 그 통 안에서 키값과 일치하는 데이터를 찾아서 리턴합니다.

＊데이터 삭제하기
hashtalbe.remove("해리");
: 키값으로 통번호를 계산하고 해당 통에서 키값과 일치하는 데이터를 찾아서 삭제합니다.

 

키값을 가지고 헤쉬 테이블의 통번호를 계산하는 공식은 프로그래머가 알 필요가 없음
하지만 해쉬 테이블 계산에는 hashCode 메소드가 사용된다는 것은 꼭 알아두어야 함
"이햄"이라는 문자열이 키로 사용되면 그 문자열에 대해 hashCode 메소드가 호출됨

내가 직접 작성한 클래스를 해쉬 테이블의 키로 사용하려면 hashCode 메소드를 오버라이드해야 함

 

 

 

2.

 

해쉬 테이블(Hash Table)은 배열처럼 여러 개의 데이타를 저장하는 자료구조이다. 배열과 가장 큰 차이점은 크기가 고정되어 있지 않고 가변적이라는 것과 인덱스를 통한 접근이 아니라 일종의 키값을 이용해 특정 위치에 접근한다는 점이다.

키값을 이용하면 자료의 수 즉, 테이블의 크기와는 상관없이 원하는 자료가 있는 위치로 한 번에 갈 수 있다는 장점이 있다. 해쉬 테이블의 용법을 한번 살펴보자.

 

Hashtable ht = new Hashtable() ;  // 해쉬테이블 객체를 만든다.

ht.put("A1", new Integer(94)) ;
ht.put("A2", new Integer(82)) ;
ht.put("A3", new Integer(87)) ;
.
.
.
System.out.println("A1 = " + (Integer)ht.get("A1")) ;

put()으로 값을 넣고 get()으로 값을 가져온다. 여기서, A1은 키값이고, 다른 하나는 실제 데이타가 된다. 즉 실제 데이타가 특정한 키값을 꼬리표로 가지고 저장되므로 키값을 사용하여 데이타를 다룰 수 있게 되는 것이다.

그런데, 주의할 점은 Hashtable에 저장되는 키값과 데이타는 반드시 '객체'라야 한다. 그래서, 직접 데이타 수치를 넣을 수가 없으므로 Integer(수치)의 형식으로 정수를 저장했고, 이를 자바에서는 'Wrapper 클래스를 사용한다'라고 한다. 출력문의 (Integer)는 '캐스팅'이다.

 

 

 

 

 

 

원문

http://blog.naver.com/es_sua?Redirect=Log&logNo=61308687

http://phoenix208.blog.me/40035732106