9. 해시테이블

9. 해시테이블

해시테이블 자료구조의두가지접근패턴 : 순차접근, 직접접근 순차접근 (sequential access) 연결리스트에의해서제공 구조의한쪽끝에서시작해각원소를하나씩살펴보면서목표에도달하거나다른끝에도달할때까지탐색을진행 탐색알고리즘은선형시간에실행 예, 오디오테이프나비디오테이프의자료구조 직접접근 (direct access), 임의접근 (random access) 배열에의해서제공 인덱스 i를이용해직접 a[i] 원소를찾음. i는 a[i] 의주소 순차접근보다훨씬더빠르고상수시간에실행 원소의인덱스에대한사전지식을필요 예, 오디오 CD 나비디오 DVD 의자료구조 2

해시테이블 (hash table) 원소의인덱스에대한사전지식없이직접접근을제공 원소의내용으로부터원소의인덱스를계산하는해시함수 (hash function) 를이용 해시 (hash) : 원소들이아무런순서없이마구뒤섞여있다는의미 이장에서는 java.util 패키지에구현되어있는해시테이블을포함한여러종류의해시테이블을기술 3

9.1 테이블과레코드 레코드 (record) 여러개의컴포넌트를가진복합적인자료구조 각컴포넌트는자신의이름과타입을가지고있음 일부프로그래밍언어에서는레코드가배열과같이표준타입으로사용 Java 에서는레코드가객체로서구현됨 테이블 (table) 동일타입의레코드의집합 예, 표 9.1 은 Country 타입을이용한테이블 (6 개의레코드 ) 테이블은순서가없는자료구조임 키테이블 (keyed table) -> 맵 (map) 또는사전 (dictionary) 테이블에저장된레코드전체에대해서값이유일한키필드 (key field) 라는특별한필드하나를레코드타입이포함하는테이블 각키는레코드식별에사용됨 4

5

9.2 맵 (Maps) 에대한 ADT 맵 (Map) : 키보유레코드의컬렉션임 ADT: Keyed Record 키보유레코드 (keyed record) : 키 (key) 와값 (value) 이라는이름을가진객체의순서쌍 연산 1. Initialize: 주어진키와주어진값을가지는키보유레코드를생성. 2. Key: 이레코드의키객체를리턴. 3. Value: 이레코드의값객체를리턴. 4. Update: 이레코드의값객체를주어진값객체로대체. setvalue 6

