.NET中的HashSet原理是什么

这篇文章主要介绍“.NET中的HashSet原理是什么”，在日常操作中，相信很多人在.NET中的HashSet原理是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”.NET中的HashSet原理是什么”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！HashSet是基于哈希表的原理实现的，学习HashSet首先要了解下哈希表。哈希表（hash table, 也叫散列表）是根据key直接访问存储位置的数据结构，它通过一个键值的函数，将所需查询的数据映射到表中一个位置来访问，加快了查找速度。上述函数即为哈希函数，哈希函数应尽量计算简单以提高插入、检索效率；计算得到的地址应尽量分布均匀，以降低哈希冲突；应具有较大的压缩性，以节省内存。常见的哈希函数构造方法有直接定址法、除留余数法、数字分析法等。HashSet采用除留余数法，将元素免费云主机域名的HashCode除以某个常数（哈希表Size）的余数作为地址，常数通常选取一个素数。两个相等的对象的哈希值相同，但两个不等的对象的哈希值是有可能相同的，这就是哈希冲突。处理冲突的方法有开放定址法、链表法、双散列法等。HashSet使用链表法，将冲突元素放在链表中。哈希表是一种用于高性能集合操作的数据结构，它有如下特点：无序、不重复；插入、查找时间复杂度为O(1)；不使用索引；容量不足时自动扩容，但扩容成本高；可提供很多高性能集合操作，如合并、裁剪等；HashSet内置了两个数组，如下。_buckets中存放由哈希函数计算得到的索引值，_buckets中的值从1开始，因此在使用时需要-1。该值即为_entries数组的相对索引，若未发生冲突，指向的值即为待查找元素的相对索引。如果发生了冲突，根据冲突链表也可以快速定位到元素。_entries存放的是Entry对象，Entry类型如下所示。HashCode为元素的哈希值，在查找、插入、删除、扩容等操作时都会用到。Value存储数据。Next在不同时刻有不同的作用，当Entry在列表中时，形成冲突链表，其Next指向冲突链表的下一元素，链表最后一个元素的Next值为-1；若Entry已被列表删除，形成空位链表，其Next指向空位链表的下一元素，空位链表的最后一个元素值为-2。HashSet还有几个关键成员：_count、_freeList、_freeCount。_count表示添加元素数量，注意它并不是实际存储的元素数量，因为在删除元素时未更新它。_freeList为空位链表头，其值指向被删除的_entries索引，_entries[_freeList].Next指向下一空位的相对位置。_freeCount表示空位数量，列表实际存储的元素数量为_count – _freeCount。HashSet提供了多个构造函数重载，如果不传任何参数，不会初始化_buckets和_entries。当添元素时，会调用Initialize(0)。Initialize方法接受一个int参数，该参数表示需要初始化的列表容量。实际初始化的列表容量为大于等于该值的最小素数。取素数作为列表长度是因为该值作为使用除留余数法构造的哈希函数的除数，对素数求余结果分布更均匀，减少了冲突的发生。查找元素时，首先调用元素的GetHashCode方法计算哈希值，然后调用GetBucketRef方法执行哈希函数运算，获得索引。GetBucketRef的返回值-1为真实索引i，若i为-1，则未找到元素。若i>=0，表示列表中存在与待查找元素哈希值相同的元素，但相等的哈希值并不一定表示元素相等，还要进一步判断HashCode，若HashCode相等，再判断元素是否相等，满足则查找到元素，返回_entries的索引i。插入元素时，首先会查找待插入的元素是否存在，HashSet是不重复的，因此若插入元素已存在会直接返回false。若不存在元素，则会寻找存放元素的index。如果存在删除后的空位，则会将元素放到_freeList指向的空位上；如果不存在空位，则按_entries顺序插入元素。找到index后，即可将元素的HashCode及元素赋值到_entries[index]对应字段，当没有冲突时，Next值为-1；若存在冲突，则形成链表，将其添加到链表头，Next指向冲突的下一位置。插入时若列表容量不足，会调用Resize方法进行扩容。扩容后的大小为大于等于原大小2倍的最小素数。获取待扩容的大小后，以新大小重新分配entries内存，并调用Array.Copy方法将原内容拷贝到新位置。由于列表长度变了，因此哈希值会变，因此需要更新_buckets的内容(_entries索引)，同理entry.Next的值也要更新。当删除元素时，首先查找待删除元素是否存在。若哈希值存在冲突，会记录冲突链表的上一索引。查找到元素后，需要更新冲突链表的指针。删除元素后，会更新_freeCount空位数量，并将删除元素索引赋值给_freeList，记录删除空位，添加到空位链表头，其Next指向下一空位的相对位置。插入元素时，会将元素插入到_freeList记录的空位索引处，并根据该空位的Next更新_freeList的值。到此，关于“.NET中的HashSet原理是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注百云主机网站，小编会继续努力为大家带来更多实用的文章！

相关推荐: SpringBoot常见get/post请求参数处理的方法

这篇文章主要介绍了SpringBoot常见get/post请求参数处理的方法的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇SpringBoot常见get/post请求参数处理的方法文章都会有所收获，下面我们一起来看看吧。在定义一个…