정확히 동일한 내용을 가진 사전의 주문입니까?

Question

내가 사전의 순서가 정의되지 않은 것을 알고, MSDN 이렇게 말한다 :

열거의 목적

은, 사전에 각 항목의 값과 키를 나타내는 KeyValuePair 구조로 처리됩니다. 항목이 반환되는 순서는 정의되지 않습니다.

그래도 괜찮 으면 좋겠지 만 동일한 콘텐츠가 포함 된 두 개의 사전 인스턴스가있는 경우 순서는 동일합니까?

내가 이해할 수있는 것처럼 키의 해시에 의해 순서가 결정되고 두 개의 사전에 동일한 키가 있으면 동일한 해시가 있으므로 같은 순서가됩니다.

... 오른쪽?

감사합니다.

앤디.

Answer 1

아니요 동일한 주문이되는 것이 보장되지 않습니다. 동일한 해시 코드를 사용하여 Dictionary<TKey, TValue>에 여러 항목이있는 시나리오를 생각해보십시오. 서로 다른 순서로 두 개의 사전에 추가되면 열거 형의 순서가 달라집니다. MSDN은 당신이에 의존해야 그 정의를 말한다면

예를 들어 다음 (준수 평등) 코드를 고려

class Example 
{ 
    public char Value; 
    public override int GetHashCode() 
    { 
     return 1; 
    } 
    public override bool Equals(object obj) 
    { 
     return obj is Example && ((Example)obj).Value == Value; 
    } 
    public override string ToString() 
    { 
     return Value.ToString(); 
    } 
} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     var e1 = new Example() { Value = 'a' }; 
     var e2 = new Example() { Value = 'b' }; 
     var map1 = new Dictionary<Example, string>(); 
     map1.Add(e1, "1"); 
     map1.Add(e2, "2"); 

     var map2 = new Dictionary<Example, string>(); 
     map2.Add(e2, "2"); 
     map2.Add(e1, "1"); 

     Console.WriteLine(map1.Values.Aggregate((x, y) => x + y)); 
     Console.WriteLine(map2.Values.Aggregate((x, y) => x + y)); 
    } 
} 

이 프로그램을 실행의 출력은

12 
21 

Answer 2

Microsoft 구현의 세부 사항을 모르지만 일반적으로 동일한 값으로 해시하는 항목이 사전에 없거나 충돌하는 항목이 같은 순서로 추가되는 경우에만 가정이 유지됩니다 .

Answer 3

입니다. 정의되지 않은 것은 사전의 구현이 원하는 순서대로 저장할 수 있다는 것을 의미합니다. 즉, 프로그래머는 순서에 대해 어떠한 가정도해서는 안됩니다. 사전에있는 요소들의 순서가 그들이 들어간 순서에 달려 있다고 생각하지 않고 개인적으로 생각 하겠지만 틀릴 수도 있습니다. 대답이 무엇이든간에 당신이 어떤 행동을 원한다면 두 가지 모두에 대해 순서가 동일하므로 잘못된 행동을하는 것입니다.

Answer 4

"두 사전이 같은 키가있는 경우, 그들이 동일한 해시를 가지고 있고, 때문에 같은 순서로 ..."나는이 경우 생각하지 않는다

. 비록 그것이 사실 일지라도, 나는 이것에 의지하지 않을 것입니다. 그것이 사실이라면 그것은 구현 세부 사항입니다. CLR 또는 BCL의 다른 구현에 따라 달라 지거나 다를 수 있습니다 (단점).

Microsoft 사전 구현은 다소 복잡하지만 코드를 5 분간 보면서 열거 순서가 에 기초 할 것이라고 추측합니다. 사전이 그 상태로되어 있습니다. 크기 조정 및 게재 신청서 수

Answer 5

짧은 버전 : 아니요.

긴 버전 :

[TestMethod] 
    public void TestDictionary() 
    { 
     Dictionary<String, Int32> d1 = new Dictionary<string, int>(); 
     Dictionary<String, Int32> d2 = new Dictionary<string, int>(); 

     d1.Add("555", 1); 
     d1.Add("abc2", 2); 
     d1.Add("abc3", 3); 
     d1.Remove("abc2"); 
     d1.Add("abc2", 2); 
     d1.Add("556", 1); 

     d2.Add("555", 1); 
     d2.Add("556", 1); 
     d2.Add("abc2", 2); 
     d2.Add("abc3", 3); 

     foreach (var i in d1) 
     { 
      Console.WriteLine(i); 
     } 
     Console.WriteLine(); 
     foreach (var i in d2) 
     { 
      Console.WriteLine(i); 
     } 
    } 

출력 : 사양은 순서가 "정의되지 않은"말한다

[555, 1] 
[abc2, 2] 
[abc3, 3] 
[556, 1] 

[555, 1] 
[556, 1] 
[abc2, 2] 
[abc3, 3] 

Answer 6

경우, 당신은 명시 적으로 주문하지 않고 순서에 의존 할 수 없다. 기본 구현은 새로운 릴리스 또는 서비스 팩을 사용하여 언제든지 변경 될 수 있습니다. 사전은 임의의 수의 구체적인 구현에서도 상영 될 수 있습니다.

기본 구현은 적용된 작업 순서에 민감 할 수 있습니다. 키 'a', 'b'및 'c'를이 순서대로 추가하면 다른 순서로 동일한 키 세트를 추가하는 것과는 다른 데이터 구조가 생길 수 있습니다 (예 : 'b', 'c'및 'a'). 삭제는 마찬가지로 데이터 구조에 영향을 줄 수 있습니다.

예를 들어 사전 뒤에있는 데이터 구조로 사용되는 경우, 키가 순서대로 추가되는 경우 순수 결과는 본질적으로 링크 된 목록 인 고도로 불균형 한 트리입니다. 노드가 임의의 순서로 삽입되면 트리의 균형이 더 높아집니다.

그리고 일부 데이터 구조가 조작으로 수행됩니다. 예를 들어 사전이 기본 데이터 구조가 빨간색/검은 색 트리로 구현 된 경우 삽입 및 삭제가 발생할 때 트리를 균형있게 유지하기 위해 트리 노드가 분할/회전됩니다. 따라서 실제 데이터 구조는 최종 내용이 동일하더라도 작업 순서에 크게 의존합니다.