6
A
답변
5
코드는 OpenHashMap의 사용 사례 중 하나와 정확히 일치합니다. 코드 : OpenHashMap (scaladoc)에 대한
println ("scala OpenHashMap: " + time (warmup) {
val m = new scala.collection.mutable.OpenHashMap[Int,Int];
var i = 0;
var start = System.currentTimeMillis();
while(i<100000) { m.put(i,i);i=i+1;};
})
설명 : 오픈 해싱 방식에 따라
변경 가능한 해시 맵. 정확한 체계 은 정의되어 있지 않지만 연속 해시 코드가 포함 된 삽입물이 불필요하게 불이익을받지 않도록 합당한 노력을 기울여야합니다. 특히 에서 연속적인 정수 키의 매핑은 상당한 성능 손실없이 작동해야합니다.
내 강조. 당신의 연구 결과를 설명합니다. HashMap 대신 OpenHashMap을 사용할 때? Wikipedia을 참조하십시오. 거기에서 : 연결리스트와
사슬로 매인 해시 테이블은 간단한 알고리즘 기본적인 데이터 구조를 필요로하기 때문에 인기가 있고, 다른 방법에 적합하지 않은 간단한 해시 기능을 사용할 수 있습니다.
표 연산의 비용은 선택된 버킷의 항목을 원하는 키로 검색하는 데 드는 비용입니다. 키 분포가 이라면 균일 한 평균 조회 비용은 버킷 당 평균 키 수 ( ), 즉로드 요소에 따라 달라집니다.
표 테이블 n의 수가 슬롯 수보다 훨씬 많은 경우에도 연결 해시 테이블은 유효합니다. 성능은 으로 부하율에 따라 (선형으로) 저하됩니다. 예를 들어, 1000 개의 슬롯과 10,000 개의 저장된 키 (로드 팩터 10)가있는 연결 해시 테이블은 10,000 슬롯 테이블 (로드 팩터 1)보다 5-10 배 느립니다. 여전히 일반 순차 목록 인 보다 1000 배 빠르고 균형 잡힌 검색 트리보다 빠릅니다. 모든 항목 해시 테이블 비효율적 인 경우에 동일한 버킷에 삽입하고, 선정 된 버킷 데이터 구조를 탐색 그 때 별도 체이닝 들어
는 최악의 시나리오이다. 후자가 선형 목록 인 경우, 검색 절차는 모든 항목을 스캔해야 할 수 있습니다. 따라서 최악의 경우의 비용은 표의 항목 수 n에 대해 에 비례합니다.
이것은 일반적인 설명입니다. 이러한 것들과 마찬가지로, 성능은 유스 케이스에 따라 다르며, 관심이 있다면 측정해야합니다.