반응형

 레퍼런스 사이트에서 보면, unordered_map의 insert나 delete나 find 함수는 평균적으로 O(1)이라고 나와 있습니다. 그런데, 최악의 경우, O(n)이라고 나와 있습니다. 

 

 

[관련글]

해쉬 테이블의 평균 복잡도를 분석해 봅시다.

 

 

 왜 최악의 경우에 O(n)일까요? 이유는 간단합니다. Chaining 방식이 List이기 때문입니다. 그러면, 왜 최악의 경우에 선형 시간이 걸리는지는 해결이 된 셈입니다. 하나의 버킷에 좌르르륵 skew가 되어 있으면 List의 경우에는 계속 찾아야만 하니까 O(n)이 걸립니다.

 

 그런데, 아무리 최악의 경우가 O(n)이라고 한다면, 저격 데이터를 만드는 게 굉장히 어렵다면 사실 그냥 써도 무난할 겁니다만. 생각보다 충돌이 극단적으로 일어나는 데이터를 만드는 작업이, 특히 키 값이 정수형인 경우에, 그렇게 어렵지 않다는 것이 문제입니다.

 

 


 먼저 Hash Table, 줄여서 HT에는, 버킷과, 버킷에 매달린 자료 구조로 구성되어 있어요. 보통, 일정 이상의 수 만큼의 키가 들어가게 되면, 재해싱을 하게 되는데요. 그냥 버킷을 확 늘려준다. 정도로 생각하시면 됩니다. 실험 프로그램 1을 보겠습니다.

 

 

 먼저 vector를 선언했습니다. 그런데, int형을 저장하는 배열이군요. 무엇을 저장할까요?

 

 

 for문 안에서 무엇을 하고 있나요? key값이 i인 데이터를 계속 넣고 있습니다. 그러면 unordered_map에 Key가 계속 들어가고 있을 겁니다. 넣고 나서, bucket_count를 계속 vector에 넣는데요. 이것은, 키 값이 x개가 들어갔을 때, 할당된 총 바구니의 수가 몇 개인지를 알아옵니다.

 

 그러면 키가 들어감에 따라서, Hash Table에 있는 버킷 수를 알아올 수 있을 거에요. 그리고, 중복 데이터를 제거하기 위해서, v.erase(unique(v.begin(),v.end()),v.end()); 를 수행합니다. 그러면, 버킷 사이즈가 어떻게 변했는지에 대해서 추적이 가능할 거에요.

 

 

 그러면, 3, 7, 17, 37, 79, 167, ... 과 같은 데이터들이 나오게 되는데요. 저는 여기에서 3209라는 숫자에 주목해 보겠습니다.

 

 

 실험 프로그램 2에서는, 3209로 나누었을 때 나머지가 1인 서로 다른 수 3000개를 넣습니다. 즉, 모듈러 3209 합동이면서, 3000개의 수가 모두 다릅니다. 그러면 3209x + 1 이렇게 넣으면 되겠네요.

 

 

 bucket_size는 i번 바구니에 몇 개의 원소가 들어있는지를 알아내는 함수입니다.

 

 

 실행 결과는 #1 : 3000입니다. 1번 버킷에 3000개의 수가 skew 되었다는 것입니다. 이것은 상당히 중요한 것 중 하나인데요. 어떻게 버킷 수가 변하는 지만 알면 정수형 Key에 대해서는 쉽게 저격이 가능하다는 이야기가 되겠습니다. 즉, 계속 데이터를 넣을 때 마다, bucket 수가 어떻게 변하는지에 대한 수열을 얻어온다면, 최악의 케이스를 만드는 일은, 그렇게 어려운 일이 아니라는 것을 알 수 있어요.

 

 


 위의 데이터는 제 리눅스 환경에서 실험을 해 본 거고요. wandbox나, ideone에서도 실험을 해 봐야 겠습니다.

 

 

 

 사실, 그렇게 어려운 일도 아닌 것이, bucket_size(n)하고, bucket_count() 함수만 잘 쓰면 되기 때문입니다.

 

 

 실험 프로그램 1을 wand에서 돌려보았습니다. 그랬더니 2, 5, 11, ... , 3739, ... 이렇게 나옵니다. 아. 쉽진 않네요. 일단, 3000개의 키를 넣을 거니까, 3739를 선택해 봅시다. 그러면 실험 프로그램 2가 아래 코드와 같이 바뀌어야 할 겁니다.

 

 

 정확하게 말하면 7번째 줄만 바뀐 셈입니다. 제 리눅스에서는 3209*i+1을 넣었는데, wand에서는 3739*i+1을 넣었습니다. 3739 모듈러 합동인 수 3000개를 좌르륵 다 넣어본 겁니다. 그리고 각 버킷에 몇 개의 수가 들어있는지를 출력합니다. 결과는 어떻게 나올까요?

 

 

 #1 : 3000이 나옵니다. 1번 버킷에 3000개의 수가 들어있다는 것입니다. 이는 한 바구니에 skew가 되었다는 의미입니다.

 

 

 ideone에서는 어떨까요? 프로그램 1을 돌려봤더니, 버킷 수가 요래 변합니다. 3739가 눈에 보이는군요.

 

 

 키 값을 넣을 때, 3739 모듈러 합동인 수들을 모두 넣겠습니다. 3739x + 1을 넣어버리면 될 거에요. x가 0부터 3000까지 변하게 하면서요. 이 때, #1번에 3000개의 수가 skew가 된다는 것을 알 수 있습니다. List의 특성상, n개의 원소가 List에 들어가게 되면 찾는데 최악의 경우에 O(n)이 걸립니다.

 

 따라서, 최악의 경우에 O(n)이 걸리고, Key가 정수인 경우, 최악의 케이스를 만드는 데 그렇게 어렵지 않다는 점만 짚고 넘어가시면 되겠습니다.

반응형

댓글을 달아 주세요

  1. 곰곰지영

    잘 읽고 가용 ~:)

  2. #§*

    정말 너무 어렵네요..,, 제가아는건 웹코딩 쪼금인데 웹코딩은 코딩강아지님에게 언제배워보나요 ㅎㅎㅎ

  3. hunnek

    어렵네요..
    잘보고갑니다.