해시 테이블이나 정렬 된 목록에서 항목을 찾는 것이 더 빠릅니까?

Question

해시 테이블이나 정렬 된 목록에서 항목을 찾는 것이 더 빠릅니다.

Answer 1

알고리즘 복잡성은 알아두면 좋지만 해시 테이블은 0 (1) 인 것으로 알려져 있지만 정렬 된 벡터 (목록에서는 정렬 된 배열을 사용하는 것이 더 나을 것이라고 생각합니다)는 0 n) 액세스 시간.

그러나 복잡한 표기법을 사용하면 N이 무한대로가는 데 필요한 액세스 시간을 확보 할 수 있습니다. 즉, 데이터가 계속 증가 할 경우 복잡도 표기법을 선택하면 알고리즘 선택에 대한 힌트가 제공됩니다.

데이터가 다소 길어질 것이라는 것을 알고있는 경우 : 배열/해시 테이블에 몇 개의 항목 만있는 경우와 같이 시계와 측정 값을 사용해야합니다. 그러니 시험 받으십시오.

예를 들어 다른 문제 : 배열 정렬. 에 대한 몇 가지 항목 버블 정렬 O (N^2)는 빠른 정렬보다 빠르다. (n log n) ..

또한 다른 답변에 따라, 그리고 항목의 경우 해시 테이블 인스턴스에 가장 적합한 해시 함수를 찾아야합니다. 그렇지 않으면 Hank Gay의 답변에서 지적한 것처럼 해시 테이블에서 조회 성능이 크게 저하 될 수 있습니다.

편집 : the meaning of Big O notation을 이해하려면이 기사를 살펴보십시오.

Answer 2

해시 알고리즘이 인 경우 매우이 느리거나 나쁜 경우가 아니면 해시 테이블이 더 빠릅니다.

업데이트 : 의견 제시자가 지적한 것처럼 너무 많은 충돌로 인해 성능이 저하 될 수있는 것은 아니며 해시 알고리즘이 좋지 않아 해시 테이블이 충분히 크지 않기 때문에 성능이 저하 될 수 있습니다. 대부분의 라이브러리 구현 (적어도 고급 언어)은 백그라운드에서 해시 테이블을 자동으로 확장하므로 성장을 유발하는 인서트에서 예상보다 느린 성능을 유발할 수 있습니다. 그러나 자신 만의 롤링을 수행한다면 분명히 뭔가가 있습니다 고려하다.

Answer 3

'정렬 된 목록'으로 '랜덤 액세스 가능, 정렬 된 컬렉션'을 의미한다고 가정합니다. 목록에는 요소별로 트래버스 할 수있는 속성 만 있으므로 O (N) 복잡도가 발생합니다.

정렬 된 인덱싱 가능한 컬렉션에서 요소를 찾는 가장 빠른 방법은 N 진법 검색 O (logN)이며, 콜리 전이없는 해시 테이블은 O (1)의 찾기 복잡성을가집니다.

Answer 4

경우에 따라 콜렉션의 크기에 따라 다르지만 (다소 적게는 구현 세부 사항) 귀하의 목록이 매우 작다면 5 ~ 10 개의 항목 일 가능성이 높습니다. 목록이 더 빠를 것이라고 생각합니다. 그렇지 않으면 xtofl이 맞습니다.

Answer 5

HashTable은 10 개가 넘는 항목을 포함하는 목록에 더 효율적입니다. 목록에 10 개 미만의 항목이 있으면 해시 알곤으로 인한 오버 헤드가 더 커집니다.

빠른 사전이 필요하지만 순서가 지정된 방식으로 항목을 유지해야하는 경우 OrderedDictionary를 사용하십시오. (.Net 2.0 이후)

Answer 6

SortedList에서의 작업은 O(log n)이고, 동일한 작업은 HashTable은 O(1)입니다. 따라서 은 일반적으로입니다. HashTable은 훨씬 빠릅니다.

이

• 이 목록의 크기 충돌
• 해시 알고리즘의 성능
• 수/해시 알고리즘의 품질는

Answer 7

상황에 따라 다르다 :하지만이은 여러 가지 요인에 따라 달라집니다 전적으로 귀하가 저장 ​​한 데이터의 양에 달려 있습니다.

해시 테이블이 너무 커서 충분한 메모리가 있다고 가정하면 해시 테이블은 고정 된 시간 내에 대상 데이터를 찾습니다. 그러나 해시를 계산해야 할 필요가 있습니다. 고정 된) 오버 헤드.

정렬 된 목록을 검색해도 해싱 오버 헤드가 발생하지 않지만 목록이 커질수록 실제로 대상 데이터를 찾는 작업을 수행하는 데 필요한 시간이 늘어납니다.

일반적으로 정렬 된 목록은 일반적으로 작은 데이터 세트의 경우 더 빠릅니다. 자주 변경되거나 매우 드물게 검색되는 매우 작은 데이터 세트의 경우 un 정렬 목록은 정렬 작업의 오버 헤드를 피하기 때문에 더 빠릅니다. 데이터 세트가 커지면 목록의 크기가 커집니다 검색 시간은 해싱의 고정 오버 헤드를 과소 해 해시 테이블이 빨라집니다.

여기서 중단 점은 특정 해시 테이블 및 정렬 목록 검색 구현에 따라 달라집니다. 일반적으로 크기가 큰 데이터 세트에서 테스트 및 벤치 마크 성능을 실행하여 어떤 경우에 실제로 더 나은 성능을 낼지 확인하십시오. (코드가 이미 "빠름"으로 실행되고있는 경우에는 더 이상 사용하지 말고 최적화 할 필요가없는 것을 최적화하는 것에 대해 걱정하지 마십시오.)