src/mscorlib/shared/System/Collections/Generic/Dictionary.cs

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 using System;
   6 using System.Collections;
   7 using System.Diagnostics;
   8 using System.Runtime.CompilerServices;
   9 using System.Runtime.Serialization;
  10
  11 namespace System.Collections.Generic
  12 {
  13     /// <summary>
  14     /// Used internally to control behavior of insertion into a <see cref="Dictionary{TKey, TValue}"/>.
  15     /// </summary>
  16     internal enum InsertionBehavior : byte
  17     {
  18         /// <summary>
  19         /// The default insertion behavior.
  20         /// </summary>
  21         None = 0,
  22
  23         /// <summary>
  24         /// Specifies that an existing entry with the same key should be overwritten if encountered.
  25         /// </summary>
  26         OverwriteExisting = 1,
  27
  28         /// <summary>
  29         /// Specifies that if an existing entry with the same key is encountered, an exception should be thrown.
  30         /// </summary>
  31         ThrowOnExisting = 2
  32     }
  33
  34     [DebuggerTypeProxy(typeof(IDictionaryDebugView<,>))]
  35     [DebuggerDisplay("Count = {Count}")]
  36     [Serializable]
  37     [System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
  38     public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback
  39     {
  40         private struct Entry
  41         {
  42             public int hashCode;    // Lower 31 bits of hash code, -1 if unused
  43             public int next;        // Index of next entry, -1 if last
  44             public TKey key;           // Key of entry
  45             public TValue value;         // Value of entry
  46         }
  47
  48         private int[] _buckets;
  49         private Entry[] _entries;
  50         private int _count;
  51         private int _freeList;
  52         private int _freeCount;
  53         private int _version;
  54         private IEqualityComparer<TKey> _comparer;
  55         private KeyCollection _keys;
  56         private ValueCollection _values;
  57         private object _syncRoot;
  58
  59         // constants for serialization
  60         private const string VersionName = "Version"; // Do not rename (binary serialization)
  61         private const string HashSizeName = "HashSize"; // Do not rename (binary serialization). Must save buckets.Length
  62         private const string KeyValuePairsName = "KeyValuePairs"; // Do not rename (binary serialization)
  63         private const string ComparerName = "Comparer"; // Do not rename (binary serialization)
  64
  65         public Dictionary() : this(0, null) { }
  66
  67         public Dictionary(int capacity) : this(capacity, null) { }
  68
  69         public Dictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) { }
  70
  71         public Dictionary(int capacity, IEqualityComparer<TKey> comparer)
  72         {
  73             if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
  74             if (capacity > 0) Initialize(capacity);
  75             if (comparer != EqualityComparer<TKey>.Default)
  76             {
  77                 _comparer = comparer;
  78             }
  79
  80             if (typeof(TKey) == typeof(string) && _comparer == null)
  81             {
  82                 // To start, move off default comparer for string which is randomised
  83                 _comparer = (IEqualityComparer<TKey>)NonRandomizedStringEqualityComparer.Default;
  84             }
  85         }
  86
  87         public Dictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { }
  88
  89         public Dictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) :
  90             this(dictionary != null ? dictionary.Count : 0, comparer)
  91         {
  92             if (dictionary == null)
  93             {
  94                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
  95             }
  96
  97             // It is likely that the passed-in dictionary is Dictionary<TKey,TValue>. When this is the case,
  98             // avoid the enumerator allocation and overhead by looping through the entries array directly.
  99             // We only do this when dictionary is Dictionary<TKey,TValue> and not a subclass, to maintain
 100             // back-compat with subclasses that may have overridden the enumerator behavior.
 101             if (dictionary.GetType() == typeof(Dictionary<TKey, TValue>))
 102             {
 103                 Dictionary<TKey, TValue> d = (Dictionary<TKey, TValue>)dictionary;
 104                 int count = d._count;
 105                 Entry[] entries = d._entries;
 106                 for (int i = 0; i < count; i++)
 107                 {
 108                     if (entries[i].hashCode >= 0)
 109                     {
 110                         Add(entries[i].key, entries[i].value);
 111                     }
 112                 }
 113                 return;
 114             }
 115
 116             foreach (KeyValuePair<TKey, TValue> pair in dictionary)
 117             {
 118                 Add(pair.Key, pair.Value);
 119             }
 120         }
 121
 122         public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection) : this(collection, null) { }
 123
 124         public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) :
 125             this((collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? 0, comparer)
 126         {
 127             if (collection == null)
 128             {
 129                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
 130             }
 131
 132             foreach (KeyValuePair<TKey, TValue> pair in collection)
 133             {
 134                 Add(pair.Key, pair.Value);
 135             }
 136         }
 137
 138         protected Dictionary(SerializationInfo info, StreamingContext context)
 139         {
 140             // We can't do anything with the keys and values until the entire graph has been deserialized
 141             // and we have a resonable estimate that GetHashCode is not going to fail.  For the time being,
 142             // we'll just cache this.  The graph is not valid until OnDeserialization has been called.
 143             HashHelpers.SerializationInfoTable.Add(this, info);
 144         }
 145
 146         public IEqualityComparer<TKey> Comparer
 147         {
 148             get
 149             {
 150                 return (_comparer == null || _comparer is NonRandomizedStringEqualityComparer) ? EqualityComparer<TKey>.Default : _comparer;
 151             }
 152         }
 153
 154         public int Count
 155         {
 156             get { return _count - _freeCount; }
 157         }
 158
 159         public KeyCollection Keys
 160         {
 161             get
 162             {
 163                 if (_keys == null) _keys = new KeyCollection(this);
 164                 return _keys;
 165             }
 166         }
 167
 168         ICollection<TKey> IDictionary<TKey, TValue>.Keys
 169         {
 170             get
 171             {
 172                 if (_keys == null) _keys = new KeyCollection(this);
 173                 return _keys;
 174             }
 175         }
 176
 177         IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys
 178         {
 179             get
 180             {
 181                 if (_keys == null) _keys = new KeyCollection(this);
 182                 return _keys;
 183             }
 184         }
 185
 186         public ValueCollection Values
 187         {
 188             get
 189             {
 190                 if (_values == null) _values = new ValueCollection(this);
 191                 return _values;
 192             }
 193         }
 194
 195         ICollection<TValue> IDictionary<TKey, TValue>.Values
 196         {
 197             get
 198             {
 199                 if (_values == null) _values = new ValueCollection(this);
 200                 return _values;
 201             }
 202         }
 203
 204         IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values
 205         {
 206             get
 207             {
 208                 if (_values == null) _values = new ValueCollection(this);
 209                 return _values;
 210             }
 211         }
 212
 213         public TValue this[TKey key]
 214         {
 215             get
 216             {
 217                 int i = FindEntry(key);
 218                 if (i >= 0) return _entries[i].value;
 219                 ThrowHelper.ThrowKeyNotFoundException(key);
 220                 return default(TValue);
 221             }
 222             set
 223             {
 224                 bool modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting);
 225                 Debug.Assert(modified);
 226             }
 227         }
 228
 229         public void Add(TKey key, TValue value)
 230         {
 231             bool modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting);
 232             Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown.
 233         }
 234
 235         void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair)
 236         {
 237             Add(keyValuePair.Key, keyValuePair.Value);
 238         }
 239
 240         bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair)
 241         {
 242             int i = FindEntry(keyValuePair.Key);
 243             if (i >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[i].value, keyValuePair.Value))
 244             {
 245                 return true;
 246             }
 247             return false;
 248         }
 249
 250         bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair)
 251         {
 252             int i = FindEntry(keyValuePair.Key);
 253             if (i >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[i].value, keyValuePair.Value))
 254             {
 255                 Remove(keyValuePair.Key);
 256                 return true;
 257             }
 258             return false;
 259         }
 260
 261         public void Clear()
 262         {
 263             int count = _count;
 264             if (count > 0)
 265             {
 266                 Array.Clear(_buckets, 0, _buckets.Length);
 267
 268                 _count = 0;
 269                 _freeList = -1;
 270                 _freeCount = 0;
 271                 _version++;
 272                 Array.Clear(_entries, 0, count);
 273             }
 274         }
 275
 276         public bool ContainsKey(TKey key)
 277         {
 278             return FindEntry(key) >= 0;
 279         }
 280
 281         public bool ContainsValue(TValue value)
 282         {
 283             if (value == null)
 284             {
 285                 for (int i = 0; i < _count; i++)
 286                 {
 287                     if (_entries[i].hashCode >= 0 && _entries[i].value == null) return true;
 288                 }
 289             }
 290             else
 291             {
 292                 for (int i = 0; i < _count; i++)
 293                 {
 294                     if (_entries[i].hashCode >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[i].value, value)) return true;
 295                 }
 296             }
 297             return false;
 298         }
 299
 300         private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
 301         {
 302             if (array == null)
 303             {
 304                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 305             }
 306
 307             if (index < 0 || index > array.Length)
 308             {
 309                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
 310             }
 311
 312             if (array.Length - index < Count)
 313             {
 314                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
 315             }
 316
 317             int count = _count;
 318             Entry[] entries = _entries;
 319             for (int i = 0; i < count; i++)
 320             {
 321                 if (entries[i].hashCode >= 0)
 322                 {
 323                     array[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
 324                 }
 325             }
 326         }
 327
 328         public Enumerator GetEnumerator()
 329         {
 330             return new Enumerator(this, Enumerator.KeyValuePair);
 331         }
 332
 333         IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
 334         {
 335             return new Enumerator(this, Enumerator.KeyValuePair);
 336         }
 337
 338         public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
 339         {
 340             if (info == null)
 341             {
 342                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info);
 343             }
 344
 345             info.AddValue(VersionName, _version);
 346             info.AddValue(ComparerName, _comparer ?? EqualityComparer<TKey>.Default, typeof(IEqualityComparer<TKey>));
 347             info.AddValue(HashSizeName, _buckets == null ? 0 : _buckets.Length); // This is the length of the bucket array
 348
 349             if (_buckets != null)
 350             {
 351                 var array = new KeyValuePair<TKey, TValue>[Count];
 352                 CopyTo(array, 0);
 353                 info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair<TKey, TValue>[]));
 354             }
 355         }
 356
 357         private int FindEntry(TKey key)
 358         {
 359             if (key == null)
 360             {
 361                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 362             }
 363
 364             int i = -1;
 365             int[] buckets = _buckets;
 366             Entry[] entries = _entries;
 367             if (buckets != null)
 368             {
 369                 IEqualityComparer<TKey> comparer = _comparer;
 370                 if (comparer == null)
 371                 {
 372                     int hashCode = key.GetHashCode() & 0x7FFFFFFF;
 373                     // Value in _buckets is 1-based
 374                     i = buckets[hashCode % buckets.Length] - 1;
 375                     do
 376                     {
 377                         // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
 378                         // Test in if to drop range check for following array access
 379                         if ((uint)i >= (uint)entries.Length || (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key)))
 380                         {
 381                             break;
 382                         }
 383
 384                         i = entries[i].next;
 385                     } while (true);
 386                 }
 387                 else
 388                 {
 389                     int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
 390                     // Value in _buckets is 1-based
 391                     i = buckets[hashCode % buckets.Length] - 1;
 392                     do
 393                     {
 394                         // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
 395                         // Test in if to drop range check for following array access
 396                         if ((uint)i >= (uint)entries.Length ||
 397                             (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)))
 398                         {
 399                             break;
 400                         }
 401
 402                         i = entries[i].next;
 403                     } while (true);
 404                 }
 405             }
 406
 407             return i;
 408         }
 409
 410         private int Initialize(int capacity)
 411         {
 412             int size = HashHelpers.GetPrime(capacity);
 413
 414             _freeList = -1;
 415             _buckets = new int[size];
 416             _entries = new Entry[size];
 417
 418             return size;
 419         }
 420
 421         private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
 422         {
 423             if (key == null)
 424             {
 425                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 426             }
 427
 428             if (_buckets == null)
 429             {
 430                 Initialize(0);
 431             }
 432
 433             Entry[] entries = _entries;
 434             IEqualityComparer<TKey> comparer = _comparer;
 435
 436             int hashCode = ((comparer == null) ? key.GetHashCode() : comparer.GetHashCode(key)) & 0x7FFFFFFF;
 437
 438             int collisionCount = 0;
 439             ref int bucket = ref _buckets[hashCode % _buckets.Length];
 440             // Value in _buckets is 1-based
 441             int i = bucket - 1;
 442
 443             if (comparer == null)
 444             {
 445                 do
 446                 {
 447                     // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
 448                     // Test uint in if rather than loop condition to drop range check for following array access
 449                     if ((uint)i >= (uint)entries.Length)
 450                     {
 451                         break;
 452                     }
 453
 454                     if (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key))
 455                     {
 456                         if (behavior == InsertionBehavior.OverwriteExisting)
 457                         {
 458                             entries[i].value = value;
 459                             _version++;
 460                             return true;
 461                         }
 462
 463                         if (behavior == InsertionBehavior.ThrowOnExisting)
 464                         {
 465                             ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
 466                         }
 467
 468                         return false;
 469                     }
 470
 471                     i = entries[i].next;
 472                     collisionCount++;
 473                 } while (true);
 474             }
 475             else
 476             {
 477                 do
 478                 {
 479                     // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
 480                     // Test uint in if rather than loop condition to drop range check for following array access
 481                     if ((uint)i >= (uint)entries.Length)
 482                     {
 483                         break;
 484                     }
 485
 486                     if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
 487                     {
 488                         if (behavior == InsertionBehavior.OverwriteExisting)
 489                         {
 490                             entries[i].value = value;
 491                             _version++;
 492                             return true;
 493                         }
 494
 495                         if (behavior == InsertionBehavior.ThrowOnExisting)
 496                         {
 497                             ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
 498                         }
 499
 500                         return false;
 501                     }
 502
 503                     i = entries[i].next;
 504                     collisionCount++;
 505                 } while (true);
 506
 507             }
 508
 509             // Can be improved with "Ref Local Reassignment"
 510             // https://github.com/dotnet/csharplang/blob/master/proposals/ref-local-reassignment.md
 511             bool resized = false;
 512             bool updateFreeList = false;
 513             int index;
 514             if (_freeCount > 0)
 515             {
 516                 index = _freeList;
 517                 updateFreeList = true;
 518                 _freeCount--;
 519             }
 520             else
 521             {
 522                 int count = _count;
 523                 if (count == entries.Length)
 524                 {
 525                     Resize();
 526                     resized = true;
 527                 }
 528                 index = count;
 529                 _count = count + 1;
 530                 entries = _entries;
 531             }
 532
 533             ref int targetBucket = ref resized ? ref _buckets[hashCode % _buckets.Length] : ref bucket;
 534             ref Entry entry = ref entries[index];
 535
 536             if (updateFreeList)
 537             {
 538                 _freeList = entry.next;
 539             }
 540             entry.hashCode = hashCode;
 541             // Value in _buckets is 1-based
 542             entry.next = targetBucket - 1;
 543             entry.key = key;
 544             entry.value = value;
 545             // Value in _buckets is 1-based
 546             targetBucket = index + 1;
 547             _version++;
 548
 549             // Value types never rehash
 550             if (default(TKey) == null && collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer)
 551             {
 552                 // If we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
 553                 // i.e. EqualityComparer<string>.Default.
 554                 _comparer = null;
 555                 Resize(entries.Length, true);
 556             }
 557
 558             return true;
 559         }
 560
 561         public virtual void OnDeserialization(object sender)
 562         {
 563             SerializationInfo siInfo;
 564             HashHelpers.SerializationInfoTable.TryGetValue(this, out siInfo);
 565
 566             if (siInfo == null)
 567             {
 568                 // We can return immediately if this function is called twice.
 569                 // Note we remove the serialization info from the table at the end of this method.
 570                 return;
 571             }
 572
 573             int realVersion = siInfo.GetInt32(VersionName);
 574             int hashsize = siInfo.GetInt32(HashSizeName);
 575             _comparer = (IEqualityComparer<TKey>)siInfo.GetValue(ComparerName, typeof(IEqualityComparer<TKey>));
 576
 577             if (hashsize != 0)
 578             {
 579                 Initialize(hashsize);
 580
 581                 KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[])
 582                     siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[]));
 583
 584                 if (array == null)
 585                 {
 586                     ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys);
 587                 }
 588
 589                 for (int i = 0; i < array.Length; i++)
 590                 {
 591                     if (array[i].Key == null)
 592                     {
 593                         ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_NullKey);
 594                     }
 595                     Add(array[i].Key, array[i].Value);
 596                 }
 597             }
 598             else
 599             {
 600                 _buckets = null;
 601             }
 602
 603             _version = realVersion;
 604             HashHelpers.SerializationInfoTable.Remove(this);
 605         }
 606
 607         private void Resize()
 608         {
 609             Resize(HashHelpers.ExpandPrime(_count), false);
 610         }
 611
 612         private void Resize(int newSize, bool forceNewHashCodes)
 613         {
 614             // Value types never rehash
 615             Debug.Assert(!forceNewHashCodes || default(TKey) == null);
 616             Debug.Assert(newSize >= _entries.Length);
 617
 618             int[] buckets = new int[newSize];
 619             Entry[] entries = new Entry[newSize];
 620
 621             int count = _count;
 622             Array.Copy(_entries, 0, entries, 0, count);
 623
 624             if (default(TKey) == null && forceNewHashCodes)
 625             {
 626                 for (int i = 0; i < count; i++)
 627                 {
 628                     if (entries[i].hashCode >= 0)
 629                     {
 630                         Debug.Assert(_comparer == null);
 631                         entries[i].hashCode = (entries[i].key.GetHashCode() & 0x7FFFFFFF);
 632                     }
 633                 }
 634             }
 635
 636             for (int i = 0; i < count; i++)
 637             {
 638                 if (entries[i].hashCode >= 0)
 639                 {
 640                     int bucket = entries[i].hashCode % newSize;
 641                     // Value in _buckets is 1-based
 642                     entries[i].next = buckets[bucket] - 1;
 643                     // Value in _buckets is 1-based
 644                     buckets[bucket] = i + 1;
 645                 }
 646             }
 647
 648             _buckets = buckets;
 649             _entries = entries;
 650         }
 651
 652         // The overload Remove(TKey key, out TValue value) is a copy of this method with one additional
 653         // statement to copy the value for entry being removed into the output parameter.
 654         // Code has been intentionally duplicated for performance reasons.
 655         public bool Remove(TKey key)
 656         {
 657             if (key == null)
 658             {
 659                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 660             }
 661
 662             if (_buckets != null)
 663             {
 664                 int hashCode = (_comparer?.GetHashCode(key) ?? key.GetHashCode()) & 0x7FFFFFFF;
 665                 int bucket = hashCode % _buckets.Length;
 666                 int last = -1;
 667                 // Value in _buckets is 1-based
 668                 int i = _buckets[bucket] - 1;
 669                 while (i >= 0)
 670                 {
 671                     ref Entry entry = ref _entries[i];
 672
 673                     if (entry.hashCode == hashCode && (_comparer?.Equals(entry.key, key) ?? EqualityComparer<TKey>.Default.Equals(entry.key, key)))
 674                     {
 675                         if (last < 0)
 676                         {
 677                             // Value in _buckets is 1-based
 678                             _buckets[bucket] = entry.next + 1;
 679                         }
 680                         else
 681                         {
 682                             _entries[last].next = entry.next;
 683                         }
 684                         entry.hashCode = -1;
 685                         entry.next = _freeList;
 686
 687                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
 688                         {
 689                             entry.key = default(TKey);
 690                         }
 691                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
 692                         {
 693                             entry.value = default(TValue);
 694                         }
 695                         _freeList = i;
 696                         _freeCount++;
 697                         _version++;
 698                         return true;
 699                     }
 700
 701                     last = i;
 702                     i = entry.next;
 703                 }
 704             }
 705             return false;
 706         }
 707
 708         // This overload is a copy of the overload Remove(TKey key) with one additional
 709         // statement to copy the value for entry being removed into the output parameter.
 710         // Code has been intentionally duplicated for performance reasons.
 711         public bool Remove(TKey key, out TValue value)
 712         {
 713             if (key == null)
 714             {
 715                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 716             }
 717
 718             if (_buckets != null)
 719             {
 720                 int hashCode = (_comparer?.GetHashCode(key) ?? key.GetHashCode()) & 0x7FFFFFFF;
 721                 int bucket = hashCode % _buckets.Length;
 722                 int last = -1;
 723                 // Value in _buckets is 1-based
 724                 int i = _buckets[bucket] - 1;
 725                 while (i >= 0)
 726                 {
 727                     ref Entry entry = ref _entries[i];
 728
 729                     if (entry.hashCode == hashCode && (_comparer?.Equals(entry.key, key) ?? EqualityComparer<TKey>.Default.Equals(entry.key, key)))
 730                     {
 731                         if (last < 0)
 732                         {
 733                             // Value in _buckets is 1-based
 734                             _buckets[bucket] = entry.next + 1;
 735                         }
 736                         else
 737                         {
 738                             _entries[last].next = entry.next;
 739                         }
 740
 741                         value = entry.value;
 742
 743                         entry.hashCode = -1;
 744                         entry.next = _freeList;
 745
 746                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
 747                         {
 748                             entry.key = default(TKey);
 749                         }
 750                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
 751                         {
 752                             entry.value = default(TValue);
 753                         }
 754                         _freeList = i;
 755                         _freeCount++;
 756                         _version++;
 757                         return true;
 758                     }
 759
 760                     last = i;
 761                     i = entry.next;
 762                 }
 763             }
 764             value = default(TValue);
 765             return false;
 766         }
 767
 768         public bool TryGetValue(TKey key, out TValue value)
 769         {
 770             int i = FindEntry(key);
 771             if (i >= 0)
 772             {
 773                 value = _entries[i].value;
 774                 return true;
 775             }
 776             value = default(TValue);
 777             return false;
 778         }
 779
 780         public bool TryAdd(TKey key, TValue value) => TryInsert(key, value, InsertionBehavior.None);
 781
 782         bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
 783         {
 784             get { return false; }
 785         }
 786
 787         void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
 788         {
 789             CopyTo(array, index);
 790         }
 791
 792         void ICollection.CopyTo(Array array, int index)
 793         {
 794             if (array == null)
 795             {
 796                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 797             }
 798
 799             if (array.Rank != 1)
 800             {
 801                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
 802             }
 803
 804             if (array.GetLowerBound(0) != 0)
 805             {
 806                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
 807             }
 808
 809             if (index < 0 || index > array.Length)
 810             {
 811                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
 812             }
 813
 814             if (array.Length - index < Count)
 815             {
 816                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
 817             }
 818
 819             KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[];
 820             if (pairs != null)
 821             {
 822                 CopyTo(pairs, index);
 823             }
 824             else if (array is DictionaryEntry[])
 825             {
 826                 DictionaryEntry[] dictEntryArray = array as DictionaryEntry[];
 827                 Entry[] entries = _entries;
 828                 for (int i = 0; i < _count; i++)
 829                 {
 830                     if (entries[i].hashCode >= 0)
 831                     {
 832                         dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value);
 833                     }
 834                 }
 835             }
 836             else
 837             {
 838                 object[] objects = array as object[];
 839                 if (objects == null)
 840                 {
 841                     ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
 842                 }
 843
 844                 try
 845                 {
 846                     int count = _count;
 847                     Entry[] entries = _entries;
 848                     for (int i = 0; i < count; i++)
 849                     {
 850                         if (entries[i].hashCode >= 0)
 851                         {
 852                             objects[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
 853                         }
 854                     }
 855                 }
 856                 catch (ArrayTypeMismatchException)
 857                 {
 858                     ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
 859                 }
 860             }
 861         }
 862
 863         IEnumerator IEnumerable.GetEnumerator()
 864         {
 865             return new Enumerator(this, Enumerator.KeyValuePair);
 866         }
 867
 868         /// <summary>
 869         /// Ensures that the dictionary can hold up to 'capacity' entries without any further expansion of its backing storage
 870         /// </summary>
 871         public int EnsureCapacity(int capacity)
 872         {
 873             if (capacity < 0)
 874                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
 875             int currentCapacity = _entries == null ? 0 : _entries.Length;
 876             if (currentCapacity >= capacity)
 877                 return currentCapacity;
 878             if (_buckets == null)
 879                 return Initialize(capacity);
 880             int newSize = HashHelpers.GetPrime(capacity);
 881             Resize(newSize, forceNewHashCodes: false);
 882             return newSize;
 883         }
 884
 885         /// <summary>
 886         /// Sets the capacity of this dictionary to what it would be if it had been originally initialized with all its entries
 887         ///
 888         /// This method can be used to minimize the memory overhead
 889         /// once it is known that no new elements will be added.
 890         ///
 891         /// To allocate minimum size storage array, execute the following statements:
 892         ///
 893         /// dictionary.Clear();
 894         /// dictionary.TrimExcess();
 895         /// </summary>
 896         public void TrimExcess()
 897         {
 898             TrimExcess(Count);
 899         }
 900
 901         /// <summary>
 902         /// Sets the capacity of this dictionary to hold up 'capacity' entries without any further expansion of its backing storage
 903         ///
 904         /// This method can be used to minimize the memory overhead
 905         /// once it is known that no new elements will be added.
 906         /// </summary>
 907         public void TrimExcess(int capacity)
 908         {
 909             if (capacity < Count)
 910                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
 911             int newSize = HashHelpers.GetPrime(capacity);
 912
 913             Entry[] oldEntries = _entries;
 914             int currentCapacity = oldEntries == null ? 0 : oldEntries.Length;
 915             if (newSize >= currentCapacity)
 916                 return;
 917
 918             int oldCount = _count;
 919             Initialize(newSize);
 920             Entry[] entries = _entries;
 921             int[] buckets = _buckets;
 922             int count = 0;
 923             for (int i = 0; i < oldCount; i++)
 924             {
 925                 int hashCode = oldEntries[i].hashCode;
 926                 if (hashCode >= 0)
 927                 {
 928                     ref Entry entry = ref entries[count];
 929                     entry = oldEntries[i];
 930                     int bucket = hashCode % newSize;
 931                     // Value in _buckets is 1-based
 932                     entry.next = buckets[bucket] - 1;
 933                     // Value in _buckets is 1-based
 934                     buckets[bucket] = count + 1;
 935                     count++;
 936                 }
 937             }
 938             _count = count;
 939             _freeCount = 0;
 940         }
 941
 942         bool ICollection.IsSynchronized
 943         {
 944             get { return false; }
 945         }
 946
 947         object ICollection.SyncRoot
 948         {
 949             get
 950             {
 951                 if (_syncRoot == null)
 952                 {
 953                     System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
 954                 }
 955                 return _syncRoot;
 956             }
 957         }
 958
 959         bool IDictionary.IsFixedSize
 960         {
 961             get { return false; }
 962         }
 963
 964         bool IDictionary.IsReadOnly
 965         {
 966             get { return false; }
 967         }
 968
 969         ICollection IDictionary.Keys
 970         {
 971             get { return (ICollection)Keys; }
 972         }
 973
 974         ICollection IDictionary.Values
 975         {
 976             get { return (ICollection)Values; }
 977         }
 978
 979         object IDictionary.this[object key]
 980         {
 981             get
 982             {
 983                 if (IsCompatibleKey(key))
 984                 {
 985                     int i = FindEntry((TKey)key);
 986                     if (i >= 0)
 987                     {
 988                         return _entries[i].value;
 989                     }
 990                 }
 991                 return null;
 992             }
 993             set
 994             {
 995                 if (key == null)
 996                 {
 997                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 998                 }
 999                 ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
1000
1001                 try
1002                 {
1003                     TKey tempKey = (TKey)key;
1004                     try
1005                     {
1006                         this[tempKey] = (TValue)value;
1007                     }
1008                     catch (InvalidCastException)
1009                     {
1010                         ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
1011                     }
1012                 }
1013                 catch (InvalidCastException)
1014                 {
1015                     ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
1016                 }
1017             }
1018         }
1019
1020         private static bool IsCompatibleKey(object key)
1021         {
1022             if (key == null)
1023             {
1024                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
1025             }
1026             return (key is TKey);
1027         }
1028
1029         void IDictionary.Add(object key, object value)
1030         {
1031             if (key == null)
1032             {
1033                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
1034             }
1035             ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
1036
1037             try
1038             {
1039                 TKey tempKey = (TKey)key;
1040
1041                 try
1042                 {
1043                     Add(tempKey, (TValue)value);
1044                 }
1045                 catch (InvalidCastException)
1046                 {
1047                     ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
1048                 }
1049             }
1050             catch (InvalidCastException)
1051             {
1052                 ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
1053             }
1054         }
1055
1056         bool IDictionary.Contains(object key)
1057         {
1058             if (IsCompatibleKey(key))
1059             {
1060                 return ContainsKey((TKey)key);
1061             }
1062
1063             return false;
1064         }
1065
1066         IDictionaryEnumerator IDictionary.GetEnumerator()
1067         {
1068             return new Enumerator(this, Enumerator.DictEntry);
1069         }
1070
1071         void IDictionary.Remove(object key)
1072         {
1073             if (IsCompatibleKey(key))
1074             {
1075                 Remove((TKey)key);
1076             }
1077         }
1078
1079         public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>,
1080             IDictionaryEnumerator
1081         {
1082             private Dictionary<TKey, TValue> _dictionary;
1083             private int _version;
1084             private int _index;
1085             private KeyValuePair<TKey, TValue> _current;
1086             private int _getEnumeratorRetType;  // What should Enumerator.Current return?
1087
1088             internal const int DictEntry = 1;
1089             internal const int KeyValuePair = 2;
1090
1091             internal Enumerator(Dictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
1092             {
1093                 _dictionary = dictionary;
1094                 _version = dictionary._version;
1095                 _index = 0;
1096                 _getEnumeratorRetType = getEnumeratorRetType;
1097                 _current = new KeyValuePair<TKey, TValue>();
1098             }
1099
1100             public bool MoveNext()
1101             {
1102                 if (_version != _dictionary._version)
1103                 {
1104                     ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1105                 }
1106
1107                 // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends.
1108                 // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue
1109                 while ((uint)_index < (uint)_dictionary._count)
1110                 {
1111                     ref Entry entry = ref _dictionary._entries[_index++];
1112
1113                     if (entry.hashCode >= 0)
1114                     {
1115                         _current = new KeyValuePair<TKey, TValue>(entry.key, entry.value);
1116                         return true;
1117                     }
1118                 }
1119
1120                 _index = _dictionary._count + 1;
1121                 _current = new KeyValuePair<TKey, TValue>();
1122                 return false;
1123             }
1124
1125             public KeyValuePair<TKey, TValue> Current
1126             {
1127                 get { return _current; }
1128             }
1129
1130             public void Dispose()
1131             {
1132             }
1133
1134             object IEnumerator.Current
1135             {
1136                 get
1137                 {
1138                     if (_index == 0 || (_index == _dictionary._count + 1))
1139                     {
1140                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1141                     }
1142
1143                     if (_getEnumeratorRetType == DictEntry)
1144                     {
1145                         return new System.Collections.DictionaryEntry(_current.Key, _current.Value);
1146                     }
1147                     else
1148                     {
1149                         return new KeyValuePair<TKey, TValue>(_current.Key, _current.Value);
1150                     }
1151                 }
1152             }
1153
1154             void IEnumerator.Reset()
1155             {
1156                 if (_version != _dictionary._version)
1157                 {
1158                     ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1159                 }
1160
1161                 _index = 0;
1162                 _current = new KeyValuePair<TKey, TValue>();
1163             }
1164
1165             DictionaryEntry IDictionaryEnumerator.Entry
1166             {
1167                 get
1168                 {
1169                     if (_index == 0 || (_index == _dictionary._count + 1))
1170                     {
1171                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1172                     }
1173
1174                     return new DictionaryEntry(_current.Key, _current.Value);
1175                 }
1176             }
1177
1178             object IDictionaryEnumerator.Key
1179             {
1180                 get
1181                 {
1182                     if (_index == 0 || (_index == _dictionary._count + 1))
1183                     {
1184                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1185                     }
1186
1187                     return _current.Key;
1188                 }
1189             }
1190
1191             object IDictionaryEnumerator.Value
1192             {
1193                 get
1194                 {
1195                     if (_index == 0 || (_index == _dictionary._count + 1))
1196                     {
1197                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1198                     }
1199
1200                     return _current.Value;
1201                 }
1202             }
1203         }
1204
1205         [DebuggerTypeProxy(typeof(DictionaryKeyCollectionDebugView<,>))]
1206         [DebuggerDisplay("Count = {Count}")]
1207         public sealed class KeyCollection : ICollection<TKey>, ICollection, IReadOnlyCollection<TKey>
1208         {
1209             private Dictionary<TKey, TValue> _dictionary;
1210
1211             public KeyCollection(Dictionary<TKey, TValue> dictionary)
1212             {
1213                 if (dictionary == null)
1214                 {
1215                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
1216                 }
1217                 _dictionary = dictionary;
1218             }
1219
1220             public Enumerator GetEnumerator()
1221             {
1222                 return new Enumerator(_dictionary);
1223             }
1224
1225             public void CopyTo(TKey[] array, int index)
1226             {
1227                 if (array == null)
1228                 {
1229                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1230                 }
1231
1232                 if (index < 0 || index > array.Length)
1233                 {
1234                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1235                 }
1236
1237                 if (array.Length - index < _dictionary.Count)
1238                 {
1239                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1240                 }
1241
1242                 int count = _dictionary._count;
1243                 Entry[] entries = _dictionary._entries;
1244                 for (int i = 0; i < count; i++)
1245                 {
1246                     if (entries[i].hashCode >= 0) array[index++] = entries[i].key;
1247                 }
1248             }
1249
1250             public int Count
1251             {
1252                 get { return _dictionary.Count; }
1253             }
1254
1255             bool ICollection<TKey>.IsReadOnly
1256             {
1257                 get { return true; }
1258             }
1259
1260             void ICollection<TKey>.Add(TKey item)
1261             {
1262                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
1263             }
1264
1265             void ICollection<TKey>.Clear()
1266             {
1267                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
1268             }
1269
1270             bool ICollection<TKey>.Contains(TKey item)
1271             {
1272                 return _dictionary.ContainsKey(item);
1273             }
1274
1275             bool ICollection<TKey>.Remove(TKey item)
1276             {
1277                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
1278                 return false;
1279             }
1280
1281             IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator()
1282             {
1283                 return new Enumerator(_dictionary);
1284             }
1285
1286             IEnumerator IEnumerable.GetEnumerator()
1287             {
1288                 return new Enumerator(_dictionary);
1289             }
1290
1291             void ICollection.CopyTo(Array array, int index)
1292             {
1293                 if (array == null)
1294                 {
1295                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1296                 }
1297
1298                 if (array.Rank != 1)
1299                 {
1300                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
1301                 }
1302
1303                 if (array.GetLowerBound(0) != 0)
1304                 {
1305                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
1306                 }
1307
1308                 if (index < 0 || index > array.Length)
1309                 {
1310                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1311                 }
1312
1313                 if (array.Length - index < _dictionary.Count)
1314                 {
1315                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1316                 }
1317
1318                 TKey[] keys = array as TKey[];
1319                 if (keys != null)
1320                 {
1321                     CopyTo(keys, index);
1322                 }
1323                 else
1324                 {
1325                     object[] objects = array as object[];
1326                     if (objects == null)
1327                     {
1328                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1329                     }
1330
1331                     int count = _dictionary._count;
1332                     Entry[] entries = _dictionary._entries;
1333                     try
1334                     {
1335                         for (int i = 0; i < count; i++)
1336                         {
1337                             if (entries[i].hashCode >= 0) objects[index++] = entries[i].key;
1338                         }
1339                     }
1340                     catch (ArrayTypeMismatchException)
1341                     {
1342                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1343                     }
1344                 }
1345             }
1346
1347             bool ICollection.IsSynchronized
1348             {
1349                 get { return false; }
1350             }
1351
1352             object ICollection.SyncRoot
1353             {
1354                 get { return ((ICollection)_dictionary).SyncRoot; }
1355             }
1356
1357             public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator
1358             {
1359                 private Dictionary<TKey, TValue> _dictionary;
1360                 private int _index;
1361                 private int _version;
1362                 private TKey _currentKey;
1363
1364                 internal Enumerator(Dictionary<TKey, TValue> dictionary)
1365                 {
1366                     _dictionary = dictionary;
1367                     _version = dictionary._version;
1368                     _index = 0;
1369                     _currentKey = default(TKey);
1370                 }
1371
1372                 public void Dispose()
1373                 {
1374                 }
1375
1376                 public bool MoveNext()
1377                 {
1378                     if (_version != _dictionary._version)
1379                     {
1380                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1381                     }
1382
1383                     while ((uint)_index < (uint)_dictionary._count)
1384                     {
1385                         ref Entry entry = ref _dictionary._entries[_index++];
1386
1387                         if (entry.hashCode >= 0)
1388                         {
1389                             _currentKey = entry.key;
1390                             return true;
1391                         }
1392                     }
1393
1394                     _index = _dictionary._count + 1;
1395                     _currentKey = default(TKey);
1396                     return false;
1397                 }
1398
1399                 public TKey Current
1400                 {
1401                     get
1402                     {
1403                         return _currentKey;
1404                     }
1405                 }
1406
1407                 object System.Collections.IEnumerator.Current
1408                 {
1409                     get
1410                     {
1411                         if (_index == 0 || (_index == _dictionary._count + 1))
1412                         {
1413                             ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1414                         }
1415
1416                         return _currentKey;
1417                     }
1418                 }
1419
1420                 void System.Collections.IEnumerator.Reset()
1421                 {
1422                     if (_version != _dictionary._version)
1423                     {
1424                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1425                     }
1426
1427                     _index = 0;
1428                     _currentKey = default(TKey);
1429                 }
1430             }
1431         }
1432
1433         [DebuggerTypeProxy(typeof(DictionaryValueCollectionDebugView<,>))]
1434         [DebuggerDisplay("Count = {Count}")]
1435         public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue>
1436         {
1437             private Dictionary<TKey, TValue> _dictionary;
1438
1439             public ValueCollection(Dictionary<TKey, TValue> dictionary)
1440             {
1441                 if (dictionary == null)
1442                 {
1443                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
1444                 }
1445                 _dictionary = dictionary;
1446             }
1447
1448             public Enumerator GetEnumerator()
1449             {
1450                 return new Enumerator(_dictionary);
1451             }
1452
1453             public void CopyTo(TValue[] array, int index)
1454             {
1455                 if (array == null)
1456                 {
1457                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1458                 }
1459
1460                 if (index < 0 || index > array.Length)
1461                 {
1462                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1463                 }
1464
1465                 if (array.Length - index < _dictionary.Count)
1466                 {
1467                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1468                 }
1469
1470                 int count = _dictionary._count;
1471                 Entry[] entries = _dictionary._entries;
1472                 for (int i = 0; i < count; i++)
1473                 {
1474                     if (entries[i].hashCode >= 0) array[index++] = entries[i].value;
1475                 }
1476             }
1477
1478             public int Count
1479             {
1480                 get { return _dictionary.Count; }
1481             }
1482
1483             bool ICollection<TValue>.IsReadOnly
1484             {
1485                 get { return true; }
1486             }
1487
1488             void ICollection<TValue>.Add(TValue item)
1489             {
1490                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
1491             }
1492
1493             bool ICollection<TValue>.Remove(TValue item)
1494             {
1495                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
1496                 return false;
1497             }
1498
1499             void ICollection<TValue>.Clear()
1500             {
1501                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
1502             }
1503
1504             bool ICollection<TValue>.Contains(TValue item)
1505             {
1506                 return _dictionary.ContainsValue(item);
1507             }
1508
1509             IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
1510             {
1511                 return new Enumerator(_dictionary);
1512             }
1513
1514             IEnumerator IEnumerable.GetEnumerator()
1515             {
1516                 return new Enumerator(_dictionary);
1517             }
1518
1519             void ICollection.CopyTo(Array array, int index)
1520             {
1521                 if (array == null)
1522                 {
1523                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1524                 }
1525
1526                 if (array.Rank != 1)
1527                 {
1528                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
1529                 }
1530
1531                 if (array.GetLowerBound(0) != 0)
1532                 {
1533                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
1534                 }
1535
1536                 if (index < 0 || index > array.Length)
1537                 {
1538                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1539                 }
1540
1541                 if (array.Length - index < _dictionary.Count)
1542                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1543
1544                 TValue[] values = array as TValue[];
1545                 if (values != null)
1546                 {
1547                     CopyTo(values, index);
1548                 }
1549                 else
1550                 {
1551                     object[] objects = array as object[];
1552                     if (objects == null)
1553                     {
1554                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1555                     }
1556
1557                     int count = _dictionary._count;
1558                     Entry[] entries = _dictionary._entries;
1559                     try
1560                     {
1561                         for (int i = 0; i < count; i++)
1562                         {
1563                             if (entries[i].hashCode >= 0) objects[index++] = entries[i].value;
1564                         }
1565                     }
1566                     catch (ArrayTypeMismatchException)
1567                     {
1568                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1569                     }
1570                 }
1571             }
1572
1573             bool ICollection.IsSynchronized
1574             {
1575                 get { return false; }
1576             }
1577
1578             object ICollection.SyncRoot
1579             {
1580                 get { return ((ICollection)_dictionary).SyncRoot; }
1581             }
1582
1583             public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator
1584             {
1585                 private Dictionary<TKey, TValue> _dictionary;
1586                 private int _index;
1587                 private int _version;
1588                 private TValue _currentValue;
1589
1590                 internal Enumerator(Dictionary<TKey, TValue> dictionary)
1591                 {
1592                     _dictionary = dictionary;
1593                     _version = dictionary._version;
1594                     _index = 0;
1595                     _currentValue = default(TValue);
1596                 }
1597
1598                 public void Dispose()
1599                 {
1600                 }
1601
1602                 public bool MoveNext()
1603                 {
1604                     if (_version != _dictionary._version)
1605                     {
1606                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1607                     }
1608
1609                     while ((uint)_index < (uint)_dictionary._count)
1610                     {
1611                         ref Entry entry = ref _dictionary._entries[_index++];
1612
1613                         if (entry.hashCode >= 0)
1614                         {
1615                             _currentValue = entry.value;
1616                             return true;
1617                         }
1618                     }
1619                     _index = _dictionary._count + 1;
1620                     _currentValue = default(TValue);
1621                     return false;
1622                 }
1623
1624                 public TValue Current
1625                 {
1626                     get
1627                     {
1628                         return _currentValue;
1629                     }
1630                 }
1631
1632                 object System.Collections.IEnumerator.Current
1633                 {
1634                     get
1635                     {
1636                         if (_index == 0 || (_index == _dictionary._count + 1))
1637                         {
1638                             ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1639                         }
1640
1641                         return _currentValue;
1642                     }
1643                 }
1644
1645                 void System.Collections.IEnumerator.Reset()
1646                 {
1647                     if (_version != _dictionary._version)
1648                     {
1649                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1650                     }
1651                     _index = 0;
1652                     _currentValue = default(TValue);
1653                 }
1654             }
1655         }
1656     }
1657 }