Entry 인터페이스 LISTING 9.2: An Entry Interface 1 public interface Entry { 2 public Object getkey(); 3 // RETURN: key; 4 // POST: key is the first object in this ordered pair; 5 6 public Object getvalue(); 7 // RETURN: value; 8 // POST: value is the second object in this ordered pair; 9 10 public void setvalue(object value); 11 // POST: value is the second object in this ordered pair; 12 } 7

ADT : Map 맵 (map) : 유일한키를갖는키보유레코드의컬렉션임 연산 1. Initialize: 공백맵을생성. 2. Search: 주어진키에대해테이블에서그키를가진레코드를탐색. 발견시그값을리턴. 그렇지않으면 null 을리턴. 3. Insert/Update: 주어진레코드에대해테이블에서그키를가진레코드를탐색. 발견시 : 그테이블레코드의값을주어진레코드의값으로대체하고대체된값을리턴. 그렇지않으면 : 주어진레코드를테이블에삽입. 4. Delete: 주어진키에대해테이블에서그키를가진레코드를탐색. 발견시해당레코드를테이블에서삭제하고그값을리턴. 그렇지않으면, null을리턴. 5. Count: 테이블의레코드수를리턴. 8

Map 인터페이스 (Object) 9

LISTING 9.3 Map 인터페이스 public interface Map { public Object get(object key); // RETURN: value; // POST: if value!=null, then (key,value) is in this map; // if value==null, then no record in this map has the given key; public Object put(object key, Object value); // RETURN: oldvalue; // POST: if oldvalue==null, then (key,value) is in this map; // if oldvalue!=null, then (key,oldvalue) was in this map; public Object remove(object key); // RETURN: oldvalue; // POST: if oldvalue==null, no record in this map has the given key; // if oldvalue!=null, then (key,oldvalue) was in this map; public int size(); // RETURN: n; // POST: this map contains n records; } 10

9.3 Hash Tables 자료구조에대한추가적인구성이없다면키테이블에대한접근은순차적임 테이블이키값에의해정렬되고배열에저장되었다면 이진탐색 : 접근시간을 Θ(n) 에서 Θ(lg n) 으로개선 해싱 (hashing) : 정렬하지않고도더좋은성능을낼수있음 키테이블에대한해시함수 테이블에서주어진키값을가지고있는레코드의위치 ( 배열인덱스 ) 를리턴하는함수 해시테이블 : 해시함수를가진키테이블임 11

초보적인해시테이블클래스 LISTING 9.4: A Naive Hash Table Class 1 public class HashTable implements Map { 2 private Entry[] entries = new Entry[11]; 3 private int size; 4 5 public Object get(object key) { 6 return entries[hash(key)].value; 7 } 8 9 public Object put(object key, Object value) { 10 entries[hash(key)] = new Entry(key,value); 11 ++size; 12 return null; 13 } 12

15 public Object remove(object key) { 16 int h = hash(key); 17 Object value = entries[h].value; 18 entries[h] = null; 19 --size; 20 return value; 21 } 23 public int size() { 24 return size; 25 } 27 private class Entry { 28 Object key, value; 29 Entry(Object k, Object v) { key = k; value = v; } 30 } 31 32 private int hash(object key) { 33 return (key.hashcode() & 0x7FFFFFFF) % entries.length; 34 } 35 } 13

hashcode( ) Object 클래스는임의의객체에대해 int 를리턴하는 hashcode( ) 메소드를정의하고있다. 2- 문자 String iso 에대해 hashcode() 는 31*iso.charAt(0) + iso.charat(1) 을리턴 (key.hashcode() & 0x7FFFFFFF) % entries.length key.hashcode() 의맨앞비트를 0 으로변경하여양수로만듬 나머지연산 14

크기 7 인해시테이블 15

9.4 선형조사 충돌 (collision) : 해당키의버킷이이미다른키에의하여점유되어있을때 해시테이블에서충돌을해결하는가장단순한방법 충돌된레코드를배열의가용한다음셀에저장하는것 이알고리즘은각 조사 에서배열의인덱스를 1 씩증가시므로선형조사 (linear probing) 라고함 이러한방법은해당원소가해시값에의해인덱스된슬롯에항상배치되지는않고테이블의임의에장소에서끝날수있기때문에개방주소법 (open addressing) 이라고도함 16

선형조사 17

맨뒤에서맨앞으로연결 18

put() 메소드에대한수정된코드는다음과같음 public Object put(object key, Object value) { int h = hash(key); for (int i = 0; i < entries.length; i++) { } } int j = (h+i)%entries.length; Entry entry=entries[ j]; if (entry == null) { entries[ j] = new Entry(key,value); ++size; ++used; return null; // insertion success } throw new IllegalStateException(); // failure: table overflow return null; 19

그결과수정된 remove() 메소드는다음과같은형태가됨 public Object remove(object key) { int h = hash(key); for (int i = 0; i < entries.length; i++) { int j = (h+i)%entries.length; if (entries[ j] == null) break; if (entries[ j].key.equals(key)) { Object value = entries[ j].value; entries[j] = NIL; --size; return value; } } return null; // failure: key not found } private final Entry NIL = new Entry(null, null); 20

put() 메소드에대한다시수정된코드는다음과같음 public Object put(object key, Object value) { int h = hash(key); for (int i = 0; i < entries.length; i++) { } } int j = (h+i)%entries.length; Entry entry=entries[ j]; if (entry == null entry == NIL) { entries[ j] = new Entry(key,value); ++size; return null; // insertion success } throw new IllegalStateException(); // failure: table overflow return null; 21

get(key) 메소드에대한수정된코드는? 22

9.5 재해싱 (rehashing) 테이블오버플로문제를해결하는방법 : 더큰배열을사용하여테이블을재구축함 경험에의하면테이블이포화상태에이르기전에 rehash() 를호출하는것이좋은전략이라고알려져있음 이는 rehash() 에대한호출을발생시키는임계크기를설정해수행할수있음 임계값을저장하는대신에최대비율 r = n/m 을명세한다. 여기서, n=size 이고 m=entries.length 임 이비율을적재율 (load factor) 이라고하며, 그상한값은대개 75% 나 80% 근처로설정함 예, 적재율이 75% 일때배열길이를 11 로하여시작하면 rehash() 는 size 가 8.25 를초과할때 ( 즉, 9 번째레코드가삽입된후에 ) 호출될것임 이호출은해시테이블을길이 23 으로재구축하게됨 23

기존배열보다크기가 2 배인배열로이동시키는 rehash() 메소드 private void rehash() { Entry[] oldentries = entries; Entries = new Entry[2*oldEntries.length+1]; for (int k = 0; k < oldentries.length; k++) { Entry entry = oldentries[k]; if (entry == null entry == NIL) continue; int h = hash(entry.key); for (int i = 0; i < entries.length; i++) { int j = nextprobe(h,i); //overflow 처리 if (entries[ j]==null) { entries[j] = entry; break; } hash 메소드를재정의함 NIL 참조는복사되지않음 } } used = size; } 24

LISTING 9.5 정확한해시테이블클래스 1 public class HashTable implements Map { 2 private Entry[] entries; 3 private int size, used; 4 private float loadfactor; 5 private final Entry NIL = new Entry(null, null); 6 7 public HashTable(int capacity, float loadfactor) { 8 entries = new Entry[capacity]; 9 this.loadfactor = loadfactor; 10 } 12 public HashTable(int capacity) { 13 this(capacity, 0.75F); 14 } 16 public HashTable() { 17 this(101); 18 } 25

20 public Object get(object key) { 21 int h = hash(key); 22 for (int i = 0; i < entries.length; i++) { 23 int j = nextprobe(h,i); 24 Entry entry=entries[ j]; 25 if (entry == null) break; 26 if (entry == NIL) continue; 27 if (entry.key.equals(key)) return entry.value; 28 } 29 return null; // failure: key not found 30 } 32 public Object put(object key, Object value) { 33 if (used > loadfactor*entries.length) rehash(); 34 int h = hash(key); 35 for (int i = 0; i < entries.length; i++) { 36 int j = nextprobe(h,i); 37 Entry entry = entries[ j]; 38 if (entry == null) { 39 entries[ j] = new Entry(key, value); 40 ++size; 41 ++used; 42 return null; // insertion success 43 } 26

44 if (entry == NIL) continue; 45 if (entry.key.equals(key)) { 46 Object oldvalue = entry.value; 47 entries[ j].value = value; 48 return oldvalue; // update success 49 } 50 } 51 return null; // failure: table overflow 52 } 54 public Object remove(object key) { 55 int h = hash(key); 56 for (int i = 0; i < entries.length; i++) { 57 int j = nextprobe(h,i); 58 Entry entry = entries[ j]; 59 if (entry == null) break; 60 if (entry == NIL) continue; 61 if (entry.key.equals(key)) { 62 Object oldvalue = entry.value; 63 entries[ j] = NIL; 64 --size; 65 return oldvalue; // success 66 } 67 } 27

68 return null; // failure: key not found 69 } 71 public int size() { 72 return size; 73 } 74 75 private class Entry { 76 Object key, value; 77 Entry(Object k, Object v) { key = k; value = v; } 78 } 79 80 private int hash(object key) { 81 if (key == null) throw new IllegalArgumentException(); 82 return (key.hashcode() & 0x7FFFFFFF) % entries.length; 83 } 84 85 private int nextprobe(int h, int i) { 86 return (h + i)%entries.length; // Linear Probing 87 } 28

89 private void rehash() { 90 Entry[] oldentries = entries; 91 entries = new Entry[2*oldEntries.length+1]; 92 for (int k = 0; k < oldentries.length; k++) { 93 Entry entry = oldentries[k]; 94 if (entry == null entry == NIL) continue; 95 int h = hash(entry.key); 96 for (int i = 0; i < entries.length; i++) { 97 int j = nextprobe(h,i); 98 if (entries[j] == null) { 99 entries[ j] = entry; 100 break; 101 } 102 } 103 } 104 used = size; 105 } 106 } 29

9.6 기타충돌해결알고리즘 선형조사 (linear probing) 는충돌의해결에있어서단순하고어느정도효율적인방법임 선형조사의문제점 기본집중 (primary clustering) 이발생 : 해시함수가테이블전체에대해레코드를균일하게분배하는데실패하면선형조사는함께묶인레코드의긴체인을만드는경우 예, 다음의 9 개국가에대한레코드를길이 m=101 인빈테이블에삽입한다고가정해보자. 30

선형조사의삽입예 길이 m=101 인빈테이블에삽입한다고가정해보자. put("fi", new Country("Finland", "Finnish", 130100, 5158372)); put("iq", new Country("Iraq", "Arabic", 168754, 22427150)); put("ir", new Country("Iran", "Farsi", 636000, 65179752)); put("sk", new Country("Slovakia", "Slovak", 18859, 5396193)); put("ca", new Country("Canada", "English", 3851800, 31006347)); put("ly", new Country("Libya", "Arabic", 679400, 4992838)); put("it", new Country("Italy", "Italian", 116300, 56735130)); put("pe", new Country("Peru", "Spanish", 496200, 26624582)); put("is", new Country("Iceland", "Islenska", 40000, 272512)); 31

선형조사에서삽입후의충돌예 선형조사의경우, 아래와같은순서로 9 개의레코드를삽입하면 26 번의충돌이발생 : 해결방법은제곱조사 "FI" 21 "IQ" 21 22 "IR" 22 23 "SK" 22 23 24 "CA" 21 22 23 24 25 "LY" 21 22 23 24 25 26 "IT" 24 25 26 27 "PE" 24 25 26 27 28 "IS" 23 24 25 26 27 28 29 32

제곱조사 선형조사의문제점 : 집중에의해성능이손상됨 하나의클러스터는그안에갭이없다. 그러므로 PE 와 IS 처럼클러스터의시작부근에해시되는새레코드들은한번에한단계씩여러레코드를거쳐야하므로충돌이늘어나고시간도낭비됨 제곱조사 (quadratic probing) : 이알고리즘은매번 1 씩증가하는대신에점진적으로더큰폭으로증가시켜충돌을해결함 이를구현하기위해서는 int j = (h + i)%entries.length 를 int j = (h + i*i)%entries.length; 로대체함 33

제곱조사 (2) int j = (h + i*i)%entries.length; 즉, 각충돌후에 h 에 i 를더하는대신에 i*i 를더한다. (quadratic 은변수의제곱을의미한다.) 따라서증분의순서는 1, 4, 9, 16, 25,... 가된다. 제곱조사는선형조사의충돌횟수를반으로줄임 결과가개선되는이유는제곱조사가사용이안된갭을중간에남겨두어선형조사보다적은집중을가져오기때문이다. 34

제곱조사에서삽입후의충돌예 제곱조사를이용하면동일한 9 개레코드의순서적인입력 에대해 13 번의충돌만이발생한다. "FI" 21 "IQ" 21 22 "IR" 22 23 "SK" 22 23 26 "CA" 21 22 25 "LY" 21 22 25 30 "IT" 24 "PE" 24 25 28 "IS" 23 24 27 35

LY 에대한제곱조사순서 36

제곱조사의문제점 이중해싱 길이가 m=11 인테이블에어떤키가인덱스 j=3 으로해시될때, 순서는 3, 4, 7, 1, 8, 6, 6, 8, 1, 7, 4, 3, 4, 7, 1, 8, 6, 6, 8, 1, 7, 4, 3 됨 이는희소주기순서이다. 이는 11 개셀중 6 개셀이모두점유되고나면다른 5 개의셀이비어있더라도 put() 은실패하게된다. 해결책 : 임계적재율을 50% 로설정함. 즉, 6 > 11/2 가됨 만약, 적재율을 50% 로제한한다해도, 2 차집중문제가발생함 37

이중해싱 (2) 2 차집중 (secondary clustering) : 동일한값으로해시되는 2 개의상이한키가동일한조사순서를가지게되는것이다. 해결책 : 이중해싱 (double hashing) 이중해싱 (double hashing) 조사순서를결정해주는제 2 의독립적인해시함수를사용 2 번째해시함수에의한상수증분은대개 1 보다큼 제곱조사처럼이중해싱도조사순서를넓게확대해서기본집중을피함 38

이중해싱을위한리스팅 9.5 의조정 20 public Object get(object key) { 21 int h = hash(key); int h = hash(key); int d = hash2(key); 22 for (int i = 0; i < entries.length; i++) { 23 int j = nextprobe(h,i); int j = nextprobe(h,d,i) : } 80 private int hash(object key) { 81 if (key == null) throw new IllegalArgumentException(); 82 return (key.hashcode() & 0x7FFFFFFF) % entries.length; 83 } 84 85 private int nextprobe(int h, int i) { 86 return (h + i)%entries.length; // Linear Probing 87 } hash2( ) 는??? nextprobe(h,d,i) 는???

이중해싱에서삽입후의충돌예 동일한순서의 9 개레코드의입력에대해 5 번의충돌만발생 "FI" 21 "IQ" 21 89 "IR" 22 "SK" 22 97 "CA" 21 85 "LY" 21 91 "IT" 24 "PE" 24 99 "IS" 23 40

9.7 별도체인 개방주소법 : 이제까지기술된해시알고리즘 개방주소법은충돌해결을위해배열내부에서개방된위치를탐색하기때문이다. 폐쇄주소법 (closed addressing) 폐쇄주소법은하나의해시위치에 1 개보다많은레코드를허용함으로써충돌을피한다. 따라서복잡한자료구조가필요. 별도체인 (separate chaining) 레코드의배열대신에버켓의배열을사용 버켓 (bucket) 이란일종의레코드의컬렉션임 가장단순한자료구조는하나의버켓에대해하나의연결리스트를사용하는것 41

체인을이용한폐쇄주소법 그림 9.7 은용량을 11 로, 적재율을 2.0 으로하고 15 개의유럽국가를적재한후의해시테이블을보이고있다. 키만을보이고있고전체레코드는보이지않고있다. 그림 9.7 42

폐쇄주소법 폐쇄주소법을사용하는해시테이블에대한자료구조가더복잡하기는하지만코드는약간더짧다. 빈 NIL 항목도필요하지않고충돌해결알고리즘도필요하지않다. 폐쇄주소법의경우체인의길이에제한이없으므로적재율이지원배열의길이를초과할수있다. 그렇지만, 긴체인을허용하게되면해시테이블의성능이저하된다. 그러므로테이블 size 가주어진임계값을넘어가면재해싱을수행함. 폐쇄주소법은충돌을방지하는명확한장점을가지고있다. 각버켓이임의개수의다수의키를저장할수있다면오버플로는일어나지않게될것이다. 단점은일부체인이매우길어질수있다는것이다. 매우불균형한버켓체인의배열은해싱이제공해야할상수시간접근의장점을파괴할수도있다. 43

별도체인에의한폐쇄주소법 LISTING 9.6: Closed Addressing by Separate Chaining 1 public class HashTable { 2 private Entry[] entries; 3 private int size; 4 private float loadfactor; 5 6 public HashTable(int capacity, float loadfactor) { 7 entries = new Entry[capacity]; 8 this.loadfactor = loadfactor; 9 } 10 11 public HashTable(int capacity) { 12 this(capacity, 0.75F); 13 } 14 15 public HashTable() { 16 this(101); 17 } 44

19 public Object get(object key) { 20 int h = hash(key); 21 for (Entry e = entries[h]; e!= null; e = e.next) { 22 if (e.key.equals(key)) return e.value; // success 23 } 24 return null; // failure: key not found 25 } 27 public Object put(object key, Object value) { 28 int h = hash(key); 29 for (Entry e = entries[h]; e!= null; e = e.next) { 30 if (e.key.equals(key)) { 31 Object oldvalue = e.value; 32 e.value = value; 33 return oldvalue; // successful update 34 } 35 } 36 entries[h] = new Entry(key,value,entries[h]); 37 ++size; 38 if (size > loadfactor*entries.length) rehash(); 39 return null; // successful insertion 40 } 45

42 public Object remove(object key) { 43 int h = hash(key); 44 for (Entry e = entries[h], prev=null; e!=null; prev=e, e=e.next) { 45 if (e.key.equals(key)) { 46 Object oldvalue = e.value; 47 if (prev == null) entries[h] = e.next; 48 else prev.next = e.next; 49 --size; 50 return oldvalue; // success 51 } 52 } 53 return null; // failure: key not found 54 } 56 public int size() { 57 return size; 58 } 46

60 private class Entry { 61 Object key, value; 62 Entry next; 63 Entry(Object k, Object v, Entry n) { key=k; value=v; next=n; } 64 public String tostring() { 65 return key + "=" + (Country)value; 66 } 67 } 69 private int hash(object key) { 70 if (key == null) throw new IllegalArgumentException(); 71 return (key.hashcode() & 0x7FFFFFFF) % entries.length; 72 } 47

74 private void rehash() { 75 Entry[] oldentries = entries; 76 entries = new Entry[2*oldEntries.length+1]; 77 for (int k = 0; k < oldentries.length; k++) { 78 for (Entry old = oldentries[k]; old!= null; ) { 79 Entry e = old; 80 old = old.next; 81 int h = hash(e.key); 82 e.next = entries[h]; 83 entries[h] = e; 84 } 85 } 86 } 87 } 48

9.8 java.util.map 인터페이스 LISTING 9.7: The java.util.map Interface 1 public interface Map { 2 public void clear(); 3 public boolean containskey(object key); 4 public boolean containsvalue(object value); 5 public Set entryset(); 6 public boolean equals(object object); 7 public Object get(object key); 8 public int hashcode(); 9 public boolean isempty(); 10 public Set keyset(); 11 public Object put(object key, Object value); : 23 } java.util.hashmap 이 java.util.map 인터페이스를구현 - 디폴트초기용량 101 - 디폴트최대적재율이 0.75 인폐쇄주소법사용 49

1 public class TestMap { 2 public static void main(string[] args) { 3 java.util.map map = new java.util.hashmap(); 4 map.put("at", new Country("Austria", "German", 32378, 8139299)); 5 map.put("be", new Country("Belgium", "Dutch", 11800, 10182034)); 6 map.put("dk", new Country("Denmark", "Danish", 16639, 5356845)); 7 map.put("fr", new Country("France", "French", 211200, 58978172)); 8 map.put("gr", new Country("Greece", "Greek", 50900, 10707135)); 9 map.put("ie", new Country("Ireland", "English", 27100, 3632944)); 10 map.put("it", new Country("Italy", "Italian", 116300, 56735130)); 11 map.put("es", new Country("Spain", "Spanish", 194880, 39167744)); 12 System.out.println("map.keySet(): " + map.keyset()); 13 System.out.println("map.size(): " + map.size()); 14 System.out.println("map.get(\"ES\"): " + map.get("es")); 15 Country es = (Country)map.get("ES"); 16 es.population = 40000000; 17 System.out.println("map.get(\"ES\"): " + map.get("es")); 18 System.out.println("map.remove(\"ES\"): " + map.remove("es")); 19 System.out.println("map.get(\"ES\"): " + map.get("es")); 20 System.out.println("map.keySet(): " + map.keyset()); 21 System.out.println("map.size(): " + map.size()); } } 50

출력결과 map.keyset(): [AT, FR, GR, DK, IT, BE, ES, IE] map.size(): 8 map.get("es"): (Spain,Spanish,194880,39167744) map.get("es"): (Spain,Spanish,194880,40000000) map.remove("es"): (Spain,Spanish,194880,40000000) map.get("es"): null map.keyset(): [AT, FR, GR, DK, IT, BE, IE] map.size(): 7 51

9.9 해싱알고리즘의분석 4 개해싱알고리즘의평균실행 - 시간복잡도 이공식들은지원배열의길이 m 이크고 hash() 메소드가주어진모든키값의집합에대해범위 0 h<m 사이에균일하게분포된인덱스번호 h 를리턴하는것으로가정한다. 해시테이블에대한적재율이비율 r=n/m 이고, 이때 n 은테이블의레코드수, m 은지원배열의길이 (entries.length), q = 1/(1-r) = m/(m-n) 으로정의된다 키를찾음 키를찾지못함 개방주소법 (r<1) 선형조사제곱조사이중해싱 (1+q)/2 1+ln q-r/2 (ln q)/r (1+q 2 )/2 q+ln q-r q 폐쇄주소법별도체인 1+r/2 r 52

예, r=75% ( 따라서 q = 4.0 이고 ln q = 1.386) 라면, 이공식들은다음의표와같은값들을갖게된다. 주어진적재율에대한평균실행시간은테이블에서아래로갈수록좋아지는것을알수있음. 일반적으로별도체인을이용한폐쇄주소법이개방주소법알고리즘보다성능이우수하다. java.util.hashmap 클래스가이알고리즘을사용하는이유는이때문이다. 키를찾음 키를찾지못함 개방주소법 (r<1) 선형조사제곱조사이중해싱 2.5 2.0 1.8 8.5 4.6 4.0 폐쇄주소법별도체인 1.375 0.75 53

9.10 완전해시함수 개방주소법이폐쇄주소법보다잘작동하는경우 완전해시함수 (perfect hash function) 일때 해시함수가모든가능한키의집합에대해일대일이될때 보통이런특별한상황은매우드물지만, 전체키집합을미리알수있다면, 해시테이블과해시함수고안이가능 완전해시함수가발견되면개방주소법 ( 조사과정이필요없는 ) 이가장좋다. 이러한자료구조를종종조사표 (lookup table) 라고한다. 이방법은공간을낭비한다. 한예에서는길이 77 인배열이 15 레코드저장에사용되어적재율이 20% 보다낮아진다. 54

최소완전해시함수 최소완전해시함수 (minimal perfect hash function) 일대일이면서 100% 적재율을가진완전해시함수 이함수의발견은매우어렵지만, 함수의탐색과정을도와주는알고리즘중하나가 1980 년에 R. J. Cichelli 에의해서제안되었음. 문자열에대한완전해시함수발견함 최소완전해시함수는전체키집합이미리알려져있고변하지않을때유용하다. 컴파일러에서사용되는프로그래밍언어의예약어에대한테이블이이러한형태이다. 55

9.11 기타해시함수 완전해시함수가불가능하다면, 최선의해시함수는레코드를해시테이블전체에고르게분배하는것임. 제산 (division) 해시함수 이함수는큰정수를테이블의길이로나눈나머지를사용 예를들어, num(key) % entries.length (key.hashcode() & 0x7FFFFFFF) % entries.length 또다른해싱방법은추출 (extraction) 이는키의일부분에적용된제산방법으로볼수있다. 예, 일주일의 7 개요일의이름에대한해싱은모두동일한접미어 day 를가지기때문에각키워드의마지막 3 개문자를생략함 56

중첩해시함수 (folding hash function) 키가단순한정수일경우간단한솔루션을제공한다. 이방법은숫자문자열을여러부분으로분리하고나서이들을함께 중첩 시킨다. 예, 9- 자리코드로구성된미국의사회보장번호 054-36-1729 를해싱하는경우, 해시값 37 의계산방법 1. 해당하는긴정수를구성 : 054361729 2. 이를 3개부분으로분리 : 054, 361, 729 3. 중간부분을역순으로배열 : 054, 163, 729 4. 각부분들을더함 : 054+163+729 = 946 5. 테이블길이로나눈나머지를구함 : 946%101 = 37 개인레코드에대한용량이 101 인해시테이블에서사회보장번호 054-36-1729 를갖는레코드는 table[37] 에저장 57

중첩 58