Binceline

더블해싱은 Open Address 방식이라고 하며, 체이닝과는 다르게 메모리 공간을 최대한 활용하려는 방향성을 가진다. Open Address 중 기본적인 방식이 그저 테이블 크기(Prime number)로 Mod 연산을 수행한 결과 + 충돌 시 1칸씩 이동한 결과라면 더블 해싱은 위에서 이 '1칸씩 이동하는' 부분을 1이 아닌 X만큼 이동하도록 변경한다. X라는 값은 어떻게 선정해야 할까? 저번 포스팅으로 Key값을 소수로 Mod하는 것에 대한 이점을 알아보았다. '어떤 수 A로 Mod 연산 시, A의 약수들의 배수로 이루어진 input에 대해 A보다 작은 해당 수들의 배수가 output이 된다.' 마찬가지로 이 X도 그런 이유로 결정하면 된다. 하지만 추가적으로, 이 이동량이 0이 나오는 경우를 배제..

테이블 크기를 소수로 하는 이유. 소수가 아닌 수 A라고 가정해 보자. 그렇다면 A의 모든 약수는 자신의 배수가 곧 키값이 된다. 예를 들면, 12로 Mod 연산을 한다고 했을 때, 12의 약수input : 3 6 9 12 15 18 21 24 ...output : 3 6 9 0 3 6 9 0... input : 4 8 12 16 20 24 ...output : 4 8 0 4 8 0 ... input : 6 12 18 24 30 36 ...output : 6 0 6 0 6 0 ... 이런 식이다. 하지만 소수는 약수가 1과 자신 뿐이므로 약수의 배수가 항상 약수로 나오는 문제가 제외된다.

원본 : http://javacan.tistory.com/entry/19 3-웨이 트리인 TST의 구현과 TST의 기본적인 성능향상방법에 대해서 알아본다.Ternary Search Tree 데이터를 저장할 때 많이 사용되는 것을 꼽으라면 java.util.Hashtable 이나 java.util.HashMap일 것이다. 이 둘은 해시테이블을 구현한 것으로서 키값을 사용하여 객체를 저장하고 읽을 수 있을 뿐만 아니라 알고리즘의 성능은 O(1)이다. 따라서 이 두 클래스를 사용하면 키값을 사용하여 매우 빠르게 해시테이블에 데이터를 저장하거나 해시테이블로부터 데이터를 읽어올 수 있다. 하지만, 해시테이블은 정렬 상태로 데이터를 유지하지 않기 때문에, 데이터의 집합을 정렬된 상태로 유지해야 하는 경우에는 사용할..

http://burtleburtle.net/bob/hash/doobs.htmlAbstractI offer you a new hash function for hash table lookup that is faster and more thorough than the one you are using now. I also give you a way to verify that it is more thorough.All the text in this color wasn't in the 1997 Dr Dobbs article. The code given here are all public domain.The HashOver the past two years I've built a general hash functio..