0
다른 객체 (예 : 3)가 동일한 해시 코드를 가지고 결과적으로 동일한 버킷에있는 경우 맵의 크기는 어떻게되어야합니까?다른 객체 (예 : 3)가 동일한 해시 코드를 갖고 결과적으로 동일한 버킷에 있으면 맵의 크기는 어떻게되어야합니까?
A
답변
0
결과 해시 테이블의 크기는 우리가 사용하고있는 스키마 collision resolution에 따라 다릅니다.
가장 간단한 경우 별도의 연결 (링크 된 목록 포함)과 같은 것을 사용하고 있습니다.
이 경우 우리는 N 개의 버킷 배열을 가지며 각 버킷에는 연결된 목록에 대한 참조가 포함됩니다.
우리는 높은 수준에서 다음 목록에 링크 된 하나의 목표는 따라서 길이 3.
로 성장할 것 같은 해시 코드를 공유하는 모든있는 해시 테이블에 3 개 항목을,,, 삽입 진행하면 버킷 참조 + (점유 된) 연결 목록의 요소를 저장하기위한 3 "단위"공간을 저장하기 위해 최소한 N "단위"의 공간이 필요합니다.
이러한 "단위"의 정확한 크기는 단어 크기 (32 비트 대 64 비트) 및 링크 된 목록의 정확한 정의 (단독 또는 이중 연결 목록)와 같은 구현 세부 사항에 따라 달라집니다. .
32 비트 시스템에서 단일 연결 목록 (각 버킷 용)을 사용한다고 가정하면 전체 크기는 32 * N + (32 + x) * 3입니다. 여기서 x은 저장하는 데이터 형식의 크기를 나타냅니다 (예 : ints , double, string 등)
더 자세히 알고 싶으면 더 많은 정보를 얻기 위해 "해시 테이블 충돌"을 검색해보십시오.
우리는 * 왜 * 또는 이것이 필요한지 알 수 있습니까? – Eugene