나는 기사 "Rationale for Adding Hash Tables to the C++ Standard Template Library"을 읽고 있어요, 나는이 단순 해 보이는 문장 이해하지 못하는 : 해시 테이블로역할 해시 테이블 항목의 공간 소비를 계산
, 여분의 메모리의 양을 필요한 요소는 테이블의 구성과 부하 계수 (표기법이 인 조직에 따라 다름)에 따라 다릅니다. 가장 간단한 경우는 열린 주소 지정이라는 조직 이며 모든 항목은 단일 임의 액세스 테이블에 저장됩니다. [...]이 경우 엔트리 당 사용 된 메모리 양은 M/α입니다.
* M은 키와 관련 값에 필요한 바이트 수이며, α는로드 요소입니다.
왜 M/α입니까? 왜 단순히 M + (각 버킷의 메모리 양 * 총 버킷)가 아닌가?
오픈 어드레싱에서는 고정 된 크기의 슬롯 배열을 사용하여 요소를 분산시킵니다. 이것은 요소를위한 공간과 (옵션으로) 어떤 슬롯이 가득 차 있고 어떤 슬롯이 비어 있는지 표시하기 위해 던져진 제어 비트가있는 단순한 배열입니다.
슬롯이있는 테이블이 있고 테이블에 n 개의 요소를 배포하려고한다고 가정 해 보겠습니다. 즉, α = n/s, 요소 수를 슬롯 수로 나눈 값입니다. 전체 표의 공간 사용량은 sM이며, 슬롯이 있고 각 슬롯은 M 바이트를 사용하기 때문입니다. 따라서 요소 당 사용 된 메모리를 계산하려면 수식이 나오는 sM/n = M/(n/s) = M/α을 계산해야합니다. 직관적으로 이것은 의미가 있습니다. 테이블에 단일 요소가있는 경우로드 요소는 1/s이고 전체 메모리 (Ms)를 요소 수 (1)로 나눈 값은 Ms입니다. 반면에 테이블이 완전히로드 된 경우 n = s)이면 α = 1이고 총 메모리 (Ms)를 요소 수로 나눈 값은 M과 같습니다.
금액을보고 올바른 계산을 할 수 있습니다. 버킷 당 메모리를 계산하고 버킷의 수를 곱합니다. M을 요소 당 크기로, s를 슬롯 수로 처리하면 총 공간 사용량이 M이됩니다. M 항을 추가 할 필요가 없으므로 실제로는 잘못된 단위를 갖습니다. M 단위는 "요소 당 바이트"이고 Ms는 "바이트"단위를 가지므로 함께 추가하면 안됩니다.