asp.net : 사전 상수 시간 또는 log2 (n) 키로 값을 검색하는 시간 복잡?

Question

dotnet에서 datastructure가 필요합니다. 일정한 시간 내에 항목을 검색 할 수 있습니다. 즉, 데이터 구조가 내부적으로 색인 생성을 구현해야 함을 의미합니다.이 목적이나 다른 유용한 정보일까요?

Answer 1

예, 사전 < (또는 이전 버전의 .NET을 사용하는 경우 Hashtable)을 사용하십시오. 사전에 채우고있는 객체가 좋은 해시 값을 가지고 있는지 확인하십시오 (사전의 키로 사용중인 객체에 대해 GetHashCode() 및 Equals()를 재정의하십시오). 데이터 객체의 해시 코드 성능이 좋지 않은 경우 성능이 저하되기 시작합니다. 그리고 예, 귀하의 질문에 대답하기 위해, 해시 테이블/UPS는 상대적으로 일정한 시간 (책은 일반적으로 그것이 O (1)이라고 말하지만, 논쟁의 여지가 있음)에서 ups를 찾습니다. 룩업 성능은 여러 가지 요인에 의해 결정됩니다

1. 해시 기능 (결정 유통)
2. 어떻게 테이블 핸들 충돌을합니까? 프로빙? 양동이? (대부분의 구현에서는 버킷을 사용합니다).
3. 테이블 크기를 조정할 수 있습니까? 크기는 어떻게 조정됩니까? 작은 증분? 2의 힘? 소수?
4. 등 ...