해시 테이블과 해시 함수 (Hash Table and Hash function)

# 해시 테이블과 해시 함수 (Hash Table and Hash function) 검색 최적화에 자주 쓰이는 해시란 것에 대해 알아봅시다. ## PH

• 2015-11-19 : Actual implementation of Hash 이랑 Listing up all datas in hash table 부분 추가. 뭐 대충만 궁금증 정리한거지만;;;
• 2015-05-11 : 이거 직접 활용해야 할 단계에 와서 정리를 더 하면서 공부해야 하는데;;;

## TOC ## 해시 테이블과 해시 함수 (Hash Table and Hash function) format 이 정형화되어 있는 자료를 저장할 때 보통 가장 많이 쓰이는게 array (배열) 구조이다. 빼곡히 data 들을 채워넣기 편하기도 하거니와 가장 직관적이고 쉬운 방법이기도 하다. 영어사전을 저장하는 경우를 생각해보면, 0번째 단어와 뜻을 dic[0][0]='단어', dic[0][1]='뜻' 이런식으로 저장하는 셈이다. 하지만 이런식으로 저장을 해 놓으면 내가 알고 싶은 단어의 뜻이 궁금해서 검색할 때, 어느 위치에 이 단어/뜻이 저장되었는지 찾으려면 하나하나 비교를 해서 찾아야한다. 정렬을 해서 저장을 해놨다고 하더라도 100만개 단어가 저장된 data 에서 특정 단어를 찾으려면 적어도 \log(N) 시간은 걸릴것이라 예상할 수 있다. 뭐 $\log(N)$ order 니까 별거 아닐거라 생각할수는 있지만, O(1) 시간안에 단어를 찾고 뜻을 찾아주는 자료구조가 있다면 이걸 쓰는게 이런경우는 더 좋지않을까? 임의로 저장된 data 에서 전체 자료 크기에 상관없이 O(1) 시간안에 검색을 해낸다는게 언뜻 불가능해 보이지만, 생각을 조금 고쳐먹어서 자료를 저장할때부터 잘 디자인하면 불가능하지도 않다. (아무렇게나 저장된 자료에서 O(1) 시간에 검색을 해내는건 불가능하다고 알고 있다. 이 경우는 어쩔수없이 하나하나 비교해야 하기때문에 O(N: 자료 크기) 가 걸릴듯? 뭐 정렬된 자료에서야 tree search (전체 1/2 위치에서의 값과 비교한뒤 다시 앞뒤로 1/2씩 (전체의 1/4 and so on) 슉슉 움직이면서 찾기) 를 통해 $\log(N)$ 에도 가능하겠지만 말이다.) 이해를 쉽게하기 위해 가장 극단적인 예를 들자면, 그냥 단어에 해당하는 위치에 각 단어/뜻을 저장해놓으면 된다. 'a'란 단어가 있으면 dic[1] 에 저장하고, 'b'란 단어는 dic[2] 위치에 'word' 란 단어가 있으면 dic[ toInt('w')*27^3 + toInt('o')*27^2 + toInt('r')*27^1 + toInt('d') ] 란 위치에 저장하자. (a=1, b=2, c=3, d=4, e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12, m=13, n=14, o=15, p=16, q=17, r=18, s=19, t=20, u=21, v=22, w=23, x=24, y=25, z=26) 로 처리하고 27진수로 단어를 처리한 것이다. 'beautiful' 같은 단어를 저장하려면 엄청난 크기의 array 를 필요로 할 것이고, 단어란게 'a' 부터 'zzzzzzzzzzzz' 까지 촘촘히 다 존재하지도 않기 때문에 저장공간을 엄청나게 낭비하는 방법이긴 하다. 어차피 hash table의 1차원적인 이해를 위해 어처구니 없는 방법을 쓴 것이니 이 문제는 나중에 해결하기로 하고, 이런 저장법이 검색에서 어떠한 힘을 발휘하는지를 우선 보자. 'mandatory' 란 단어의 뜻이 궁금하다면, dic[] array 에서 mandatory 가 저장된 위치 27진수 m(13)a(1)......r(18)y(25) 로 바로 찾아가면 된다. 이것이 바로 O(1) 검색이다. (뭐 비슷한 단어를 검색해준다거나 이런 기능을 넣고 싶으면 다른 방식을 알아보는게 좋긴 할듯? 그냥 tree 구조로 저장하는게 이 경우는 더 좋아보이기도.) 아무리 많은 단어가 저장되어 있더라도 이것들과의 비교를 통해 찾아내는 것이 아니라, 어디에 저장되어 있을거라는 것을 계산, 즉 function 을 통해 찾아가는 것이다. 여기서 사용되는 funcion 을 Hash function 이라고 부른다. 이제 너무 많은 저장공간을 차지했던것을 해결할 차례이다. 위에서 사용했던 무식한 Hash function 을 적절히 바꾼다면, 실제 데이터 (array 에 빼곡히 저장했을 때 차지하는) 용량보다 1.3배~2배의 공간정도만 사용해서도 Hash table 을 꾸밀 수 있게된다. 검색을 빠르게 하기위해 저장공간을 조금 더 차지한다고 보면된다. 이 정도는 뭐 봐줄만하다. 요새 하드디스크, usb flash disk 등의 용량도 넉넉해졌으니 말이다. 말로 장황하게 설명하기 보단 우선 Hash function 의 예 하나만 보자. ```[.linenums] unsigned oat_hash ( void *key, int len ) { unsigned char *p = key; unsigned h = 0; int i; for ( i=0; i<len; i++ ) { h += p[i]; h += ( h<<10 ); h ^= ( h>>6 ); } h += ( h<<3 ); h ^= ( h>>11 ); h += ( h<<15 ); return h%HashSize; } ```/ 무언가 자주쓰지 않는 <<, >>, ^ 연산들 (bit shift, XOR 등) 이 쓰인것을 볼 수 있는데, 실제 이 함수가 어떻게 mapping 되는지를 (어떤 key값을 입력했을때, 어떤 숫자를 뱉어내는지) 구체적으로 알 필요는 없다. 연산이 오래걸리는 곱셉, 나눕셈, log, exp 등의 함수를 쓴것이 아니라 bit 연산자를 써서 속도를 빠르게 한 것으로 이해된다. return 되는 값을 HashSize 로 나눠준 나머지를 써서 사용되는 Hash table size 바깥으로 값이 저장되는 것을 막았다. Hash function 이 가져야할 중요한 성질 중 하나는 우리가 저장하려는 data 들의 key 값들을 hash function mapping 하면 0 부터 (HashSize-1) 까지 적절히 고르게 분포시켜야 한다는거다. key 값이 다를때 주소값도 달라야 저장도 가능하고 O(1) 에 찾을 수 있기 때문이다. ### Resolving Collision Hash function이 완벽하지 않는한 (완전 무식하게 용량을 차지하게 하지 않는 한) 다른 key 값에 대해 같은 hash 값이 return 되는 것을 막는것은 거의 불가능하다. 가능하더라도 시간과 노력이 너무 많이들게 된다. 우선 최대한 값이 중복되어 나타나지 않도록 hash function 을 data에 맞게 design 하고 HashSize 를 적당히 키우거나 하는 방법을 써준다. 이런 경우에도 0.1%정도는 중복될 가능성이 있을 것이다. 이것을 충돌 (collision) 이라고 한다. 이런 충돌이 조금 일어날 때에도 우리가 원하는 기능들 (검색이 빠른 자료저장) 이 작동하게 하려면 어찌 해야할까? 이것을 해결하는 방법은 크게 두가지가 있다. Chaining 방식 (Linked list 형태로 값을 저장하거나 tree 구조 이용. 둘을 섞는경우도 있음.) 과 Open-addressing 방식 (중복되는 data 가 뜨면 그냥 다음칸에 저장하는 식) 이다. 찾을때 (검색할때) 에 저장방식에 따라 O(1) 에서 1~2 step 만 더 찾아보면 된다. 대충 이정도만 설명해도 Hash table의 기본적인 논리구조는 이해되셨을테니, 구체적인 설명은 아래 링크들을 참조해서... ### Scalability (확장성)

