1.Hashtable 到底是什么
2.为什么要用到Hashtable
3.Hashtable 和 Dictionary 和什么不同
说到集合,他有可能是代码中用到最多的东西,C#集合的确是一个很好用的类型,
哪么,何时会用到?
for example:
1.当我要放置一组数据
2.当我们需要一个动态可变长的数组
3.需要通过一个键值去索引数据项的一组数据
其实在某些情况下.我们完全可以不用集合,用数组同样可以实现,但为了方便,集合成为首先.
哪么集合到底是什么,他内部又怎么工作?
集合就是数组,他是数组的封装,在他的内部实现了数组动态的更改长度,
我们都知道数组在定义的时候已经确定的长度,但怎么能动态更改长度呢.这里就是集合内部的办法实现
Hashtable 不只是实现了动态改动数组长度,更重要一点他是散列键值.将数据均匀分布到数组中
Hashtable数据是存放在内部一个成员数组中,这个数组的类型为Bucket类型
Bucket类型包括以下三个成员
Key Object类型的键
Val Object类型的值
Hash_Coll Key通过Hash算法得出的数值
当Hashtable被实例化时,并不会立刻在内存中开辟Bucket数组空间,它的实例方法有几个重载,其中一个重要的参数就是增量因子,增量因子的默认值为0.72这是微软推荐的一个数值。
接下来当第一个数据被加入Hashtable中，成员方法Resize去计算数组的长度而这个长度受增量因子的影响，最终计算出数组的大小
当数组计算出大小后，接下来怎么将数据放入数组中.放在什么位置这两个问题是Hashtable中实现的最重要方法,也是清楚分析Hashtable中逻辑算法最重要的地方.
Hashtable 表中单个项所在的索引位置是由key的散列值所决定，
1.F(n) = F1(n)
2.F(n) = F1(n) + F2(n)
以下两种方法是hash取值的算法,方法一是默认算法，假如方法一结果位置已被占用,哪么使用方法二,方法二在方法一的基础上使用一个增量函数使之继续偏移,直到找到空位置.这种方式叫 "开放定址法"
所以说hashtable 冲突出现的次数越少,哪么数据写入效率就越高,哪么算法直接影响到冲突的次数,
当索引项的时个是一个相似过程,首先使用 方法一计算出位置,然后通过比较hash_coll的值确定是否为要找到数据.因为hash_coll保存的是hash原始值,所以做对比可以很快判断,如果并非我们要找的数据.哪么继续使用增量函数直到找到数据为止.
下篇我们讨论一下hashtable 的内部算法.