楚雄做网站,现代装修风格效果图,搜索引擎哪个好,阿里建站服务1. 引言 哈希表#xff08;Hash Table#xff09;的应用近两年才在NOI中出现#xff0c;作为一种高效的数据结构#xff0c;它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点#xff0c;就是把数据的存储和查找消耗的时间大大降低#xff0c;几乎可以看 成是常数时…1. 引言 哈希表Hash Table的应用近两年才在NOI中出现作为一种高效的数据结构它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低几乎可以看 成是常数时间而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越 多的情况下用空间换时间的做法是值得的。另外编码比较容易也是它的特点之一。 哈希表又叫做散列表分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构本文中的“哈希表”仅指“闭散列”关于其他方面读者可参阅其他书籍。 2. 基础操作 2.1 基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数哈希函数 也叫做散列函数使得每个元素的关键字都与一个函数值即数组下标相对应于是用这个数组单元来存储这个元素也可以简单的理解为按照关键字为每一 个元素“分类”然后将这个元素存储在相应“类”所对应的地方。 但是不能够保证每个元素的关键字与函数值是一一对应的因此极有可能出现对于不同的元素却计算出了相同的函数值这样就产生了“冲突”换句话说就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 总的来说“直接定址”与“解决冲突”是哈希表的两大特点。 2.2 函数构造 构造函数的常用方法下面为了叙述简洁设 h(k) 表示关键字为 k 的元素所对应的函数值a) 除余法 选择一个适当的正整数 p 令 h(k ) k mod p 这里 p 如果选取的是比较大的素数效果比较好。而且此法非常容易实现因此是最常用的方法。b) 数字选择法 如果关键字的位数比较多超过长整型范围而无法直接运算可以选择其中数字分布比较均匀的若干位所组成的新的值作为关键字或者直接作为函数值。 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S 则当 h(k) 已经存储了元素的时候依次探查 (h(k)i) mod S , i1,2,3…… 直到找到空的存储单元为止或者从头到尾扫描一圈仍未发现空单元这就是哈希表已经满了发生了错误。当然这是可以通过扩大数组范围避免的。 转载于:https://www.cnblogs.com/wspblog/p/4931238.html
