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