HashSet <T> (IEqualityComparer <T>)의 조회 시간 복잡도는 얼마입니까?

C# .NET에서 조회 용 O (1) 시간 복잡성으로 인해 HashSet을 사용하는 것이 좋습니다. 질의를 할 많은 양의 데이터가 있다면, 나는이 시간 복잡성을 가지고 있기 때문에 종종 List에 HashSet을 사용하는 것을 선호합니다.HashSet <T> (IEqualityComparer <T>)의 조회 시간 복잡도는 얼마입니까?

은 무엇 나를 혼란스럽게하는 것은 인수로 IEqualityComparer 걸리는 HashSet에 대한 생성자입니다 : 위의 링크에서

http://msdn.microsoft.com/en-us/library/bb359100.aspx

의 발언은 "생성자는 O (1) 연산입니다 있습니다 "그러나 이것이 사실이라면 조회가 여전히 O (1)인지 궁금합니다.

특히, 내가 Comparer을 작성하여 HashSet의 생성자에 전달하면 조회를 수행 할 때마다 Comparer 코드를 모든 키에 대해 실행해야합니다. 일치하는 것이 있는지 확인하십시오. 이것은 O (1)가 아니라 O (n)입니다.

요소가 컬렉션에 추가 될 때 구현이 내부적으로 조회 테이블을 생성합니까?

일반적으로 .NET 데이터 구조의 복잡성에 대한 정보를 어떻게 확인할 수 있습니까?

출처

2012-03-21 Kirby

다양한 입력 크기로 테스트하고 조회 시간이 일정하게 유지되는지 확인하십시오. 그러나 설명서가 맞는지 확실히 확인하십시오. –

생성자가 끝나면 여전히 * HashSet입니다. 원본 데이터 구조 자체는 유지되지 않습니다 (예 :이 경우 '프록시'가 없음). 조회는 O (1)이지만 삽입은 * amortized * O (1)입니다. –

@Kirby 변경되지 않습니다. IEnumerable에서 HashSet을 구성하거나 나중에 개별적으로 요소를 추가 할 수 있습니다. [lookup] 시간 복잡도에 영향을 미치지 않는 * 다를 수도있는 유일한 것은 용량입니다. –

HashSet은 해시를 통해 (IEqualityComparer.GetHashCode을 통해) 삽입 한 개체를 작동하고 해시 당 버킷으로 개체를 보냅니다. 버킷 자체는 배열에 저장되므로 O (1) 부분에 저장됩니다.

예를 들어 해시의 첫 번째 문자를 가져 와서 1로 시작하는 해시가 버킷 1에 모두 버립니다. 해시 2 개, 버킷 1 개 2, 등등. 그 양동이 안에는 해시의 두 번째 문자로 나뉘어 진 버킷 배열이 있습니다. 해시의 모든 캐릭터에 대해 이렇게 ....

이제 무언가를 살펴보면 해시가 적절 해지고 적절한 버켓을 통해 이동합니다. 여러 개의 배열 조회 (해시의 각 문자에 대해 하나씩)를 수행해야하지만 추가 한 객체의 수인 N의 함수로 증가하지 않으므로 O (1) 등급이됩니다. 다른 질문에

가 여기 컬렉션 '작업의 수의 복잡성과 블로그 게시물 : 그것은 것 해시 함수의 품질에 따라 달라집니다 http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

출처

2012-03-21 20:08:37

나는 충돌이 발생할 때 버킷에 해싱이 발생한다고 생각합니다. – sll

@sll 양동이에 해싱이 항상 발생합니다. 충돌이 없다면 버킷은 하나의 항목을 보유합니다. – phoog

고맙습니다, 스캇. 어떤 이유로, 귀하의 설명은 "IEqualityComparer.GetHashCode."라는 호출과 관련하여 매우 명확했습니다. 지금은 많은 의미가 있습니다. – Kirby

(GetHashCode()는) 당신의 IEqualityComparer 구현을 제공합니다. 이상적인 해시 함수는 잘 분산 된 해시 코드 집합을 제공해야합니다. 이러한 해시 코드는 키를 값에 매핑 할 수있는 인덱스로 사용되므로 특히 키가 복잡한 객체/구조 인 경우 키를 기준으로 값을 검색하는 것이 더 효율적입니다.

