Data Structure 4

[자료구조] 더블해싱

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

Data Structure 2018.10.23

[자료구조] 해시테이블과 소수

테이블 크기를 소수로 하는 이유. 소수가 아닌 수 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과 자신 뿐이므로 약수의 배수가 항상 약수로 나오는 문제가 제외된다.

Data Structure 2018.10.23

[Data Structure][스크랩] Ternary Search Tree 1부, TST의 구현

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

Data Structure 2014.06.03
반응형