.NET中的HashSet及其原理，能否详细解析一下？

本文共计2318个文字，预计阅读时间需要10分钟。

目录哈希表原理HashSet实现总结参考文献在.NET中，System.Collection及System.Collection.Generic命名空间提供了系列集合类HashSet定义

目录

• 哈希表原理
• HashSet实现
• 总结
• 参考文章

在.NET中，System.Collection及System.Collection.Generic命名空间中提供了一系列的集合类，HashSet定义在System.Collections.Generic中，是一个不重复、无序的泛型集合，本文学习下HashSet的工作原理。

哈希表原理

HashSet是基于哈希表的原理实现的，学习HashSet首先要了解下哈希表。

哈希表（hash table, 也叫散列表）是根据key直接访问存储位置的数据结构，它通过一个键值的函数，将所需查询的数据映射到表中一个位置来访问，加快了查找速度。

上述函数即为哈希函数，哈希函数应尽量计算简单以提高插入、检索效率；计算得到的地址应尽量分布均匀，以降低哈希冲突；应具有较大的压缩性，以节省内存。常见的哈希函数构造方法有直接定址法、除留余数法、数字分析法等。HashSet采用除留余数法，将元素的HashCode除以某个常数（哈希表Size）的余数作为地址，常数通常选取一个素数。

两个相等的对象的哈希值相同，但两个不等的对象的哈希值是有可能相同的，这就是哈希冲突。处理冲突的方法有开放定址法、链表法、双散列法等。HashSet使用链表法，将冲突元素放在链表中。