Download presentation
Presentation is loading. Please wait.
Published by소희 사공 Modified 8년 전
1
Ch.08-4 Hashing ( 해싱 ) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr
2
Page 2 해싱 (Hashing) 하나의 문자열을 더 짧은 길이의 값으로 변환하는 것 사전적 의미 : 잘게 썰다. 예제를 통한 해싱에 대한 이해 (1/2) 0 에서 99 사이의 정수로 된 키 (key) 가 있고, 100 개의 저장해야 할 정보 가 있다고 하자. 그러면 크기가 100 인 배열 S 를 만들어서 저장하면 빠른 시간 안에 검색할 수 있다. i s[i] 그런데 만약 키 (key) 가 13 자리 주민등록번호라면 키 값 저장을 위하 여 너무 많은 저장장소가 필요하게 된다. Hashing 기본 개념
3
Page 3 예제를 통한 해싱에 대한 이해 (2/2) 해법 : 0 ~ 99 의 인덱스를 가진 크기가 100 인 배열을 만든 후에, 주민등록번호 키 값을 0~99 사이의 값을 가지도록 해쉬 (hash) 한다. 여기서 해쉬함수는 13 자리 실제 키 값을 배열의 첨자 값 (0~99) 으로 변환하는 함수이다. 해쉬함수의 예 : h(key) = key % 100 13 자리 키 값이 2 자리 키 값으로 변환됨 주민증록번호 (13 자리 ) 해시값 (2 자리 ) i s[i] 해싱의 장점 ( 또는 의무적으로 가져야 할 특징 ) 해시 연산은 매우 짧은 시간안에 이루어진다. 짧은 해시 키 ( 해싱된 결과 인덱스 ) 를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르며 메모리도 덜 차지한다. Hashing 기본 개념 읽을 거리 : http://k.daum.net/qna/view.html?qid=00WN2
4
Web Programming4 Java HashMap 자료구조 import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set; public class Number { public static void main(String[] args) throws Exception { Map mMap = new HashMap(); mMap.put("PostgreSQL", "Free Open Source Enterprise Database"); mMap.put("DB2", "Enterprise Database, It's expensive"); mMap.put("Oracle", "Enterprise Database, It's expensive"); mMap.put("MySQL", "Free Open SourceDatabase"); mMap.put("Oracle", "Enterprise Database, It's free now ! (hope)"); System.out.println("One day Oracle.. : " + mMap.get("Oracle")); }
5
Page 5 해싱의 문제점 : 충돌 (Collision) 2 개 이상의 키가 같은 해쉬값을 갖는 경우 충돌 (collision) 이 발생 이러한 해시 충돌 (Hash Collision) 을 어떻게 해결할 것인가 ? Hashing – 충돌 (Collision) [ 충돌이 일어나지 않을 확률 ] 100 개의 키가 있고, 각 키가 100 개의 인덱스로 해시될 것이다. 한편, 임의의 인덱스로 해쉬될 확률이 같다고 하자. 이 때 모든 키가 모두 다른 인덱스로 해쉬될 확률은 다음과 같다. [ 의미 ] 매우 작은 확률 ! 즉, 지속적인 해싱에 의해 최소한 2 개의 키가 하나의 인덱스로 해시, 즉 충돌이 일어날 가능성이 꽤 높다.
6
Page 6 충돌 해결법 : 오픈 해싱 (open hashing) 같은 해쉬값을 갖는 키들을 동일한 Bucket( 바구니 ) 에 모아 놓는다. 주로 Bucket 는 연결 리스트 (linked list) 로 구현 한다. Bucket 내부를 검색할 때는 순차검색 ( 또는 효율 높은 다른 검색 ) 으로 한다. 구현 방법 각 Bucket 을 가리키는 포인터 배열 Bucket[] 을 만들고 각 배열의 포인터 값은 해당 Bucket 의 연결 리스트를 가리키도록 한다. 값 i 로 해시되는 키 값들은 모두 Bucket[i] 가 가리키는 연결 리스트에 순 차적으로 위치시킨다. Hashing – 충돌 (Collision) h(key) = key % 100
7
Page 7 충돌 해결법 : 오픈 해싱 (open hashing) Bucket 의 수가 키의 개수와 같을 필요는 없다. 하지만 … 키의 수보다 Bucket 의 수가 적으면 충돌은 필연적이다. 만약 Bucket 의 수가 1 개라면 … 레코드의 검색은 단순한 키 값의 순차 검색으로 퇴보 일반적으로 레코드의 크기에 비해 포인터 변수는 상대적으로 작으므 로 최소한 레코드의 수만큼의 Bucket 을 사용하는 것이 합당하다. 만약 Bucket 의 수가 100 개일 때 100 개의 키가 같은 Bucket 으로 들어갈 확률은 ? Hashing – 충돌 (Collision) [ 의미 ] 매우 작은 확률이다.
8
Page 8 오픈 해싱 (open hashing) 방법의 분석 Assumption: 만약 n 개의 키와 m 개의 Bucket 이 있고 각 키 값들이 Bucket 마다 균일하게 분포 및 저장 되어있다. [ 기본적 사실 ] 각 Bucket 마다 n/m 개의 키가 존재한다. [ 정리 8.4] 실패하는 검색의 경우 총 비교횟수는 다음과 같다. [ 정리 8.5] 각 키마다 검색되는 확률이 동일하다면 성공한 검색의 평균 비교횟수는 다음과 같다. 교재 P21 의 알고리즘 1.1 분석과 동일한 방법으로 분석 : 임의의 Bucket 에 서의 평균 검색시간은 개의 키를 순차검색하는 평균시간과 같다 Hashing – 충돌 (Collision)
9
Page 9 오픈 해싱 (open hashing) 방법의 분석 그렇다면, n 개의 키가 주어져 있을 때 검색을 빠르게 하기 위하여 이 분 검색을 사용해야 할까 ? 아니면 해시 방법을 통해 저장한 후 검색을 해야 할까 ? Example] - 256 개의 키 이분 검색 log 2 256 = 8 번의 평균 비교검색 오픈 해싱 Bucket 이 16 개일 때 : 번의 평균 비교검색 Bucket 이 128 개일 때 : 번의 평균 비교검색 Bucket 이 256 개일 때 : 번의 평균 비교검색 Hashing – 충돌 (Collision)
10
Java HashMap 자료구조 Capacity the number of buckets in the hash table Initial capacity the capacity at the time the hash table is created. Load factor a measure of how full the hash table is allowed to get before its capacity is increased. When “# entries in the hash table” > “load factor current capacity”, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets. Higher load factor values decrease the space overhead but increase the lookup cost 1) The expected number of entries in the map, 2) its load factor, 3) initial capacity should be considered so as to minimize the number of rehash operations. If the initial capacity > the maximum number of entries * 1 / load factor, no rehash operations will ever occur. http://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#HashMap(int) Page 10
Similar presentations