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


Archive»


 

'자료구조'에 해당되는 글 2

  1. 2016.02.06 Hashtable의 이해와 구현 #1 (6)
  2. 2016.02.05 dynamic array resizing에 대해서. (5)
 

Hashtable의 이해와 구현 #1

프로그래밍/알고리즘 | 2016. 2. 6. 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 클래스를 구현하는 방법에 대해서 알아보도록 하겠다. 

본인은 구글 클라우드의 직원이며, 이 블로그에 있는 모든 글은 회사와 관계 없는 개인의 의견임을 알립니다.

댓글을 달아 주세요

  1. Mei 2016.02.06 12:57  댓글주소  수정/삭제  댓글쓰기

    Effective Java 책에 소개된 Josh Bloch's recipe라는 hash function 만드는 방법입니다.
    http://stackoverflow.com/questions/113511/best-implementation-for-hashcode-method

  2. shwlinux 2016.02.11 16:21  댓글주소  수정/삭제  댓글쓰기

    hash_function(key) / size_of_array 이 부분 오타 같습니다!

  3. ff 2016.02.23 16:21  댓글주소  수정/삭제  댓글쓰기

    separate chaining 방식은 레디스 hashtable에도 사용되더군요

  4. bdjj_dreamer 2018.02.08 10:16  댓글주소  수정/삭제  댓글쓰기

    index = hash_function(“John Smith”) % 16 를 통해서 index 값을 구해내고, array[16] = “John Smith의 전화 번호 521-8976”을 저장한다.
    출처: http://bcho.tistory.com/1072 [조대협의 블로그]

    에서 array[16]이 아니라 array[index]로 이해하면 되는거겠죠?

  5. 열코 2018.09.07 14:59 신고  댓글주소  수정/삭제  댓글쓰기

    공부하는데 많은 도움이 됬습니다.
    감사합니다.

  6. 2019.07.22 16:29  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

dynamic array resizing에 대해서.

프로그래밍/알고리즘 | 2016. 2. 5. 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 )

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


본인은 구글 클라우드의 직원이며, 이 블로그에 있는 모든 글은 회사와 관계 없는 개인의 의견임을 알립니다.

