블로그 이미지
평범하게 살고 싶은 월급쟁이 기술적인 토론 환영합니다.같이 이야기 하고 싶으시면 부담 말고 연락주세요:이메일-bwcho75골뱅이지메일 닷컴. 조대협


Archive»


 
 

Hashtable의 이해와 구현 #1

프로그래밍/알고리즘 | 2016.02.06 02:40 | Posted by 조대협

해쉬 테이블의 이해와 구현 (Hashtable)


조대협 (http://bcho.tistory.com)


기본적인 해쉬 테이블에 대한 이해


해쉬 테이블은 Key Value를 저장하는 데이타 구조로, value := get(key)에 대한 기능이 매우매우 빠르게 작동한다. 개발자라면 자주 쓰는 데이타 구조지만, 실제로 어떻게 작동하는지에 대해서 정확하게 알고 있지는 모르는 경우가 많다. 이 글에서는 해쉬 테이블에 대한 기본적인 구조와, 구현 방식에 대해서 설명 하도록 한다.

 

해쉬 테이블의 기본적인 개념은 다음과 같다.

이름을 키로, 전화 번호를 저장하는 해쉬 테이블 구조를 만든다고 하자.  전체 데이타 양을 16명이라고 가정하면

 

John Smith의 데이타를 저장할때, index = hash_function(John Smith) % 16  를 통해서 index 값을 구해내고, array[16] = John Smith의 전화 번호 521-8976”을 저장한다.



(출처 :https://en.wikipedia.org/wiki/Hash_table )

 

이런 형식으로 데이타를 저장하면, key에 대한 데이타를 찾을때, hash_function을 한번만 수행하면 array내에 저장된 index 위치를 찾아낼 수 있기 때문에, 데이타의 저장과 삭제가 매우매우 빠르다.

 

충돌 처리 방식에 따른 알고리즘 분류

 

그런데, 이 해쉬 테이블 문제는 근본적인 문제가 따르는데, hash_function(key) / size_of_array의 값이 중복이 될 수 가 있다.

 

예를 들어 저장하고자 하는 key가 정수라고 하고, hash_function key%10 이라고 하자. 그리고 size_of_array 10일때, key 1,11,21,31은 같은 index 값을 가지게 된다. 이를 collision (충돌)이라고 하는데, 이 충돌을 해결하는 방법에 따라서 여러가지 구현 방식이 존재한다.

 

1. Separate chaining 방식

 

JDK내부에서도 사용하고 있는 충돌 처리 방식인데, Linked List를 이용하는 방식이다.

index에 데이타를 저장하는 Linked list 에 대한 포인터를 가지는 방식이다.



(출처 :https://en.wikipedia.org/wiki/Hash_table )

 

만약에 동일  index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다.  이렇게 함으로써 충돌이 발생하더라도 데이타를 삽입하는 데 문제가 없다.

 

데이타를 추출을 하고자할때는 key에 대한 index를 구한후, index가 가리키고 있는 Linked list를 선형 검색하여, 해당 key에 대한 데이타가 있는지를 검색하여 리턴하면 된다. 

삭제 처리


key를 삭제하는 것 역시 간단한데, key에 대한 index가 가리키고 있는 linked list에서, 그 노드를 삭제하면 된다.

Separate changing  방식은 Linked List 구조를 사용하고 있기 때문에, 추가할 수 있는 데이타 수의 제약이 작다.

 

참고 : 동일 index에 대해서 데이타를 저장하는 자료 구조는 Linked List 뿐 아니라, Tree를 이용하여 저장함으로써, select의 성능을 높일 수 있다. 실제로, JDK 1.8의 경우에는 index에 노드가 8개 이하일 경우에는 Linked List를 사용하며, 8개 이상으로 늘어날때는 Tree 구조로 데이타 저장 구조를 바꾸도록 되어 있다.

 

2. Open addressing 방식

 

Open addressing  방식은 index에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용하는 방법으로, Separate chaining 방식에 비해서 메모리를 덜 사용한다. Open addressing  방식도 여러가지 구현 방식이 있는데, 가장 간단한 Linear probing 방식을 살펴보자

 

Linear Probing

 

Linear Probing 방식은 index에 대해서 충돌이 발생했을 때, index 뒤에 있는 버킷중에 빈 버킷을 찾아서 데이타를 넣는 방식이다. 그림에서 key % 10 해쉬 함수를 사용하는  Hashtable이 있을때, 그림에서는 충돌이 발생하지 않았다.

 

 


아래 그림을 보자, 그런데, 여기에 11을 키로 하는 데이타를 그림과 같이 넣으면 1이 키인 데이타와 충돌이 발생한다. (이미 index1인 버킷에는 데이타가 들어가 있다.) Linear Probing에서는 아래 그림과 같이 충돌이 발생한 index (1) 뒤의 버킷에 빈 버킷이 있는지를 검색한다. 2번 버킷은 이미 index2인 값이 들어가 있고, 3번 버킷이 비어있기 3번에 값을 넣으면 된다.


검색을 할때, key 11에 대해서 검색을 하면, index1이기 때문에, array[1]에서 검색을 하는데, key가 일치하지 않기 때문에 뒤의 index를 검색해서 같은 키가 나오거나 또는 Key가 없을때 까지 검색을 진행한다. 


삭제  처리


이러한 Open Addressing의 단점은 삭제가 어렵다는 것인데, 삭제를 했을 경우 충돌에 의해서 뒤로 저장된 데이타는 검색이 안될 수 있다. 아래에서 좌측 그림을 보자,  2index를 삭제했을때, key 11에 대해서 검색하면, index1이기 때문에 1부터 검색을 시작하지만 앞에서 2index가 삭제되었기 때문에, 2 index까지만 검색이 진행되고 정작 데이타가 들어 있는 3index까지 검색이 진행되지 않는다.

그래서 이런 문제를 방지하기 위해서 우측과 같이 데이타를 삭제한 후에, Dummy node를 삽입한다. Dummy node는 실제 값을 가지지 않지만, 검색할때 다음 Index까지 검색을 연결해주는 역할을 한다.


Linear probing에 대한 샘플 코드는

http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html

http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

를 참고하기 바란다.

Dummy Node를 이용해서 삭제를 할때, 삭제가 빈번하게 발생을 하면, 실제 데이타가 없더라도 검색을 할때, Dummy Node에 의해서, 많은 Bucket을 연속적으로 검색을 해야 하기 때문에, Dummy Node의 개수가 일정 수를 넘었을때는 새로운 array를 만들어서, 다시 hash를 리빌딩 함으로써, Dummy Node를 주기적으로 없애 줘야 성능을 유지할 수 있다.


Resizing

Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이타를 더 넣기 위해서는 배열을 확장해야 한다. 또한 Separate changing에 경우에도 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에, 검색 성능이 떨어지기 때문에 버킷의 개수를 늘려줘야 한다. 이를 Resizing이라고 하는데, Resizing은 별다른 기법이 없다. 더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 arrayhash를 다시 계산해서 복사해줘야 한다.


해쉬 함수


해쉬 테이블 데이타 구조에서 중요한 것중 하나가 해쉬 함수(hash function)인데, 좋은 해쉬 함수란, 데이타를 되도록이면 고르게 분포하여, 충돌을 최소화할 수 있는 함수이다. 수학적으로 증명된 여러가지 함수가 있겠지만, 간단하게 사용할 수 있는 함수를 하나 소개하고자 한다. 배경에 대해서는 http://d2.naver.com/helloworld/831311 에 잘 설명되어 있으니 참고하기 바란다. (필요하면 그냥 외워서 쓰자)

String key

char[] ch = key.toChar();

int hash = 0;

for(int i=0;i<key.length;i++)

 hash = hash*31 + char[i]

 

Cache를 이용한 성능 향상


해쉬테이블에 대한 성능 향상 방법은 여러가지가 있지만, 눈에 띄는 쉬운 방식이 하나 있어서 마지막으로 간략하게 짚고 넘어가자. 해쉬테이블의 get(key)put(key)에 간단하게, 캐쉬 로직을 추가하게 되면, 자주 hit 하는 데이타에 대해서 바로 데이타를 찾게 함으로써, 성능을 간단하게 향상 시킬 수 있다.  

다음은 실제로 간단한 HashTable 클래스를 구현하는 방법에 대해서 알아보도록 하겠다. 

저작자 표시 비영리
신고

dynamic array resizing에 대해서.

프로그래밍/알고리즘 | 2016.02.05 02:52 | Posted by 조대협

알고리즘쪽을 파다보니 재미있는게, 예전에 알았던 자료 구조도 구현 방식등에 대해서 다시 되짚어 볼 수 있는게 좋은데. (그간 생각하던 구현 방식과 다른 방식도 종종 나와서.)


보통 메모리 문제 때문에 불확실한 데이타 크기를 가지는 데이타 구조는 LinkedList를 사용하는게 유리하다고 생각했는데, 내용중에, 배열을 사용하고, 배열이 다 차면 그크기를 늘리는 (새롭게 더 큰 배열을 만들어서 기존 배열 내용을 복사해서 대처 하는것) 방식 (Array Resize)를 봤다.  일반적인 방식이기는 하지만 메모리 소모량이나 배열 복사 속도 때문에 그다지 바람직하다고 생각 안하고 있었는데, JDK내의 Map 클래스의 구현 부분을 보니, 실제로 Map 클래스에서도  array resize를 사용하고 있다.


(출처 : http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.addEntry%28int%2Cjava.lang.Object%2Cjava.lang.Object%2Cint%29 )

꽉 막혀서 생각할 것이 아니라, 이런 방식도 융통성 있게 고려를 해봐야겠다.


저작자 표시 비영리
신고


튜토리얼 포인트

자료 구조에 대한 설명과 코드들을 간략하게 잘 정리해 놓음

http://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm 


코세라 프린스턴 알고리즘 강의

https://class.coursera.org/algs4partI-010


코세라 데이타 구조에 대한 강의 (그래프 구조에 대한 문제가 잘 정리되어 있음)

https://class.coursera.org/algs4partI-010


알고리즘에 대한 일반적인 설명 (Algorithm 4th edition)

http://algs4.cs.princeton.edu/


Octree와 QuadTree에 대한 설명 (게임에서의 응용)

http://www.gamedev.net/page/resources/_/technical/game-programming/introduction-to-octrees-r3529


저작자 표시 비영리
신고

동적 연결 알고리즘 (Dynamic Connectivity)


조대협 (http://bcho.tistory.com)


요즘 알고리즘이 대세라 기초를 다지는 차원에서 다시 알고리즘을 보고 있는데, 오늘은 동적 연결 알고리즘에 대해서 공부한 내용을 간략하게 정리해본다.


동적 연결 알고리즘은 노드끼리 연결이 되어 있는지를 찾는 알고리즘이다.

각 도시간에 연결이 되어 있는지, SNS에서 친구끼리 서로 연결이 되어 있는지와 같은 연결성만을 판단한다.


예전에 이러한 문제를 그래프 형태의 자료구조를 이용해서 풀려고 했는데, 여기서 문제의 핵심은 노드 A와 B가 연결되었는지만 판단하면 된다. 즉 자료 구조상에서, 어떤 노드가 어떤 노드와 인접해 있는지등은 표시할 필요가 없다. 아래 그림을 보자, 아래 그림에서 1과 5는 연결이 되어 있다. (1->2->5 경로) 4,2는 연결되어 있지 않다.



이 처럼 노드간의 연결 여부만 판단 하는 것이 동적 연결 알고리즘 (Dynamic Connectivity)문제이다.

 

QuickUnionFind


이를 구현하는데 몇가지 알고리즘이 있는데, 가장 간단한 알고리즘으로는 QucikUnionFind라는 알고리즘이다.

QuickUionFind 알고리즘은 아래와 같이 일차원 배열을 이용해서 구현하는데, 배열의 Index가 노드명, 그 값이 ID이다. ID가 같은 노드들은 서로 연결되어 있는 것으로 취급 한다.



이런식으로 된다. 값이 9,8,7 3의 컴포넌트로 나뉘어 짐을 알 수 있다.

이 알고리즘의 경우 구현은 쉽지만, 매번 연결을 추가할때 마다 ID값을 스캔해서, 같은 컴포넌트에 있는 노드의 ID값을 매번 변경해야 하기 때문에 성능이 매우 낮다. O(N^2)의 복잡도를 갔는다.


Tree (QuickFindUF)


그래서 이를 보완하는 알고리즘으로는 Tree를 사용하는 방법이 있는데, Tree의 값에는 이 노드와 연결된 상위 노드의 인덱스 값을 가지게 한다.

이때 주의해야 하는 것이, Tree에서 표현되는 상하위 노드의 연결 내용은 중요하지 않다. 실제로 그림에서 1,3 노드간에는 연결은 없지만, 필요하다면 Tree에서는 1,3 노드를 연결해서 표현하되, 1,3이 하나의 트리에만 있으면 된다.

헷갈릴 수 있는 부분이, 각 노드간의 연결을 온전히 저장하는 것이 아니라, 컴포넌트에 어떤 노드가 있는지를 저장하는 것이기 때문에, 각 노드 간의 연결성에 초점을 맞출 필요가 없다. 



위의 그래프 저장 결과는 배열에서 다음과 같다.

 



여기서 노드가 연결되어 있는지를 찾으려면, root 노드가 같은지를 비교하면 된다.

즉, 노드 9,5가 연결되어 있는지 찾으려면 9 --> 5 까지의 경로를 트래버스 하는 것이 아니라, 9와 5의 root 노드(1)을 찾아서 동일한지를 비교하면 된다.


WeightTree

위의 트리 기반의 알고리즘의 경우, Depth가 비약적으로 길어질 수 있는 문제가 있는데, 이를 해결하기 위해서는 WeightTree라는 알고리즘을 사용할 수 있다. 이 알고리즘은 두개의 트리를 병합할때, 항상 작은 트리를 큰 트리의 루트에 붙이게 함으로써 전체 트리의 Depth를 줄이는 방법이다.


아마 이 알고리즘을 보지 않았더라면, Dynamic Connectivity 문제도 Node *  기반의 자료 구조를 만들어서 DFS(깊이 우선 검색)으로 해결하려고 하지 않았을까? (성능은 무지 안나오겠지)


참고자료 및 소스

http://algs4.cs.princeton.edu/15uf/

저작자 표시 비영리
신고