작성중. 정리하기 귀찮다;;;;;;

저장되는 데이터 숫자가 가변적일 경우, 성능을 위해 해시 테이블 사이즈를 늘리거나 줄여야 하는 경우가 빈번함. 10만개 정도 데이터가 저장될거라 생각하고 해시 테이블 사이즈를 넉넉하게 20만개 정도로 잡아놨다가, 저장되는 데이터가 30만개로 늘어나게되면 충돌이 일어나게 되고 충돌을 해결하는 구조가 있더라도 검색 성능에 저하가 일어나게 된다. 이 경우 그냥 해시 사이즈를 늘려서 테이블을 아예 옮겨버리는게 한가지 해결방법인데.. h%HashSize 로 hash 값을 return 하는거라 그냥 HashSize 만 늘려놓고 같은 테이블에서 뒷부분만 채우는 식이면 안되고 아예 hash 값을 다시 다 계산해서 다시 저장해야만 한다. 성능 향상을 위해 1번 해시 테이블에 있는걸 2번 테이블로 옮기면서 (데이터가 많을 경우 옮기는데에도 꽤나 시간이 걸릴테니), 데이터에 접근 할 경우 2번 검색 후 없으면 1번 검색. 중간에 1번에서 검색 결과를 뱉은것이 있다면 요놈 먼저 옮기는 큐에 올리는것도 생각해 볼만함. 데이터 다 옮기면 1번 테이블의 저장공간을 free. 2번만 검색. 이전엔 1번이 메인이었다면 다 옮긴 후에는 2번이 메인. 1번 저장소는 다른 데이터를 덮어써서 다른 데이터들을 저장하는데 다시 사용가능. 고차원 배열 형태랑 비슷하게 해시 테이블도 고차원으로 만드는것도 가능. 트리구조 비슷하게. 구글같은데에서 쓸거 같은데... 여러가지 속도가 빠른 해시 함수들을 조합해서 1차 해시 2차 해시로 구현 해 놓으면 초고용량 데이터를 다룰때 유용할듯. 아니면 트리랑 해시를 섞어서 쓸수도 있음. SQL 같은것들 구현에서 해시함수, 해시테이블 등이 쓰일듯. 검색 인덱스 설정하면 해시테이블이 만들어지면서 검색이 빠르게 되도록 도와주는듯. 인덱스 설정시 초기에 시간이 좀 걸리는 이유. 충돌 막는 법에 트리구조를 이용하기도 하는듯. 자바가 이런식으로 구현. 보조 해시함수도 있던데... 해시 테이블에 관한 간단한 설명 추가. 데이터 저장은 일렬로, 순서대로, 배열형태로, 혹은 적당히 다양한 방식으로 해놓고. 해시 테이블을 따로 구성. 인덱스 따라서 저장위치가 어디인지 해시 테이블을 따로 구성. 키값을 받으면 해시 함수 통과시켜서 해시 테이블 오더 1 검색. 여기서 나온 실제 데이터 저장위치 address 이용해서 바로 해당 데이터에 접근. 데이터 크기가 일정하지 않은 자료의 경우 유용. 사전 같은 것이 일예. ## Actual implementation of Hash 실제 여러 프로그래밍 언어들에서 hash table 을 어떻게 사용해 먹을 수 있을지 알아보자. 대부분 언어에서 HashMap 관련 class/library 등을 제공하니 그걸 잘 써먹으면 된다. 제공해주는 설명서, API-docu 들 참고해서. ### switch () case : ? 여러 언어에서 나오는 switch 문도 hash 이용하는 걸래나??? 그동안 if () else if () 랑 switch () case 랑 차이가 거의 없을거라고 생각해왔는데... Switch 에서는 내부적으로 hash 를 사용하는거라면 유의미한 차이가 있는거 같은데. 뭐 break 가 없을 경우 다음 case 까지 실행한다거나 그런 소소한 차이가 있긴 한데... if else 문처럼 처음 case 확인하고 아니면 다음 case 확인하는 식이 아니라 hash table 만들어놓고 key 값에 따라 해당 case 를 바로 찾아가는 식으로 내부적으로 구현해놨을수도 있을거 같은... break 같은걸 처리해야 하니 case 배치 순서도 어딘가 저장은 해놓고 처리해야겠네? 복잡시럽넹;;; Wiki 의 Switch statement - Advantages and disadvantages 부분을 보니 hash 형식의 branch table 을 내부적으로 쓰는게 맞는듯도? 프로그래밍 언어마다 내부적으로 구현해놓은게 다르긴 할테니 완전히 장담할수는 없는듯. 뭐 대부분의 언어에서는 switch 구현에 hash 방식을 쓰긴 하는듯. ### JAVA java.util.HashMap 을 import 해서 쓰면 된다. ```[.lang-java] import java.util.Map; import java.util.HashMap; imgMap=new HashMap<String, String>(); for (String imgName: imgNames) { imgMap.put(imgName, imgPath+imgName); } ```/ ### Javascript 여긴 따로 class 개념이 있는건 아니지만, JSON (JavaScript Object Notation) 자체가 아마도 hashmap 으로 이루어졌을 것으로 예상됨. (그냥 써먹기만 해서 내부적으로 어떻게 구현해놨는지 정확히는 모르겠음.) ``` data=[]; data.a="something"; data["$!@"]=53; ```/ ## Listing up all datas in hash table. Hash table 안의 내용물을 모두 list up 하고 싶을때도 있을텐데... 이 경우 어떤 방식으로 access 하는걸까나? Compact array 형태의 자료에서 list up 하는건 Order (N) 이면 충분할거 같은데, hash table 을 list up 하는건 hash size 에 비례할래나??? hash size 내를 순서대로 다 접근해보면서 empty 가 아니면 보여주는 식으로?? 뭐 언어들에서 제공하는 방법은 있긴한데... for in 같은 걸로... 여기서 data 접근이 어느 순서대로 이루어지는지를 잘 모르겠음. Hash table 에 data 를 put 한 순서도 따로 저장해놓고 그 순서대로 보여주는건가? ``` for (a in data) ```/ ## RRA

