-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
Vivian
2018-05-15
来源 ：
阅读 842
评论 0
摘要：本文主要介绍了C++语言的一些情况，通过具体的案例说明，让我们从中学到C++语言的一些重点，让我们在C++语言这条路上走得更远，更加熟练的完成这些代码。
本文主要介绍了C++语言的一些情况，通过具体的案例说明，让我们从中学到C++语言的一些重点，让我们在C++语言这条路上走得更远，更加熟练的完成这些代码。
关于hash table的简单了解
hash table是一种可以提供对任何有名项的存取、删除操作的技术。它的操作对象是有名项，是一种dictionary(字典结构)。通过该技术可以使得对元素集的基本操作的时间达到常量级。
hashtable的关键在于映射函数hash function(哈希散列函数)能够实现有名项的个体差异转换为映射值的不同，并且保持该序列(即索引)的大小是可接受的。
在hash function中有一个问题，不同元素可能得到相同的映射，这被称之为哈希碰撞。
解决方法包括：linear probing(线性探测)、quadratic probing(二次探测)、separate chaining(开链)等。这些不同的解决方法都能够解决这一问题，但他们的loading factor(负载系数)不同，除separate chaining外，值都在0-1之间。
在 linear probing中，值得注意的是在hash table中，元素的删除是惰性的，即实际上是一种标记删除，正真删除是在表被rehashing时进行的。 linear probing中有一个问题是，随着主体元素的增加，每次增加新的元素，需要解除碰撞的次数会越来越大。这被称之为primary clustering(主体集团)问题。
quadratic probing可以很好的解决primary clustering问题。quadratic probing解决哈希碰撞的原理是：F(i)=i^2。quadratic probing解决了primary clustering问题，但会带来secondary clustering(次集团)问题，解决办法是double hashing(复式散列)。
在separate chaining中，在碰撞点处生成list，每次产生碰撞，就依照某种规则将元素插入相应list。
hash table的合理使用会使我们对数据的操纵更有效率。
本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！
喜欢 | 0
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
