随笔 - 13  文章 - 36  trackbacks - 0
<2009年10月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(2)

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

                                                                           哈希结构

                                                                                                         C++博客   Alex-Lee   2009-10-21

       哈希结构在处理大量数据时具有很好的优势,在插入,查询,删除等操作上具有常量的时间复杂度O(1)。使用范围是数据集具有自然数上的关键字域(不是自然数也需要能够转为自然数域),通过哈希函数将关键字映射到寻址数组的槽。由于关键字域U[0...n]与寻址数组[0...m]中,总是n>m,也就是说,总有多个关键字对应一个槽。这个碰撞就需要通过一些方法改变。可以通过拉链法(链表法)和开放地址法。对于拉链法中,链表不能太长,否则影响速度,最好控制在10个元素之内,这样就要去寻址数组长度m>= n/10,这样就会多消耗些空间。为了让每个链表长度基本一致,就需要选择合适的关键字到槽的映射函数,即哈希函数。在选取哈希函数方面有3种方法:乘法、除法、全域法。乘法对m值选取上要求比较强,而除法对m值没有特别要求,全域法则是在一组哈希函数中,运行时每次随机的选取一个哈希函数。因此,全域法在随机上具有更好的均匀分布,性能最好。下面是拉链法的实现:
1,哈希节点:
2,创建哈希表
 1//拉链技术杂凑法
 2static const int m = 100701;
 3int hash_create(HASH_TABLE *pht)
 4{
 5    HASH_TABLE ht;
 6    int i;
 7    ht = (HASH_TABLE) LM_MALLOC(sizeof(DATA_NODE) * m);
 8    if (!ht)
 9    {
10        return -1;
11    }

12    for (i = 0; i < m;++i)
13    {
14        ht[i].data = 0;
15        ht[i].length = 0;
16        ht[i].key = -1;
17        ht[i].prev = 0;
18        ht[i].next = 0;
19    }

20    *pht = ht;
21    return 0;
22}
3,销毁哈希表
4,插入元素
5,查询
6,删除
7,哈希函数
8,测试
由于耗费内存比较大,测试100W整数的插入操作是4秒左右,查询操作是2秒左右,删除时0.4秒左右,1000w整数的上述操作分别是47s,22s,3.3s。
看起来效率还是不错。
算法实现代码
posted on 2009-10-22 00:31 Alex-Lee 阅读(1867) 评论(5)  编辑 收藏 引用

FeedBack:
# re: 哈希结构 2009-10-22 08:47 fcc
楼主你确定你代码通过编译了?看到2,创建哈希表看不下去了。HASH_TABLE 哪定义的?ht变量究竟是HASH_TABLE类型还是HASH_TABLE* 类型?莫非有某个malloc函数返回值竟然不是指针类型的?看不明白
  回复  更多评论
  
# re: 哈希结构 2009-10-22 08:57 fcc
@fcc
又看了看,猜出来了,估计HASH_TABLE是DATA_NODE*型。这样可以解释  回复  更多评论
  
# re: 哈希结构 2009-10-22 09:14 李佳
我感觉我应该去看看数据结构的书了...呵呵 最近处理数据怎么忘了哈希表了   回复  更多评论
  
# re: 哈希结构 2009-10-22 12:10 Vincent
^_^恩.hash是的确很有意思的.
我更喜欢通过构造一个简单的hash来剔除一些明显的无关解,来缩小筛选范围..
就象是Rabin-Karp匹配里的那个用法..
甚至觉得这样的用法更多  回复  更多评论
  
# re: 哈希结构 2009-10-22 18:54 Alex-Lee
@fcc
程序经过编译,没有什么问题。LM_MALLOC等是我写的一个内存分配封装函数,用于将所有的分配的内存地址使用单链表连接,在debug时,用于发现内存泄露问题,release时直接就是malloc。这是我实现的一个发现内存泄露的方法,灵感来源于《微软C编程精粹》。
HASH_TABLE是DATA_NODE*型。不好意思,在摘代码时把
typedef DATA_NODE* HASH_TABLE;
给忘掉了。谢谢提醒。

@李佳
@Vincent
受金融危机影响,今年工作不怎么忙。几乎将数据结构与算法忘得差不多了。这阵子看《算法导论(中文版)》潘金贵版。这本书讲得很好,有广度,也很有深度。数学基本忘得差不多了,其中关于数学论证时间复杂度的相关方面看得马马虎虎。哈希的开放地址法就没怎么看明白。谢谢大家的回复,有不对的地方,请大家指点。  回复  更多评论
  
# re: 哈希结构 2009-10-24 11:43 Goteet
Data Structure for Game Developer 中hash那里讲的很详细啊  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理