해시 테이블 대 선형 목록

Question

선형 목록의 키워드 검색이 해시 테이블보다 빠르다는 인스턴스가 있습니까?

선형 목록의 키워드 검색이 해시 테이블 검색보다 빠르다는 프린지 사례가 있는지 기본적으로 알고 싶습니다.

감사합니다.

Answer 1

예, 매우 적은 수의 요소 인 경우. 해시가 어떻게 작동하는지 생각해보십시오. 버킷을 찾기 위해 해시를 계산 한 다음 해당 버킷의 목록을 검색해야합니다. 게다가 복잡한 다중 레벨 해시 등이 될 수 있습니다. 따라서 선형 목록을 통한 검색이 해시 검색 알고리즘보다 많은 작업을 수행하는 경우에도 문제가 발생합니다.

찾고있는 요소가 항상 목록의 시작 부분 또는 시작 부분에있는 경우도 있습니다. 당신이하는 일에 따라 일어날 수 있습니다.

다른 것들도 있지만 생각해 보면 도움이 될 것입니다.

아직도 혼란스러워하지 마세요. 해시는 보통 원하는 것입니다.

Answer 2

해시 테이블에서 검색 항상 현실에서 일정한 시간이 아니다. 해시 함수가 데이터와 일치하지 않는 경우 많은 충돌이 발생할 수 있으며 모든 데이터 항목의 해시 값이 같은 극단적 인 경우 결과는 선형 검색과 매우 유사합니다. 세부 사항에 따라이 효과적인 선형 검색은 배열의 데이터에 대한 선형 검색보다 느리게 작동합니다. (예 : 프로세서 캐시를 제대로 사용하지 않는 2 차 탐색 시퀀스가있는 open addressing) 배열을 통한 선형 검색보다 속도가 느릴 수 있습니다.

다음은 모든 키가 끝난 실제 사례입니다 같은 양동이 : Java bug 4669519.