.NET 사전에 항목이 추가 된 이유는 무엇입니까?

StackOverflow https://stackoverflow.com/questions/154307

문제

방금이 행동을 보았고 나는 그것에 약간 놀랐습니다 ...

사전에 3 개 또는 4 개의 요소를 추가 한 다음 모든 키를 얻기 위해 "각각"에 대해 "각각"을 수행하면 추가 한 순서로 표시됩니다.

이것이 나를 놀라게하는 이유는 사전이 내부적으로 해시 가능해야하기 때문입니다. 그래서 나는 어떤 순서로든 나올 것으로 예상했습니다 (열쇠의 해시에 의해 순서대로).

내가 여기서 무엇을 놓치고 있습니까? 이것이 내가 믿을 수있는 행동입니까?

편집 : 좋아, 나는 이미 많은 이유를 생각했다. ~할 것 같다 일치에 관계없이 항목에 대한 별도의 목록과 같은 일치 등). 내 질문은, 누구든지입니다 알다 이것이 실제로 어떻게 작동합니까?

도움이 되었습니까?

해결책

3.5 클래스 라이브러리에서 .NET 리플렉터를 사용하는 경우 사전 구현이 실제로 항목을 배열에 저장하고 (필요에 따라 크기를 조정 함) 해시 색인을 해당 배열에 저장하고 있음을 알 수 있습니다. 키를 얻을 때 해시 가능을 완전히 무시하고 항목 배열을 반복합니다. 이러한 이유로, 배열 끝에 새 항목이 추가되기 때문에 설명한 동작이 표시됩니다. 다음을 수행하는 경우처럼 보입니다.

add 1
add 2
add 3
add 4
remove 2
add 5

빈 슬롯을 재사용하기 때문에 1 5 3 4로 돌아갑니다.

다른 많은 사람들과 마찬가지로 앞으로 (또는 과거) 릴리스 에서이 행동을 믿을 수는 없습니다. 사전을 정렬하기를 원한다면 SortedDictionary 이 목적을위한 수업.

다른 팁

사전은 해시 순서로 품목을 검색합니다. 그들이 삽입 순서로 나왔다는 사실은 완전히 우연의 일치였습니다.

MSDN 문서는 다음과 같습니다.

키 수집에서 키의 순서는 지정되지 않지만 값 속성에 의해 반환 된 valuecollection의 관련 값과 동일한 순서입니다.

이 행동을 믿을 수는 없지만 놀라운 것은 아닙니다.

간단한 해시 테이블의 키 반복을 구현하는 방법을 고려하십시오. 당신은 모든 해시 버킷을 반복해야 할 것입니다. 큰 해시 테이블에서 작은 데이터 세트를 얻는 것은 비효율적 일 수 있습니다.

따라서 별도의 중복 키 목록을 유지하는 것이 좋은 최적화 일 수 있습니다. 이중 연결 목록을 사용하면 여전히 일정한 시간 삽입/삭제가 발생합니다. (해시 테이블 버킷 에서이 목록으로 다시 포인터를 유지합니다.) 키 목록을 통해 반복하는 것은 버킷 수가 아닌 항목 수에만 의존합니다.

나는 이것이 두 종류의 사전 "ListDictionary"와 "HybridDictionary"를 가진 오래된 .NET 1.1 번에서 나온다고 생각합니다. ListDictionary 내부적으로 주문 목록으로 구현 된 사전이었으며 "작은 항목 세트"에 권장되었습니다. 그럼 당신은 가지고있었습니다 하이브리드 소설, 그것은 처음에는 내부적으로 목록으로 구성되었지만 구성 가능한 임계 값보다 커지면 해시 테이블이됩니다. 이것은 역사적으로 적절한 해시 기반 사전이 비싼 것으로 간주 되었기 때문에 이루어졌습니다. 이제는 의미가없는 날이지만, .NET은 기존 하이브리드 디터크의 새로운 사전 일반 클래스를 기반으로합니다.

메모: 어쨌든, 다른 사람이 이미 지적했듯이 절대 무엇이든 사전 순서를 의지합니다

인용문 MSDN :

사전 <(<(tkey, tvalue>)>)의 키의 순서는 지정되지 않지만 사전 <(<(tkey, tvalue>)>)의 관련 값과 동일한 순서입니다. .valuecollection 사전 <(<(tkey, tvalue>)>)에 의해 반환됩니다. 값 특성.

테스트에서 어떤 키를 추가했으며 어떤 순서로 추가 했습니까?

당신의 항목은 모두 사전에서 같은 해시 버킷에있을 수 있습니다. 각 버킷은 아마도 버킷의 항목 목록 일 것입니다. 이것은 순서대로 돌아 오는 항목을 설명합니다.

내가 아는 바에 따르면 이것이 의존하는 행동이되어서는 안됩니다. 동일한 요소를 빠르게 사용하고 사전에 추가하는 순서를 변경하려면 사전에 추가하십시오. 추가 된 순서대로 되돌릴 수 있는지 또는 우연의 일치 일뿐입니다.

특정 목록 크기까지 해싱 대신 모든 항목 만 확인하는 것이 저렴합니다. 그것은 아마도 일어나고있는 일일 것입니다.

100 또는 1000 항목을 추가하고 여전히 같은 순서인지 확인하십시오.

나는 이런 종류의 "디자인"기능을 싫어합니다. 나는 당신의 수업에 "사전"과 같은 일반적인 이름을 줄 때 "일반적으로 예상대로"행동해야한다고 생각합니다. 예를 들어 std :: map은 항상 키 값을 정렬합니다.

편집 : 분명히 해결책은 std :: map과 유사하게 작동하는 SortedDictionary를 사용하는 것입니다.

질문과 많은 답변은 해시 가능 또는 사전의 목적을 오해하는 것 같습니다. 이러한 데이터 구조에는 데이터 구조에 포함 된 항목의 값 (또는 실제로 키)의 열거와 관련하여 지정된 동작이 없습니다.

사전 또는 해시 테이블의 목적은 알려진 키가 주어진 특정 값을 효율적으로 조회 할 수 있어야합니다. 사전 또는 해시 가능의 내부 구현은 이러한 조회의 효율성을 제공해야하지만 열거와 관련하여 또는 값 또는 키에 대한 "각각의"유형 반복과 관련하여 특정 동작을 제공 할 필요는 없습니다.

요컨대, 내부 데이터 구조는 삽입 된 순서를 포함하여 원하는 방식으로 이러한 값을 저장하고 열거 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top