没有合适的资源?快使用搜索试试~ 我知道了~
C++哈希表使用的好文章-Hash_Map
4星 · 超过85%的资源 需积分: 18 245 下载量 166 浏览量
2010-05-17
12:38:24
上传
评论 2
收藏 39KB DOC 举报
温馨提示
试读
5页
hash_map基于hash table(哈希表)。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。
资源推荐
资源详情
资源评论
参考文章
条条大路通罗马,为什么你不随便选一条?
为什么需要
用过 吧? 提供一个很常用的功能,那就是提供 的存储和查找功能。例如,
我要记录一个人名和相应的存储,而且随时增加,要快速查找和修改:
岳不群-华山派掌门人,人称君子剑张三丰-武当掌门人,太极拳创始人东方不败-第一
高手,葵花宝典这些信息如果保存下来并不复杂,但是找起来比较麻烦。例如我要找 张
三丰的信息,最傻的方法就是取得所有的记录,然后按照名字一个一个比较。如果要速度
快,就需要把这些记录按照字母顺序排列,然后按照二分法查找。但是增加记录的时候同
时需要保持记录有序,因此需要插入排序。考虑到效率,这就需要用到二叉树。讲下去会
没完没了,如果你使用 的 容器,你可以非常方便的实现这个功能,而不用关心其
细节。关于 的数据结构细节,感兴趣的朋友可以参看学习 之数据结构
基础。看看 的实现
! !"" 增
加。。。#岳不群$%华山派掌门人,人称君子剑!#张三丰$%武当掌
门人,太 极拳 创始 人 !# 东方 不败 $% 第一高手,葵花宝典!"" 查找。。
&'('岳不群)*%'))+,不觉得用起来很 吗?而且效率很高,
- 万条记录,最多也只要 . 次的 / 的比较,就能找到你要找的记录!. 万
条记录事,也只要用 .- 次的比较。
速度永远都满足不了现实的需求。如果有 - 万条记录,我需要频繁进行搜索时,. 次比
较也会成为瓶颈,要是能降到一次或者两次比较是否有可能?而且当记录数到 . 万的时
候也是一次或者两次的比较,是否有可能?而且还需要和 一样的方便使用。
答案是肯定的。这时你需要 虽然 目前并没有纳入 011标准模板库中,
但几乎每个版本的 都提供了相应的实现。而且应用十分广泛。在正式使用 之
前,先看看 的原理。
-数据结构: 原理
这是一节让你深入理解 的介绍,如果你只是想囫囵吞枣,不想理解其原理,你
倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。
基于 2(哈希表)。哈希表最大的优点,就是把数据的存储和查找消耗
的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当
前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也
是它的特点之一。
其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函
数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标, 值)
相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一
个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。
但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同
的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素
arthaslonely
- 粉丝: 1
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
- 4
前往页