일치가 있는지 확인하려면 모든 키에서 Comparer 코드를 실행해야합니다. 이것은 O (1)가 아니라 O (n)입니다.

이것은 해시 테이블이 작동하는 방식이 아니라 일종의 간단한 bruteforce 검색입니다. 해시 테이블의 경우 인덱스 (해시 코드)로 검색하는보다 지능적인 접근 방식을 사용하게됩니다.

출처

2012-03-21 20:08:57 sll

OP는'HashSet '이 아니라'HashSet '에 대해 질문하고 있습니다 (구현 세부 사항은 약간 다릅니다). – phoog

그 점에 유의 해 주셔서 감사합니다. 확실하지는 않지만 확실한 것을 만들고 싶습니다. 이것은 [MSDN] (http://msdn.microsoft.com/en-us/library/bb397727.aspx)에서 찾은 것입니다. :'The HashSet (Of T) 클래스는 수학 집합 모델을 기반으로하며 Dictionary (Of TKey, TValue) 또는 Hashtable 컬렉션의 키에 액세스하는 것과 비슷한 고성능 집합 연산을 제공합니다. 간단히 말해 HashSet (Of T) 클래스는 값없이 Dictionary (Of TKey, TValue) 컬렉션으로 간주 될 수 있습니다. ' – sll

사실입니다. 'HashSet '와 'Dictionary '는 실제로 같은 내부 클래스를 사용하여 코어 로직을 처리합니다. 비 제네릭 Hashtable은 다른 구현을 사용하지만 성능 특성은 비슷합니다. 해시 함수의 중요성에 대한 설명은 두 가지 모두에 적용됩니다 (나는 언급하지 않았습니다). 그래서 +1. – phoog

IEqualityComparer를 전달하면 조회가 여전히 O (1)입니다.해시 세트는 여전히 동일한 논리를 사용합니다. 은이 아닌 경우 IEqualityComparer를 전달합니다. 단지 System.Object의 인스턴스 메서드 (또는 해당 개체가 제공하는 재정의) 대신 IEqualityComparer의 GetHashCode 및 Equals 구현을 사용합니다.

출처

2012-03-21 20:13:18 phoog

내가 조회를 수행 할 때마다 Comparer을 작성하여 HashSet의 생성자에 전달하면 Comparer 코드가 일치하는지 확인하기 위해 모든 키에서 실행해야합니다. 이것은 O (1)가 아니라 O (n)입니다.

"쿼리"값을 검색하는 값을 호출 해 봅시다.

모든 키에서 비교자를 실행하여 쿼리와 일치하는지 확인하는 이유를 설명 할 수 있습니까?

이 신념은 거짓입니다. 물론 비교 자에 의해 제공된 해시 코드는 모든 키에 대해 동일하지 않습니다. 검색 알고리즘은 해시 코드이 해시 테이블의 버킷 수를 모듈의 쿼리 해시 코드와 일치시키는 모든 키 에 대해 동등 비교자를 실행합니다. 이것이 해시 테이블에서 O (1) 조회 시간을 얻는 방법입니다.

요소가 컬렉션에 추가 될 때 구현이 내부적으로 조회 테이블을 구성합니까?

예.

일반적으로 .NET 데이터 구조의 복잡성에 대한 정보를 어떻게 확인할 수 있습니까?

설명서를 읽으십시오.

출처

2012-03-21 20:26:02

"문서 읽기 "를 확장하기 위해 문서가 약간 희미합니다. 대부분의 프레임 워크 어셈블리의 경우 Microsoft가 [Reference Source Program] (http://referencesource.microsoft.com/)을 통해 제공하는 소스 코드 (!)를 읽을 수 있습니다. 물론 문서화되지 않은 사항은 잠재적으로 변경 될 수 있지만 대부분 변경 될 가능성이없는 사실을 결정할 수 있습니다. –

"비교 자에 의해 제공된 해시 코드가 모든 키에 대해 동일하지 않으면!".. 그래서 같은 해시 코드 값이 반환되고 항목이 해시 집합 컬렉션에 추가 관리되면 어떻게됩니까? – user384080

@ user384080 : 명시된 믿음은 사실입니다. 그 문장에서 "없다"는 것을 의미합니다. –

HashSet <T> (IEqualityComparer <T>)의 조회 시간 복잡도는 얼마입니까?

답변

관련 문제