Ch.08-4 Hashing ( 해싱 ) [CPA340] Algorithms and Practice Youn-Hee Han

Page 2 해싱 (Hashing)  하나의 문자열을 더 짧은 길이의 값으로 변환하는 것  사전적 의미 : 잘게 썰다. 예제를 통한 해싱에 대한 이해 (1/2)  0 에서 99 사이의 정수로 된 키 (key) 가 있고, 100 개의 저장해야 할 정보 가 있다고 하자. 그러면 크기가 100 인 배열 S 를 만들어서 저장하면 빠른 시간 안에 검색할 수 있다.  i  s[i]  그런데 만약 키 (key) 가 13 자리 주민등록번호라면 키 값 저장을 위하 여 너무 많은 저장장소가 필요하게 된다. Hashing 기본 개념

Page 3 예제를 통한 해싱에 대한 이해 (2/2)  해법 : 0 ~ 99 의 인덱스를 가진 크기가 100 인 배열을 만든 후에, 주민등록번호 키 값을 0~99 사이의 값을 가지도록 해쉬 (hash) 한다.  여기서 해쉬함수는 13 자리 실제 키 값을 배열의 첨자 값 (0~99) 으로 변환하는 함수이다.  해쉬함수의 예 : h(key) = key % 자리 키 값이 2 자리 키 값으로 변환됨 주민증록번호 (13 자리 )  해시값 (2 자리 ) i  s[i] 해싱의 장점 ( 또는 의무적으로 가져야 할 특징 )  해시 연산은 매우 짧은 시간안에 이루어진다.  짧은 해시 키 ( 해싱된 결과 인덱스 ) 를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르며 메모리도 덜 차지한다. Hashing 기본 개념 읽을 거리 :

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")); }

Page 5 해싱의 문제점 : 충돌 (Collision)  2 개 이상의 키가 같은 해쉬값을 갖는 경우 충돌 (collision) 이 발생 이러한 해시 충돌 (Hash Collision) 을 어떻게 해결할 것인가 ? Hashing – 충돌 (Collision) [ 충돌이 일어나지 않을 확률 ] 100 개의 키가 있고, 각 키가 100 개의 인덱스로 해시될 것이다. 한편, 임의의 인덱스로 해쉬될 확률이 같다고 하자. 이 때 모든 키가 모두 다른 인덱스로 해쉬될 확률은 다음과 같다. [ 의미 ] 매우 작은 확률 ! 즉, 지속적인 해싱에 의해 최소한 2 개의 키가 하나의 인덱스로 해시, 즉 충돌이 일어날 가능성이 꽤 높다.

Page 6 충돌 해결법 : 오픈 해싱 (open hashing)  같은 해쉬값을 갖는 키들을 동일한 Bucket( 바구니 ) 에 모아 놓는다.  주로 Bucket 는 연결 리스트 (linked list) 로 구현 한다.  Bucket 내부를 검색할 때는 순차검색 ( 또는 효율 높은 다른 검색 ) 으로 한다.  구현 방법  각 Bucket 을 가리키는 포인터 배열 Bucket[] 을 만들고 각 배열의 포인터 값은 해당 Bucket 의 연결 리스트를 가리키도록 한다.  값 i 로 해시되는 키 값들은 모두 Bucket[i] 가 가리키는 연결 리스트에 순 차적으로 위치시킨다. Hashing – 충돌 (Collision) h(key) = key % 100

Page 7 충돌 해결법 : 오픈 해싱 (open hashing)  Bucket 의 수가 키의 개수와 같을 필요는 없다. 하지만 …  키의 수보다 Bucket 의 수가 적으면 충돌은 필연적이다.  만약 Bucket 의 수가 1 개라면 …  레코드의 검색은 단순한 키 값의 순차 검색으로 퇴보  일반적으로 레코드의 크기에 비해 포인터 변수는 상대적으로 작으므 로 최소한 레코드의 수만큼의 Bucket 을 사용하는 것이 합당하다.  만약 Bucket 의 수가 100 개일 때 100 개의 키가 같은 Bucket 으로 들어갈 확률은 ? Hashing – 충돌 (Collision) [ 의미 ] 매우 작은 확률이다.

Page 8 오픈 해싱 (open hashing) 방법의 분석  Assumption: 만약 n 개의 키와 m 개의 Bucket 이 있고 각 키 값들이 Bucket 마다 균일하게 분포 및 저장 되어있다.  [ 기본적 사실 ] 각 Bucket 마다 n/m 개의 키가 존재한다.  [ 정리 8.4] 실패하는 검색의 경우 총 비교횟수는 다음과 같다.   [ 정리 8.5] 각 키마다 검색되는 확률이 동일하다면 성공한 검색의 평균 비교횟수는 다음과 같다.  교재 P21 의 알고리즘 1.1 분석과 동일한 방법으로 분석 : 임의의 Bucket 에 서의 평균 검색시간은 개의 키를 순차검색하는 평균시간과 같다 Hashing – 충돌 (Collision)

Page 9 오픈 해싱 (open hashing) 방법의 분석  그렇다면, n 개의 키가 주어져 있을 때 검색을 빠르게 하기 위하여 이 분 검색을 사용해야 할까 ? 아니면 해시 방법을 통해 저장한 후 검색을 해야 할까 ?  Example] 개의 키  이분 검색  log = 8 번의 평균 비교검색  오픈 해싱  Bucket 이 16 개일 때 : 번의 평균 비교검색  Bucket 이 128 개일 때 : 번의 평균 비교검색  Bucket 이 256 개일 때 : 번의 평균 비교검색 Hashing – 충돌 (Collision)

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. Page 10