-
Notifications
You must be signed in to change notification settings - Fork 1.3k
/
hashtable.cs
1842 lines (1592 loc) · 80.7 KB
/
hashtable.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
/*============================================================
**
** Class: Hashtable
**
** <OWNER>[....]</OWNER>
**
**
** Purpose: Hash table implementation
**
**
===========================================================*/
namespace System.Collections {
using System;
using System.Runtime;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Diagnostics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Runtime.ConstrainedExecution;
using System.Diagnostics.Contracts;
using System.Security.Cryptography;
// The Hashtable class represents a dictionary of associated keys and values
// with constant lookup time.
//
// Objects used as keys in a hashtable must implement the GetHashCode
// and Equals methods (or they can rely on the default implementations
// inherited from Object if key equality is simply reference
// equality). Furthermore, the GetHashCode and Equals methods of
// a key object must produce the same results given the same parameters for the
// entire time the key is present in the hashtable. In practical terms, this
// means that key objects should be immutable, at least for the time they are
// used as keys in a hashtable.
//
// When entries are added to a hashtable, they are placed into
// buckets based on the hashcode of their keys. Subsequent lookups of
// keys will use the hashcode of the keys to only search a particular bucket,
// thus substantially reducing the number of key comparisons required to find
// an entry. A hashtable's maximum load factor, which can be specified
// when the hashtable is instantiated, determines the maximum ratio of
// hashtable entries to hashtable buckets. Smaller load factors cause faster
// average lookup times at the cost of increased memory consumption. The
// default maximum load factor of 1.0 generally provides the best balance
// between speed and size. As entries are added to a hashtable, the hashtable's
// actual load factor increases, and when the actual load factor reaches the
// maximum load factor value, the number of buckets in the hashtable is
// automatically increased by approximately a factor of two (to be precise, the
// number of hashtable buckets is increased to the smallest prime number that
// is larger than twice the current number of hashtable buckets).
//
// Each object provides their own hash function, accessed by calling
// GetHashCode(). However, one can write their own object
// implementing IEqualityComparer and pass it to a constructor on
// the Hashtable. That hash function (and the equals method on the
// IEqualityComparer) would be used for all objects in the table.
//
// Changes since V1 during Whidbey:
// *) Deprecated IHashCodeProvider, use IEqualityComparer instead. This will
// allow better performance for objects where equality checking can be
// done much faster than establishing an ordering between two objects,
// such as an ordinal string equality check.
//
[DebuggerTypeProxy(typeof(System.Collections.Hashtable.HashtableDebugView))]
[DebuggerDisplay("Count = {Count}")]
[System.Runtime.InteropServices.ComVisible(true)]
[Serializable]
public class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable {
/*
Implementation Notes:
The generic Dictionary was copied from Hashtable's source - any bug
fixes here probably need to be made to the generic Dictionary as well.
This Hashtable uses double hashing. There are hashsize buckets in the
table, and each bucket can contain 0 or 1 element. We a bit to mark
whether there's been a collision when we inserted multiple elements
(ie, an inserted item was hashed at least a second time and we probed
this bucket, but it was already in use). Using the collision bit, we
can terminate lookups & removes for elements that aren't in the hash
table more quickly. We steal the most significant bit from the hash code
to store the collision bit.
Our hash function is of the following form:
h(key, n) = h1(key) + n*h2(key)
where n is the number of times we've hit a collided bucket and rehashed
(on this particular lookup). Here are our hash functions:
h1(key) = GetHash(key); // default implementation calls key.GetHashCode();
h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));
The h1 can return any number. h2 must return a number between 1 and
hashsize - 1 that is relatively prime to hashsize (not a problem if
hashsize is prime). (Knuth's Art of Computer Programming, Vol. 3, p. 528-9)
If this is true, then we are guaranteed to visit every bucket in exactly
hashsize probes, since the least common multiple of hashsize and h2(key)
will be hashsize * h2(key). (This is the first number where adding h2 to
h1 mod hashsize will be 0 and we will search the same bucket twice).
We previously used a different h2(key, n) that was not constant. That is a
horrifically bad idea, unless you can prove that series will never produce
any identical numbers that overlap when you mod them by hashsize, for all
subranges from i to i+hashsize, for all i. It's not worth investigating,
since there was no clear benefit from using that hash function, and it was
broken.
For efficiency reasons, we've implemented this by storing h1 and h2 in a
temporary, and setting a variable called seed equal to h1. We do a probe,
and if we collided, we simply add h2 to seed each time through the loop.
A good test for h2() is to subclass Hashtable, provide your own implementation
of GetHash() that returns a constant, then add many items to the hash table.
Make sure Count equals the number of items you inserted.
Note that when we remove an item from the hash table, we set the key
equal to buckets, if there was a collision in this bucket. Otherwise
we'd either wipe out the collision bit, or we'd still have an item in
the hash table.
--
*/
internal const Int32 HashPrime = 101;
private const Int32 InitialSize = 3;
private const String LoadFactorName = "LoadFactor";
private const String VersionName = "Version";
private const String ComparerName = "Comparer";
private const String HashCodeProviderName = "HashCodeProvider";
private const String HashSizeName = "HashSize"; // Must save buckets.Length
private const String KeysName = "Keys";
private const String ValuesName = "Values";
private const String KeyComparerName = "KeyComparer";
// Deleted entries have their key set to buckets
// The hash table data.
// This cannot be serialised
private struct bucket {
public Object key;
public Object val;
public int hash_coll; // Store hash code; sign bit means there was a collision.
}
private bucket[] buckets;
// The total number of entries in the hash table.
private int count;
// The total number of collision bits set in the hashtable
private int occupancy;
private int loadsize;
private float loadFactor;
private volatile int version;
private volatile bool isWriterInProgress;
private ICollection keys;
private ICollection values;
private IEqualityComparer _keycomparer;
private Object _syncRoot;
[Obsolete("Please use EqualityComparer property.")]
protected IHashCodeProvider hcp
{
get
{
if( _keycomparer is CompatibleComparer) {
return ((CompatibleComparer)_keycomparer).HashCodeProvider;
}
else if( _keycomparer == null) {
return null;
}
else {
throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
}
}
set
{
if (_keycomparer is CompatibleComparer) {
CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer;
_keycomparer = new CompatibleComparer(keyComparer.Comparer, value);
}
else if( _keycomparer == null) {
_keycomparer = new CompatibleComparer((IComparer)null, value);
}
else {
throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
}
}
}
[Obsolete("Please use KeyComparer properties.")]
protected IComparer comparer
{
get
{
if( _keycomparer is CompatibleComparer) {
return ((CompatibleComparer)_keycomparer).Comparer;
}
else if( _keycomparer == null) {
return null;
}
else {
throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
}
}
set
{
if (_keycomparer is CompatibleComparer) {
CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer;
_keycomparer = new CompatibleComparer(value, keyComparer.HashCodeProvider);
}
else if( _keycomparer == null) {
_keycomparer = new CompatibleComparer(value, (IHashCodeProvider)null);
}
else {
throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
}
}
}
protected IEqualityComparer EqualityComparer
{
get
{
return _keycomparer;
}
}
// Note: this constructor is a bogus constructor that does nothing
// and is for use only with SyncHashtable.
internal Hashtable( bool trash )
{
}
// Constructs a new hashtable. The hashtable is created with an initial
// capacity of zero and a load factor of 1.0.
public Hashtable() : this(0, 1.0f) {
}
// Constructs a new hashtable with the given initial capacity and a load
// factor of 1.0. The capacity argument serves as an indication of
// the number of entries the hashtable will contain. When this number (or
// an approximation) is known, specifying it in the constructor can
// eliminate a number of resizing operations that would otherwise be
// performed when elements are added to the hashtable.
//
public Hashtable(int capacity) : this(capacity, 1.0f) {
}
// Constructs a new hashtable with the given initial capacity and load
// factor. The capacity argument serves as an indication of the
// number of entries the hashtable will contain. When this number (or an
// approximation) is known, specifying it in the constructor can eliminate
// a number of resizing operations that would otherwise be performed when
// elements are added to the hashtable. The loadFactor argument
// indicates the maximum ratio of hashtable entries to hashtable buckets.
// Smaller load factors cause faster average lookup times at the cost of
// increased memory consumption. A load factor of 1.0 generally provides
// the best balance between speed and size.
//
public Hashtable(int capacity, float loadFactor) {
if (capacity < 0)
throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
if (!(loadFactor >= 0.1f && loadFactor <= 1.0f))
throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", .1, 1.0));
Contract.EndContractBlock();
// Based on perf work, .72 is the optimal load factor for this table.
this.loadFactor = 0.72f * loadFactor;
double rawsize = capacity / this.loadFactor;
if (rawsize > Int32.MaxValue)
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
// Avoid awfully small sizes
int hashsize = (rawsize > InitialSize) ? HashHelpers.GetPrime((int)rawsize) : InitialSize;
buckets = new bucket[hashsize];
loadsize = (int)(this.loadFactor * hashsize);
isWriterInProgress = false;
// Based on the current algorithm, loadsize must be less than hashsize.
Contract.Assert( loadsize < hashsize, "Invalid hashtable loadsize!");
}
// Constructs a new hashtable with the given initial capacity and load
// factor. The capacity argument serves as an indication of the
// number of entries the hashtable will contain. When this number (or an
// approximation) is known, specifying it in the constructor can eliminate
// a number of resizing operations that would otherwise be performed when
// elements are added to the hashtable. The loadFactor argument
// indicates the maximum ratio of hashtable entries to hashtable buckets.
// Smaller load factors cause faster average lookup times at the cost of
// increased memory consumption. A load factor of 1.0 generally provides
// the best balance between speed and size. The hcp argument
// is used to specify an Object that will provide hash codes for all
// the Objects in the table. Using this, you can in effect override
// GetHashCode() on each Object using your own hash function. The
// comparer argument will let you specify a custom function for
// comparing keys. By specifying user-defined objects for hcp
// and comparer, users could make a hash table using strings
// as keys do case-insensitive lookups.
//
[Obsolete("Please use Hashtable(int, float, IEqualityComparer) instead.")]
public Hashtable(int capacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer) : this(capacity, loadFactor) {
if (hcp == null && comparer == null) {
this._keycomparer = null;
}
else {
this._keycomparer = new CompatibleComparer(comparer,hcp);
}
}
public Hashtable(int capacity, float loadFactor, IEqualityComparer equalityComparer) : this(capacity, loadFactor) {
this._keycomparer = equalityComparer;
}
// Constructs a new hashtable using a custom hash function
// and a custom comparison function for keys. This will enable scenarios
// such as doing lookups with case-insensitive strings.
//
[Obsolete("Please use Hashtable(IEqualityComparer) instead.")]
public Hashtable(IHashCodeProvider hcp, IComparer comparer) : this(0, 1.0f, hcp, comparer) {
}
public Hashtable(IEqualityComparer equalityComparer) : this(0, 1.0f, equalityComparer) {
}
// Constructs a new hashtable using a custom hash function
// and a custom comparison function for keys. This will enable scenarios
// such as doing lookups with case-insensitive strings.
//
[Obsolete("Please use Hashtable(int, IEqualityComparer) instead.")]
public Hashtable(int capacity, IHashCodeProvider hcp, IComparer comparer)
: this(capacity, 1.0f, hcp, comparer) {
}
public Hashtable(int capacity, IEqualityComparer equalityComparer)
: this(capacity, 1.0f, equalityComparer) {
}
// Constructs a new hashtable containing a copy of the entries in the given
// dictionary. The hashtable is created with a load factor of 1.0.
//
public Hashtable(IDictionary d) : this(d, 1.0f) {
}
// Constructs a new hashtable containing a copy of the entries in the given
// dictionary. The hashtable is created with the given load factor.
//
public Hashtable(IDictionary d, float loadFactor)
: this(d, loadFactor, (IEqualityComparer)null) {
}
[Obsolete("Please use Hashtable(IDictionary, IEqualityComparer) instead.")]
public Hashtable(IDictionary d, IHashCodeProvider hcp, IComparer comparer)
: this(d, 1.0f, hcp, comparer) {
}
public Hashtable(IDictionary d, IEqualityComparer equalityComparer)
: this(d, 1.0f, equalityComparer) {
}
[Obsolete("Please use Hashtable(IDictionary, float, IEqualityComparer) instead.")]
public Hashtable(IDictionary d, float loadFactor, IHashCodeProvider hcp, IComparer comparer)
: this((d != null ? d.Count : 0), loadFactor, hcp, comparer) {
if (d==null)
throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary"));
Contract.EndContractBlock();
IDictionaryEnumerator e = d.GetEnumerator();
while (e.MoveNext()) Add(e.Key, e.Value);
}
public Hashtable(IDictionary d, float loadFactor, IEqualityComparer equalityComparer)
: this((d != null ? d.Count : 0), loadFactor, equalityComparer) {
if (d==null)
throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary"));
Contract.EndContractBlock();
IDictionaryEnumerator e = d.GetEnumerator();
while (e.MoveNext()) Add(e.Key, e.Value);
}
protected Hashtable(SerializationInfo info, StreamingContext context) {
//We can't do anything with the keys and values until the entire graph has been deserialized
//and we have a reasonable estimate that GetHashCode is not going to fail. For the time being,
//we'll just cache this. The graph is not valid until OnDeserialization has been called.
HashHelpers.SerializationInfoTable.Add(this, info);
}
// InitHash is basically an implementation of classic DoubleHashing (see http://en.wikipedia.org/wiki/Double_hashing)
//
// 1) The only correctness requirement is that the increment used to probe
// a. Be non-zero
// b. Be relatively prime to the table size hashSize. (This is needed to insure you probe all entries in the table before you wrap and visit entries already probed)
// 2) Because we choose table sizes to be primes, we just need to insure that the increment is 0 < incr < hashSize
//
// Thus this function would work: Incr = 1 + (seed % (hashSize-1))
//
// While this works well for uniformly distributed keys, in practice, non-uniformity is common.
// In particular in practice we can see mostly sequential where you get long clusters of keys that pack.
// To avoid bad behavior you want it to be the case that the increment is large even for small values (because small
// values tend to happen more in practice). Thus we multiply seed by a number that will make these small values
// bigger (and not hurt large values). We picked HashPrime (101) because it was prime, and if hashSize-1 is not a multiple of HashPrime
// (enforced in GetPrime), then incr has the potential of being every value from 1 to hashSize-1. The choice was largely arbitrary.
//
// Computes the hash function: H(key, i) = h1(key) + i*h2(key, hashSize).
// The out parameter seed is h1(key), while the out parameter
// incr is h2(key, hashSize). Callers of this function should
// add incr each time through a loop.
private uint InitHash(Object key, int hashsize, out uint seed, out uint incr) {
// Hashcode must be positive. Also, we must not use the sign bit, since
// that is used for the collision bit.
uint hashcode = (uint) GetHash(key) & 0x7FFFFFFF;
seed = (uint) hashcode;
// Restriction: incr MUST be between 1 and hashsize - 1, inclusive for
// the modular arithmetic to work correctly. This guarantees you'll
// visit every bucket in the table exactly once within hashsize
// iterations. Violate this and it'll cause obscure bugs forever.
// If you change this calculation for h2(key), update putEntry too!
incr = (uint)(1 + ((seed * HashPrime) % ((uint)hashsize - 1)));
return hashcode;
}
// Adds an entry with the given key and value to this hashtable. An
// ArgumentException is thrown if the key is null or if the key is already
// present in the hashtable.
//
public virtual void Add(Object key, Object value) {
Insert(key, value, true);
}
// Removes all entries from this hashtable.
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public virtual void Clear() {
Contract.Assert(!isWriterInProgress, "Race condition detected in usages of Hashtable - multiple threads appear to be writing to a Hashtable instance simultaneously! Don't do that - use Hashtable.Synchronized.");
if (count == 0 && occupancy == 0)
return;
#if !FEATURE_CORECLR
Thread.BeginCriticalRegion();
#endif
isWriterInProgress = true;
for (int i = 0; i < buckets.Length; i++){
buckets[i].hash_coll = 0;
buckets[i].key = null;
buckets[i].val = null;
}
count = 0;
occupancy = 0;
UpdateVersion();
isWriterInProgress = false;
#if !FEATURE_CORECLR
Thread.EndCriticalRegion();
#endif
}
// Clone returns a virtually identical copy of this hash table. This does
// a shallow copy - the Objects in the table aren't cloned, only the references
// to those Objects.
public virtual Object Clone()
{
bucket[] lbuckets = buckets;
Hashtable ht = new Hashtable(count,_keycomparer);
ht.version = version;
ht.loadFactor = loadFactor;
ht.count = 0;
int bucket = lbuckets.Length;
while (bucket > 0) {
bucket--;
Object keyv = lbuckets[bucket].key;
if ((keyv!= null) && (keyv != lbuckets)) {
ht[keyv] = lbuckets[bucket].val;
}
}
return ht;
}
// Checks if this hashtable contains the given key.
public virtual bool Contains(Object key) {
return ContainsKey(key);
}
// Checks if this hashtable contains an entry with the given key. This is
// an O(1) operation.
//
public virtual bool ContainsKey(Object key) {
if (key == null) {
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Contract.EndContractBlock();
uint seed;
uint incr;
// Take a snapshot of buckets, in case another thread resizes table
bucket[] lbuckets = buckets;
uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
int ntry = 0;
bucket b;
int bucketNumber = (int) (seed % (uint)lbuckets.Length);
do {
b = lbuckets[bucketNumber];
if (b.key == null) {
return false;
}
if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
KeyEquals (b.key, key))
return true;
bucketNumber = (int) (((long)bucketNumber + incr)% (uint)lbuckets.Length);
} while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
return false;
}
// Checks if this hashtable contains an entry with the given value. The
// values of the entries of the hashtable are compared to the given value
// using the Object.Equals method. This method performs a linear
// search and is thus be substantially slower than the ContainsKey
// method.
//
public virtual bool ContainsValue(Object value) {
if (value == null) {
for (int i = buckets.Length; --i >= 0;) {
if (buckets[i].key != null && buckets[i].key != buckets && buckets[i].val == null)
return true;
}
}
else {
for (int i = buckets.Length; --i >= 0;) {
Object val = buckets[i].val;
if (val!=null && val.Equals(value)) return true;
}
}
return false;
}
// Copies the keys of this hashtable to a given array starting at a given
// index. This method is used by the implementation of the CopyTo method in
// the KeyCollection class.
private void CopyKeys(Array array, int arrayIndex) {
Contract.Requires(array != null);
Contract.Requires(array.Rank == 1);
bucket[] lbuckets = buckets;
for (int i = lbuckets.Length; --i >= 0;) {
Object keyv = lbuckets[i].key;
if ((keyv != null) && (keyv != buckets)){
array.SetValue(keyv, arrayIndex++);
}
}
}
// Copies the keys of this hashtable to a given array starting at a given
// index. This method is used by the implementation of the CopyTo method in
// the KeyCollection class.
private void CopyEntries(Array array, int arrayIndex) {
Contract.Requires(array != null);
Contract.Requires(array.Rank == 1);
bucket[] lbuckets = buckets;
for (int i = lbuckets.Length; --i >= 0;) {
Object keyv = lbuckets[i].key;
if ((keyv != null) && (keyv != buckets)){
DictionaryEntry entry = new DictionaryEntry(keyv,lbuckets[i].val);
array.SetValue(entry, arrayIndex++);
}
}
}
// Copies the values in this hash table to an array at
// a given index. Note that this only copies values, and not keys.
public virtual void CopyTo(Array array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException("array", Environment.GetResourceString("ArgumentNull_Array"));
if (array.Rank != 1)
throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
if (arrayIndex < 0)
throw new ArgumentOutOfRangeException("arrayIndex", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
if (array.Length - arrayIndex < Count)
throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall"));
Contract.EndContractBlock();
CopyEntries(array, arrayIndex);
}
// Copies the values in this Hashtable to an KeyValuePairs array.
// KeyValuePairs is different from Dictionary Entry in that it has special
// debugger attributes on its fields.
internal virtual KeyValuePairs[] ToKeyValuePairsArray() {
KeyValuePairs[] array = new KeyValuePairs[count];
int index = 0;
bucket[] lbuckets = buckets;
for (int i = lbuckets.Length; --i >= 0;) {
Object keyv = lbuckets[i].key;
if ((keyv != null) && (keyv != buckets)){
array[index++] = new KeyValuePairs(keyv,lbuckets[i].val);
}
}
return array;
}
// Copies the values of this hashtable to a given array starting at a given
// index. This method is used by the implementation of the CopyTo method in
// the ValueCollection class.
private void CopyValues(Array array, int arrayIndex) {
Contract.Requires(array != null);
Contract.Requires(array.Rank == 1);
bucket[] lbuckets = buckets;
for (int i = lbuckets.Length; --i >= 0;) {
Object keyv = lbuckets[i].key;
if ((keyv != null) && (keyv != buckets)){
array.SetValue(lbuckets[i].val, arrayIndex++);
}
}
}
// Returns the value associated with the given key. If an entry with the
// given key is not found, the returned value is null.
//
public virtual Object this[Object key] {
get {
if (key == null) {
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Contract.EndContractBlock();
uint seed;
uint incr;
// Take a snapshot of buckets, in case another thread does a resize
bucket[] lbuckets = buckets;
uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
int ntry = 0;
bucket b;
int bucketNumber = (int) (seed % (uint)lbuckets.Length);
do
{
int currentversion;
// A read operation on hashtable has three steps:
// (1) calculate the hash and find the slot number.
// (2) compare the hashcode, if equal, go to step 3. Otherwise end.
// (3) compare the key, if equal, go to step 4. Otherwise end.
// (4) return the value contained in the bucket.
// After step 3 and before step 4. A writer can kick in a remove the old item and add a new one
// in the same bukcet. So in the reader we need to check if the hash table is modified during above steps.
//
// Writers (Insert, Remove, Clear) will set 'isWriterInProgress' flag before it starts modifying
// the hashtable and will ckear the flag when it is done. When the flag is cleared, the 'version'
// will be increased. We will repeat the reading if a writer is in progress or done with the modification
// during the read.
//
// Our memory model guarantee if we pick up the change in bucket from another processor,
// we will see the 'isWriterProgress' flag to be true or 'version' is changed in the reader.
//
int spinCount = 0;
do {
// this is violate read, following memory accesses can not be moved ahead of it.
currentversion = version;
b = lbuckets[bucketNumber];
// The contention between reader and writer shouldn't happen frequently.
// But just in case this will burn CPU, yield the control of CPU if we spinned a few times.
// 8 is just a random number I pick.
if( (++spinCount) % 8 == 0 ) {
Thread.Sleep(1); // 1 means we are yeilding control to all threads, including low-priority ones.
}
} while ( isWriterInProgress || (currentversion != version) );
if (b.key == null) {
return null;
}
if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
KeyEquals (b.key, key))
return b.val;
bucketNumber = (int) (((long)bucketNumber + incr)% (uint)lbuckets.Length);
} while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
return null;
}
set {
Insert(key, value, false);
}
}
// Increases the bucket count of this hashtable. This method is called from
// the Insert method when the actual load factor of the hashtable reaches
// the upper limit specified when the hashtable was constructed. The number
// of buckets in the hashtable is increased to the smallest prime number
// that is larger than twice the current number of buckets, and the entries
// in the hashtable are redistributed into the new buckets using the cached
// hashcodes.
private void expand() {
int rawsize = HashHelpers.ExpandPrime(buckets.Length);
rehash(rawsize, false);
}
// We occationally need to rehash the table to clean up the collision bits.
private void rehash() {
rehash( buckets.Length, false );
}
private void UpdateVersion() {
// Version might become negative when version is Int32.MaxValue, but the oddity will be still be correct.
// So we don't need to special case this.
version++;
}
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
private void rehash( int newsize, bool forceNewHashCode ) {
// reset occupancy
occupancy=0;
// Don't replace any internal state until we've finished adding to the
// new bucket[]. This serves two purposes:
// 1) Allow concurrent readers to see valid hashtable contents
// at all times
// 2) Protect against an OutOfMemoryException while allocating this
// new bucket[].
bucket[] newBuckets = new bucket[newsize];
// rehash table into new buckets
int nb;
for (nb = 0; nb < buckets.Length; nb++){
bucket oldb = buckets[nb];
if ((oldb.key != null) && (oldb.key != buckets)) {
int hashcode = ((forceNewHashCode ? GetHash(oldb.key) : oldb.hash_coll) & 0x7FFFFFFF);
putEntry(newBuckets, oldb.key, oldb.val, hashcode);
}
}
// New bucket[] is good to go - replace buckets and other internal state.
#if !FEATURE_CORECLR
Thread.BeginCriticalRegion();
#endif
isWriterInProgress = true;
buckets = newBuckets;
loadsize = (int)(loadFactor * newsize);
UpdateVersion();
isWriterInProgress = false;
#if !FEATURE_CORECLR
Thread.EndCriticalRegion();
#endif
// minimun size of hashtable is 3 now and maximum loadFactor is 0.72 now.
Contract.Assert(loadsize < newsize, "Our current implementaion means this is not possible.");
return;
}
// Returns an enumerator for this hashtable.
// If modifications made to the hashtable while an enumeration is
// in progress, the MoveNext and Current methods of the
// enumerator will throw an exception.
//
IEnumerator IEnumerable.GetEnumerator() {
return new HashtableEnumerator(this, HashtableEnumerator.DictEntry);
}
// Returns a dictionary enumerator for this hashtable.
// If modifications made to the hashtable while an enumeration is
// in progress, the MoveNext and Current methods of the
// enumerator will throw an exception.
//
public virtual IDictionaryEnumerator GetEnumerator() {
return new HashtableEnumerator(this, HashtableEnumerator.DictEntry);
}
// Internal method to get the hash code for an Object. This will call
// GetHashCode() on each object if you haven't provided an IHashCodeProvider
// instance. Otherwise, it calls hcp.GetHashCode(obj).
protected virtual int GetHash(Object key)
{
if (_keycomparer != null)
return _keycomparer.GetHashCode(key);
return key.GetHashCode();
}
// Is this Hashtable read-only?
public virtual bool IsReadOnly {
get { return false; }
}
public virtual bool IsFixedSize {
get { return false; }
}
// Is this Hashtable synchronized? See SyncRoot property
public virtual bool IsSynchronized {
get { return false; }
}
// Internal method to compare two keys. If you have provided an IComparer
// instance in the constructor, this method will call comparer.Compare(item, key).
// Otherwise, it will call item.Equals(key).
//
protected virtual bool KeyEquals(Object item, Object key)
{
Contract.Assert(key != null, "key can't be null here!");
if( Object.ReferenceEquals(buckets, item)) {
return false;
}
if (Object.ReferenceEquals(item,key))
return true;
if (_keycomparer != null)
return _keycomparer.Equals(item, key);
return item == null ? false : item.Equals(key);
}
// Returns a collection representing the keys of this hashtable. The order
// in which the returned collection represents the keys is unspecified, but
// it is guaranteed to be buckets = newBuckets; the same order in which a collection returned by
// GetValues represents the values of the hashtable.
//
// The returned collection is live in the sense that any changes
// to the hash table are reflected in this collection. It is not
// a static copy of all the keys in the hash table.
//
public virtual ICollection Keys {
get {
if (keys == null) keys = new KeyCollection(this);
return keys;
}
}
// Returns a collection representing the values of this hashtable. The
// order in which the returned collection represents the values is
// unspecified, but it is guaranteed to be the same order in which a
// collection returned by GetKeys represents the keys of the
// hashtable.
//
// The returned collection is live in the sense that any changes
// to the hash table are reflected in this collection. It is not
// a static copy of all the keys in the hash table.
//
public virtual ICollection Values {
get {
if (values == null) values = new ValueCollection(this);
return values;
}
}
// Inserts an entry into this hashtable. This method is called from the Set
// and Add methods. If the add parameter is true and the given key already
// exists in the hashtable, an exception is thrown.
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
private void Insert (Object key, Object nvalue, bool add) {
// @
if (key == null) {
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Contract.EndContractBlock();
if (count >= loadsize) {
expand();
}
else if(occupancy > loadsize && count > 100) {
rehash();
}
uint seed;
uint incr;
// Assume we only have one thread writing concurrently. Modify
// buckets to contain new data, as long as we insert in the right order.
uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
int ntry = 0;
int emptySlotNumber = -1; // We use the empty slot number to cache the first empty slot. We chose to reuse slots
// create by remove that have the collision bit set over using up new slots.
int bucketNumber = (int) (seed % (uint)buckets.Length);
do {
// Set emptySlot number to current bucket if it is the first available bucket that we have seen
// that once contained an entry and also has had a collision.
// We need to search this entire collision chain because we have to ensure that there are no
// duplicate entries in the table.
if (emptySlotNumber == -1 && (buckets[bucketNumber].key == buckets) && (buckets[bucketNumber].hash_coll < 0))//(((buckets[bucketNumber].hash_coll & unchecked(0x80000000))!=0)))
emptySlotNumber = bucketNumber;
// Insert the key/value pair into this bucket if this bucket is empty and has never contained an entry
// OR
// This bucket once contained an entry but there has never been a collision
if ((buckets[bucketNumber].key == null) ||
(buckets[bucketNumber].key == buckets && ((buckets[bucketNumber].hash_coll & unchecked(0x80000000))==0))) {
// If we have found an available bucket that has never had a collision, but we've seen an available
// bucket in the past that has the collision bit set, use the previous bucket instead
if (emptySlotNumber != -1) // Reuse slot
bucketNumber = emptySlotNumber;
// We pretty much have to insert in this order. Don't set hash
// code until the value & key are set appropriately.
#if !FEATURE_CORECLR
Thread.BeginCriticalRegion();
#endif
isWriterInProgress = true;
buckets[bucketNumber].val = nvalue;
buckets[bucketNumber].key = key;
buckets[bucketNumber].hash_coll |= (int) hashcode;
count++;
UpdateVersion();
isWriterInProgress = false;
#if !FEATURE_CORECLR
Thread.EndCriticalRegion();
#endif
#if FEATURE_RANDOMIZED_STRING_HASHING
#if !FEATURE_CORECLR
// coreclr has the randomized string hashing on by default so we don't need to resize at this point
if(ntry > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(_keycomparer))
{
// PERF: We don't want to rehash if _keycomparer is already a RandomizedObjectEqualityComparer since in some
// cases there may not be any strings in the hashtable and we wouldn't get any mixing.
if(_keycomparer == null || !(_keycomparer is System.Collections.Generic.RandomizedObjectEqualityComparer))
{
_keycomparer = HashHelpers.GetRandomizedEqualityComparer(_keycomparer);
rehash(buckets.Length, true);
}
}
#endif // !FEATURE_CORECLR
#endif // FEATURE_RANDOMIZED_STRING_HASHING
return;
}
// The current bucket is in use
// OR
// it is available, but has had the collision bit set and we have already found an available bucket
if (((buckets[bucketNumber].hash_coll & 0x7FFFFFFF) == hashcode) &&
KeyEquals (buckets[bucketNumber].key, key)) {
if (add) {
throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", buckets[bucketNumber].key, key));
}
#if !FEATURE_CORECLR
Thread.BeginCriticalRegion();
#endif
isWriterInProgress = true;
buckets[bucketNumber].val = nvalue;
UpdateVersion();
isWriterInProgress = false;
#if !FEATURE_CORECLR
Thread.EndCriticalRegion();
#endif
#if FEATURE_RANDOMIZED_STRING_HASHING
#if !FEATURE_CORECLR
if(ntry > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(_keycomparer))
{
// PERF: We don't want to rehash if _keycomparer is already a RandomizedObjectEqualityComparer since in some
// cases there may not be any strings in the hashtable and we wouldn't get any mixing.
if(_keycomparer == null || !(_keycomparer is System.Collections.Generic.RandomizedObjectEqualityComparer))
{
_keycomparer = HashHelpers.GetRandomizedEqualityComparer(_keycomparer);
rehash(buckets.Length, true);
}
}
#endif // !FEATURE_CORECLR
#endif
return;
}
// The current bucket is full, and we have therefore collided. We need to set the collision bit
// UNLESS
// we have remembered an available slot previously.
if (emptySlotNumber == -1) {// We don't need to set the collision bit here since we already have an empty slot
if( buckets[bucketNumber].hash_coll >= 0 ) {
buckets[bucketNumber].hash_coll |= unchecked((int)0x80000000);
occupancy++;
}
}
bucketNumber = (int) (((long)bucketNumber + incr)% (uint)buckets.Length);
} while (++ntry < buckets.Length);