댓글을 달아 주세요

  1. Mei 2016.02.05 20:37  댓글주소  수정/삭제  댓글쓰기

    평소에 블로그를 잘 보고 있는 개발자입니다.
    HashMap의 table을 배열이 아니라 List로 만들게 되면,
    탐색시간이 O(n)이 되기 때문에 Hash를 사용하는 의미가 없어져 버립니다.
    Constant time에 접근을 하기 위해서는 반드시 배열을 사용해야 합니다.
    즉, 이 코드에서 table 증가시 array resize를 하는 것은 어쩔 수 없는 측면인 것이죠.

    • 조대협 2016.02.06 01:09 신고  댓글주소  수정/삭제

      의견 감사합니다.
      HashTable의 O(n)의 검색 시간이 나오지 않는 것으로 알고 있습니다.
      index의 충돌이 생겼을때, 충돌을 해결하기 위해서 추가 검색이 발생하고, Linked List를 이용했을 경우에는 n의 검색이 소요 됩니다.
      실제로 JDK 1.8에서는 내부적으로 index에 대한 bucket에 대해서, List 구조로 충돌된 index의 데이타를 사용하고, 해당 index에 대해서 충돌 데이타가 많을 경우에는 Tree구조로 바꿔서 저장하고 있습니다.

      참고 : http://d2.naver.com/helloworld/831311

  2. Mei 2016.02.06 08:04  댓글주소  수정/삭제  댓글쓰기

    HashMap의 table은 일반적으로 이야기하는 bucket이 아닌지요?
    제가 말씀드린 것은 bucket(=table in HashMap)의 탐색 시간을 말씀드린 것입니다.
    즉, bucket 탐색 시간이 constant time (n이 아닙니다)이 되기 위해서는 array가 되어야 하는 것이죠.
    동일 hash를 갖는 bucket 내부의 element 들은 아래 get함수를 보면 아시겠지만 실제로 linked list 입니다.
    http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.get%28java.lang.Object%29

  3. kisow 2016.02.11 19:49  댓글주소  수정/삭제  댓글쓰기

    안녕하세요^^. 저도 블로그를 구독해 보고 있는 개발자입니다.
    다양한 분야의 좋은 글들 많이 읽고 있습니다.
    매번 읽기만 하다가 관심있는 주제라 글을 남겨봅니다.

    Mei님 말씀처럼 HashTable의 bucket access는 자료구조 특성상 O(1) 시간 복잡도가 요구되므로
    bucket 저장에 Linked List 자료구조는 애당초 의미가 없습니다. chain 방식이나 open address 방식에서
    충돌을 해결하기 위해서 Linked list 유사하게 선형 탐색하는 부분은 버킷크기가 충분히 큰 경우 어짜피 상수처리되기 때문에 중요하지 않구요.
    HashTable bucket에서 dynamic array를 쓰는 것은 본문에 생각하신 이유보다 더 직접적으로는
    HashTable ADT에 기대되는 시간복잡도를 충족시키기 위한 제약사항에 가깝습니다.

    하지만 본문의 중심 생각에는 100% 공감하고 동의 합니다.
    아주 예전에 acmicpc 준비하면서 알고리즘 한참 파던 때는 알고리즘/자료구조의 시간/공간 복잡도가 절대적이라고 생각했었는데,
    최근에 10년가까이 대용량 데이터를 다루다보니 항상 그런 것은 아니더군요.
    N이 충분히 작지 않은 경우에도 기존 시공간 복잡도 분석의 상식을 뒤엎을 만큼 성능에 영향을 미칠 수 있는 시스템 상의 요소들이 많고,
    H/W나 O/S 같은 하단 인프라가 발전하면서 눈에 보이지 않던 그 영향이 점점 더 커지고 있습니다.
    일만 PC나 commodity server 같은 보편화된 환경에서 특히 더 그런 것 같고요.

    특히 Linked List vs vector(dynamic array) 간의 성능 특성에 대한 상식에 논란이 있습니다.
    몇년 전에 Linked List 이제 그만 쓰고 무조건 vector 쓰라는 주장도 나올 정도로 논란도 됐었고요.
    http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html#more-818
    http://highscalability.com/blog/2013/5/22/strategy-stop-using-linked-lists.html

    극단적으로 얘기해서 그렇지 최적화 관점에서 보면 충분히 의미 있는 지적이라고 생각합니다.
    실제로 저희도 훨씬 이전부터 Linked List를 꼭 써야 하는 경우가 아니면 성능상 vector를 쓰는데, 꼭 Linked List를 써야하는 경우가 많지 않더군요.굳이 꼽자면 사용자 API로 덩치도 크고 복합적인 non-POD 데이터들의 목록을 뽑아줄 때, 성능은 크게 중요하지 않고
    (어짜피 튜닝포인트도 아니고, POD도 아니라 어짜피 최적화도 기대하기 힘들고)
    API 사용자들의 창의적인 조합에도 리소스를 덜 써야 하는 경우에만 썼던 것 같습니다.

    특히 본문에 언급하신 "불확실한 데이터 크기"가 유일한 이유라면 dynamic array resize가 더 낫습니다.
    SIMD나 GPGPU까지 가지 않더라도 아래와 같은 이유 때문에라도 dynamic array를 쓰면서 resize하는게 전체적으로 더 효율적인 선택일 수 있습니다.

    1.
    추가하는건 원소가 작은 POD라면 복사비용 자체도 생각보다 비싸지 않습니다.
    게다가 벌크 복사는 최신 CPU에 맞게 컴파일러가 알아서 최적화(vectorization) 해줄테고,
    메모리 대역폭도 거의 정체된 다른 리소스들에 비해서 아직은 점점 좋아지고 있고요.
    패턴상 realloc 자체가 armotized cost 라 항상 치르는 비용도 아니어서 realloc이 필요 없는 횟수만큼 비용 자체가 분할상환될테고
    미리 예상되는 만큼 적당히 realloc해두면 효과를 볼 수 있어서
    생각보다 dynamic array에서의 실제 추가 비용이 떨어지지 않을 수 있습니다.

    2.
    탐색 비용은 연속적인 array 형태가 불연속 적인 Linked List 보다 압도적으로 좋습니다.
    알고리즘 상 랜덤 엑세스가 가능한 것도 그렇지만 순차 탐색만 놓고 보더라도 지역성 때문에 array가 훨씬 좋습니다.

    보통 컴파일러 최적화 수준에서 데이터 의존성이 없는 경우에 instruction 수행 순서를 바꿔서 명령어 수행의 파이프라이닝을 극대화 하는 경우가 많은데,
    노드를 이동 해봐야 다음 노드 위치를 알 수 있는 Linked List는 이런 최적화를 기대하기 어렵습니다.
    또, H/W 레벨에서 상대적으로 느린 메모리 대역폭을 보완하기 위해서 prefetch 할 수 있는데
    연속된 array는 효과를 볼 수 있겠지만 링크된 데이터 구조에서는 역시 기대하기 어렵습니다.

    게다가 Linked List는 DRAM과 TLB의 지역성에도 않좋은 영향을 미치고 cache 히트율을 떨어뜨립니다.
    불연속적이고 더 잦은 메모리 할당을 하는 Linked List는 리스트 하나가 여러 DRAM 페이지에 흩어질 가능성이 높고
    결과적으로 더 많은 DRAM 페이지를 요구하고 단편화도 있을테니 물리적인 메모리 usage도 올라갈껍니다.
    리스트 하나를 접근하는 관점에서 봐도 사용하는 DRAM 페이지가 많다는건 그만큼 지역성이 떨어지고
    그 자체로 한정된 CPU cache 용량에서 히트율 자체에도 손해를 볼테고요.
    현대 O/S에 보편적인 가상 메모리를 지원하기 위해 CPU에 있는 TLB 역시 DRAM 페이지 번호를 찾기 위한 캐시인 만큼
    요구되는 DRAM 페이지가 많아지면 같은 매커니즘으로 히트율 손해를 볼겁니다.

    어떻게 allocator를 잘 짜서 간접층을 두고 실제로는 연속적인 메모리 공간을 크게 할당하도록 컨트롤하면
    어느 정도 완화는 되겠지만 Linked List에만 있는 링크 자체도 낭비고 그렇게 하는 것 자체가 크게 보면
    dynamic array resizing이고요.

  4. 조대협 2016.02.12 13:55 신고  댓글주소  수정/삭제  댓글쓰기

    의견 감사드립니다. 여러가지로 생각하게 만드는 의견이네요