해시충돌 검색 결과

해당 글 2건
c++ unordered_map : 어떻게 최악의 데이터를 만들까?

레퍼런스 사이트에서 보면, unordered_map의 insert나 delete나 find 함수는 평균적으로 O(1)이라고 나와 있습니다. 그런데, 최악의 경우, O(n)이라고 나와 있습니다. [관련글] 해쉬 테이블의 평균 복잡도를 분석해 봅시다. 왜 최악의 경우에 O(n)일까요? 이유는 간단합니다. Chaining 방식이 List이기 때문입니다. 그러면, 왜 최악의 경우에 선형 시간이 걸리는지는 해결이 된 셈입니다. 하나의 버킷에 좌르르륵 skew가 되어 있으면 List의 경우에는 계속 찾아야만 하니까 O(n)이 걸립니다. 그런데, 아무리 최악의 경우가 O(n)이라고 한다면, 저격 데이터를 만드는 게 굉장히 어렵다면 사실 그냥 써도 무난할 겁니다만. 생각보다 충돌이 극단적으로 일어나는 데이터를 만드는 ..
레퍼런스/분석 2019. 10. 23. 15:45
비둘기집의 원리 : 왜 해시충돌을 피할 수 없는가?

해시를 하기 전에, 비둘기집의 원리를 간단하게 짚고 넘어가겠습니다. 집이 k개가 있고 비둘기가 k+1마리가 있습니다. 그리고 비둘기들은 상자들 중 하나에 들어갔을 때, 이들이 2마리 이상 들어가는 집이 최소한 하나 존재합니다. 집 k개를 그려보았습니다. 그리고 밑에는 비둘기 k+1마리가 있어요. 그러면, 결론을 부정해 봅시다. '2마리 이상 들어가는 집이 최소한 하나 존재한다'는 명제의 부정은, 2마리 이상 들어가는 집이 존재하지 않는다입니다. 그러면 k+1마리가 있고, 집이 k개 있을 때, 많아봤자 1마리가 들어간다가 참이라고 해 봅시다. 즉 ~p가 참이다라고 한 겁니다. 그러면 각 상자에는 최대 1마리씩만 들어갈 수 있으니까, k개의 상자에는 최대 k마리가 들어갈 수 있습니다. 그러면 나머지 1마리는..
자료알고/자료구조 2019. 8. 17. 23:09