재해싱 (rehashing) : 시간 복잡도를 분석해 보면서 왜 필요한지 알아봅시다.
Hash에서, 면접에서 물어볼 만한 키워드들을 천천히 알아보도록 하겠습니다. 이 중 오늘은 재해싱에 대한 이야기를 간단하게 하고 넘어가겠습니다. Hash Table은, 저번시간에 배운 바로는, 버킷에다가, 데이터를 주렁 주렁 매달아 놓는 식으로 많이 처리를 한다고 했었습니다. 보통, Chaining을 사용하는 경우, List를 사용한다고 했었습니다. 저는 간단하게 구현하기 위해서, 2차원 배열로 구현을 했었고요. 그런데, 생각을 해 봅시다. 수가 2개만 들어왔어요. 그런데, 1000만개의 바구니를 미리 만들어 놓을 필요가 있을까요? 2개를 위해서, 1000만개의 바구니를 생성한다. 이것만큼 낭비가 없습니다. 그러면, 어떻게 할 거냐. 초기 사이즈를 매우 작게 잡습니다. 예를 들자면, 2개의 초기 buck..
자료알고/자료구조
2019. 9. 13. 00:59
최근댓글