Hashtable源码剖析
Hashtable实现一个哈希表（也叫散列表），将键映射到相应的值。任何非 null 对象都可以用作键。
哈希表是根据关键码值进行访问的数据结构，它是通过把关键码值映射到表中对应的一个位置来访问记录值，以加快查询速度（给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。）。
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素。哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，所以在冲突发生时，必须有相应的解决方案。而发生冲突的可能性又跟以下两个因素有关：
装填因子α：所谓装填因子是指合希表中已存入的记录数n与哈希地址空间大小m的比值，即 α=n / m ，α越小，冲突发生的可能性就越小；α越大，冲突发生的可能性就越大（α取值范围0.1f ~ 1.0f）。这很容易理解，因为α越小，哈希表中空闲单元的比例就越大，所以待插入记录同已插入的记录发生冲突的可能性就越小；反之，α越大，哈希表中空闲单元的比例就越小，所以待插入记录同已插入记录冲突的可能性就越大；另一方面，α越小，存储桶的利用率就越低；反之，存储桶的利用率就越高。为了既兼顾减少冲突的发生，又兼顾提高存储空间的利用率，通常把α控制在0.6～0.9的范围之内，C#的HashTable类把α的值定为0.72。
- 与所采用的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，就可能使哈希地址集中于某些区域，从而加大冲突发生的可能性。
哈希冲突解决:
冲突解决技术可分为两大类：开散列法（又称为链地址法） 和 闭散列法（又称为开放地址法） 。
哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内（一个数组空间或多个数组空间）：
- 闭散列法（开放地址法）
闭散列法是把所有的元素存储在哈希表数组中。当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程称为探测。上述方法可用如下公式表示：
i=( h(key) + di ) % m i=1，2，…，k (k≤m-1)
其中h(key)为哈希函数；m为哈希表长；di为增量的序列。根据di取值的不同，可以分成几种探测方法，下面介绍的是Hashtable所使用到的双重散列法。
双重散列法（DoubleHashing）(再哈希?)
双重散列法是经典的数据表结构（T）。设 n 为存储在 T 中元素的数目，m为T的容量，则T的加载因子为
α= n / m， α：1 > α >0。
它是以关键字的另一个散列函数值作为增量。设两个哈希函数为：h_1 和 h_2，则得到的探测序列为：
h(i,k) = ( h_1(k) + i * h_2(k) ) % m，m为哈希表的容量，i： 1 < i < m - 1。
定义h_2的方法较多，但无采用什么方法都必须使h_2(k)的值和m互素（又称互质，表示两数的最大公约数为1，或者说是两数没有共同的因子，1除外）才能使发生冲突的同义词地址均匀地分布在整个哈希表中，否则可能造成同义词地址的循环计算。若m为素数，则h_2取1至m-1之间的任何数均与m互素。
Hashtable的实现
Hashtable实现了IDictionary，在命名空间System.Collections中，表示根据键的哈希代码进行组织的键/值对的集合。
// 基本成员
internal const Int32 HashPrime = 101;// 固定的素数
private const Int32 InitialSize = 3;//哈希表的默认容量
private struct bucket
{
public Object key;//键
public Object val;//值
// 是一个Int32类型，它的最高位是符号位，为“0”时，表示这是一个正整数；
// 为“1”时表示负整数。hash_coll使用最高位表示当前位置是否发生冲突，
// 正数表示未发生冲突；负数表示当前位置存在冲突。
// 之所以专门使用一个位用于存放哈希码并标注是否发生冲突，主要是为了提高哈希表的运行效率。
public int hash_col;//哈希码
}
private bucket[] buckets;// 数据桶, 用于存储哈希表中的元素
private int count;//元素总数
private int occupancy;//冲突次数
private int loadsize;// 装载容量值，相当于一个阈值，达到了这个数值，将对哈希表进行扩容；
private float loadFactor;// 哈希表中的元素占有数据桶空间的一个比率，这个比例直接决定了哈希表在什么时候进行扩容；
private volatile int version;
private volatile bool isWriterInProgress;
private ICollection keys;
private ICollection values;
在Hashtable中的两个哈希函数分别为：
h_1(k) = k.GetHashCode()：第一个哈希函数直接用默认的GetHashCode()方法；h_2(k) = (1 + ((h_1(k) * HashPrime) % (hashsize - 1)))：HashPrime为私有成员101的素数，hashsize为哈希表长度。之所以会进行取模运算是为了保证结果值的范围在[0, hashsize - 1]
private uint InitHash(Object key, int hashsize, out uint seed, out uint incr)
{
//取正数值,第一和哈希函数h_1(k)
uint hashcode = (uint) GetHash(key) & 0x7FFFFFFF;
seed = (uint) hashcode;
//第二个哈希函数h_2(k)的增量
incr = (uint)(1 + ((seed * HashPrime) % ((uint)hashsize - 1)));
return hashcode;
}
Hashtable Add操作
Add(Object, Object)：将带有指定键和值的元素添加到 Hashtable 中。
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)
{
//在元素总数大于100之后，判断冲突计数大于装载量时，将HashTable重新哈希
rehash();
}
uint seed;// seed = (uint) hashcode;
uint incr;// 第二个哈希函数h_2(k)的增量
uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
int ntry = 0;//寻址次数，不得大于等于哈希表容量
int emptySlotNumber = -1; //用于记录第一个寻址到的可用插槽
// 算出对应的哈希桶
int bucketNumber = (int) (seed % (uint)buckets.Length);
do {
//有冲突的空插槽
if (emptySlotNumber == -1 && (buckets[bucketNumber].key == buckets) && (buckets[bucketNumber].hash_coll < 0))
emptySlotNumber = bucketNumber;
//正常的空插槽
if ((buckets[bucketNumber].key == null) ||
(buckets[bucketNumber].key == buckets && ((buckets[bucketNumber].hash_coll & unchecked(0x80000000))==0)))
{
//将元素放入寻址到的第一个可用插槽
if (emptySlotNumber != -1)
bucketNumber = emptySlotNumber;
Thread.BeginCriticalRegion();
isWriterInProgress = true;
buckets[bucketNumber].val = nvalue;
buckets[bucketNumber].key = key;
buckets[bucketNumber].hash_coll |= (int) hashcode; // 用符号位记录是否冲突
count++;
UpdateVersion();
isWriterInProgress = false;
Thread.EndCriticalRegion();
if(ntry > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(_keycomparer))
{
if(_keycomparer == null || !(_keycomparer is System.Collections.Generic.RandomizedObjectEqualityComparer))
{
_keycomparer = HashHelpers.GetRandomizedEqualityComparer(_keycomparer);
rehash(buckets.Length, true);
}
}
return;
}
//替换更新（此处值变更，Update操作），若添加重复的键，则抛出异常
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));
}
Thread.BeginCriticalRegion();
isWriterInProgress = true;
buckets[bucketNumber].val = nvalue;
UpdateVersion();
isWriterInProgress = false;
Thread.EndCriticalRegion();
if(ntry > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(_keycomparer))
{
if(_keycomparer == null || !(_keycomparer is System.Collections.Generic.RandomizedObjectEqualityComparer))
{
_keycomparer = HashHelpers.GetRandomizedEqualityComparer(_keycomparer);
rehash(buckets.Length, true);
}
}
return;
}
//存在冲突 将哈希值设置为负数
if (emptySlotNumber == -1) {
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);
//插槽已满，将元素插入第一个寻址到的可用插槽
if (emptySlotNumber != -1)
{
Thread.BeginCriticalRegion();
isWriterInProgress = true;
buckets[emptySlotNumber].val = nvalue;
buckets[emptySlotNumber].key = key;
buckets[emptySlotNumber].hash_coll |= (int) hashcode;
count++;
UpdateVersion();
isWriterInProgress = false;
Thread.EndCriticalRegion();
if(buckets.Length > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(_keycomparer))
{
if(_keycomparer == null || !(_keycomparer is System.Collections.Generic.RandomizedObjectEqualityComparer))
{
_keycomparer = HashHelpers.GetRandomizedEqualityComparer(_keycomparer);
rehash(buckets.Length, true);
}
}
return;
}
Contract.Assert(false, "hash table insert failed! Load factor too high, or our double hashing function is incorrect.");
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed"));
}
HashTable 获取值/设置值
索引器：Hashtable中通过索引器来进行获取值 / 设置值。
哈希表的读的操作有三个步骤 ︰
- 计算哈希值和找到的插槽号。
- 比较哈希码，如果相等，请转至步骤 3。否则读失败，结束。
- 比较关键字，如果相等，返回包含在存储桶中的值。否则读失败，结束。
在索引器的源代码中 有两个do while循环，最外面的循环用于遍历冲突链，嵌套的循环用于防止数据读脏。
public virtual Object this[Object key]
{
get {
if (key == null) {
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Contract.EndContractBlock();
uint seed;
uint incr;
//生成一个数据桶的结构副本，防止其他线程同一时间对同一个结构进行调整。
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;
int spinCount = 0;
do {
currentversion = version;
b = lbuckets[bucketNumber];
//这里使用线程休眠是为了防止资源争夺而导致CPU过度消耗
if( (++spinCount) % 8 == 0 ) {
Thread.Sleep(1);
}
//若有其他线程在做调整，等待完成再获取最新的值
} 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);
}
}
//比较函数
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);
}
HashTable 移除元素
Remove(Object)：从 Hashtable 中移除带有指定键的元素。
Hashtable删除元素 分两种情况处理：
- 正常插槽，将key赋空引用，hash_col赋值0。
- 冲突插槽，将key指向buckets数据桶，将hash_col赋值-2147483648 (同时赋值key和hash_col是为了与哈希码为0的冲突插槽区分开）。
public virtual void Remove(Object key)
{
if (key == null) {
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Contract.EndContractBlock();
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.");
uint seed;
uint incr;
uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
int ntry = 0;
bucket b;
int bn = (int) (seed % (uint)buckets.Length);
//第一次循环若找不到值，那么表示有冲突链 或 键值不存在
do {
b = buckets[bn];
if (((b.hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals (b.key, key)) {
Thread.BeginCriticalRegion();
isWriterInProgress = true;
//正常插槽哈希码为0 / 冲突插槽哈希码为负数
buckets[bn].hash_coll &= unchecked((int)0x80000000);
if (buckets[bn].hash_coll != 0)
{
//冲突插槽的key指向buckets
buckets[bn].key = buckets;
}
else
{
//正常插槽的key赋空引用
buckets[bn].key = null;
}
buckets[bn].val = null;
count--;
UpdateVersion();
isWriterInProgress = false;
Thread.EndCriticalRegion();
return;
}
bn = (int) (((long)bn + incr)% (uint)buckets.Length);
//循环冲突链
} while (b.hash_coll < 0 && ++ntry < buckets.Length);
}
