동적 크기 해시 테이블을 구현하는 방법은 무엇입니까?

Question

해시 테이블 데이터 구조의 기본 원칙을 알고 있습니다. 내가 크기 N의 해시 테이블을 가지고 있다면 가능한 한 균등하게이 N 개의 버킷에 데이터를 분산시켜야합니다.

실제로 대부분의 언어에는 해시 테이블 형식이 내장되어 있습니다. 내가 사용할 때 해시 테이블의 크기를 미리 알 필요가 없습니다. 나는 단지 내가 원하는 것을 넣었다. 예 : Ruby :

h = {} 
10000000.times{ |i| h[i]=rand(10000) } 

어떻게 할 수 있습니까?

Answer 1

the Dynamic resizing section of the Hash table article on Wikipedia을 참조하십시오.

일반적으로 접근 방식은 a dynamic array과 같은 논리를 사용합니다. 일부 버킷이 있고 해시 테이블에 너무 많은 항목이있는 경우 더 큰 크기의 새 해시 테이블을 만들고 모든 항목을 새 것으로 이동합니다. 해시 테이블.

해시 테이블의 유형에 따라이 크기 조정은 정확성을 위해 필요하지 않을 수도 있습니다 (즉, 크기 조정 없이도 작동 할 수 있음).하지만 성능을 위해서는 반드시 필요합니다.