1. algoviz.org - OpenDSA - chapter 4. HASHING;
   // 책 형태임 (영어). 스마트폰에서 수식이 잘 안보이는건 아쉽.
2. Spark notes - What is Hash Tables?;
   // 가장 잘 설명해놓은 웹페이지 같음.
3. 수까락's blog - 해쉬 테이블;
   // 한글 설명. Hash table/function 을 처음 접하는 사람이 이해하기는 힘들게 구성된듯도.
4. helloworld.naver.com - Java HashMap은 어떻게 동작하는가?, 2014-07-04, by 송기선;
   // JAVA에서 구현해 놓은 HashMap에 관한 설명. 최적화가 잘 되어 있는듯.
5. MSDN(Microsoft Developer Network) - Library - Hashtable Class;
   // 많이 쓰이는 자료구조인만큼 여러 언어들로 library/class가 구성되어 있음. import해서 쓰면 되는듯.
6. partow.net - General Purpose Hash Function Algorithms;
   // 여러가지 hash function들도 설명해주고 꽤나 자세한듯함. 여러 hash function의 source code들도 다운되는듯.
7. azillion monkeys - Hash functions, by Paul Hsieh.;
   // code가 있음. 읽어봐야 파악이 될듯.
8. eternally confuzzled - The Art of Hashing;
   // 여러가지 hash function code 예제들 볼만함.