- Hash哈希冲突的方法中通常有：开放定址法、再哈希法、链地址法、建立一个公共溢出区等。Dictionary使用的解决冲突方法是拉链法
- 拉链法的原理：
- Dictionary 是以数组为底层数据结构的类。当我们实例化 new Dictionary() 后，内部的数组是0个数组的状态。与 List 组件一样，Dictionary 也是需要扩容的，会随着元素数量的增加而不断扩容。
- Add接口的实现。Add 接口就是 Insert 的代理，首先在加入数据前需要对数据结构进行构造，首次定义size为3，当需要扩容时，系统会从预定义的质数序列中选择下一个更大的质数（如 7、17、31、67 等），而非简单翻倍。3->7->17->37->…. 底层数据结构的大小是按照这个数值顺序来扩展的，除非你在创建 Dictionary 时，先定义了他的初始大小，指定的初始大小也会先被 GetPrime 计算该分配的数量最终得到应该分配的数组大小。这和 List 组件的分配方式一模一样。
- Remove部分。删除的过程和插入的过程比较相似，因为要查找到Key元素所在位置，所以再次将Key值做哈希操作也是难免的，然后类似沿着拉链法的模式寻找与关键字匹配的元素。Remove 接口相对 Add 接口简单的多，同样用哈希函数 comparer.GetHashCode 再除余后得到范围内的地址索引，再做余操作确定地址落在数组范围内，从哈希索引地址开始，查找冲突的元素的Key是否与需要移除的Key值相同，相同则进行移除操作并退出。注意源码中，Remove 的移除操作并没有对内存进行删减，而只是将其单元格置空，这是为了减少了内存的频繁操作。
- ContainsKey 是一个查找Key位置的过程。它调用了 FindEntry 函数，FindEntry 查找Key值位置的方法跟我们前面提到的相同。从用Key值得到的哈希值地址开始查找，查看所有冲突链表中，是否有与Key值相同的值，找到即刻返回该索引地址。
- TryGetValue 尝试获取值的接口与 ContainsKey 同样，他调用的也是FindEntry的接口，来获取Key对应的Value值。
- 对[]操作符的重定义在重新定义[]符号的代码中，获取元素时也同样使用 FindEntry 函数，而 Set 设置元素时则使用与 Add 调用相同的 Insert函数，它们都是同一套方法，即哈希拉链冲突解决方案。
- 从源码剖析来看，哈希冲突的拉链法贯穿了整个底层数据结构。因此哈希函数是关键了，哈希函数的好坏直接决定了效率高低。
- Dictionary 同List一样并不是线程安全的组件，Hashtable在多线程读写中是线程安全的，而 Dictionary 不是。如果要在多个线程中共享Dictionaray的读写操作，就要自己写lock以保证线程安全。
- 由数组构成，并且由哈希函数完成地址构建，由拉链法冲突解决方式来解决冲突。从效率上看，同List一样最好在 实例化对象时，即 new 时尽量确定大致数量会更加高效，另外用数值方式做Key比用类实例方式作为Key值更加高效率。从内存操作上看，大小以3->7->17->37->….的速度，每次增加2倍多的顺序进行，删除时，并不缩减内存。如果想在多线程中，共享 Dictionary 则需要进行我们自己进行lock操作。
暂无评论