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