问题:要处理200000个自然数,统计每个不同的自然数出现的次数(不同的自然数个数小于10000)。
算法思路:将N个不同的键值对nodePair(num,value)存在一张HashTable中,可以达到O(1)的存取效率(不考虑冲突)
1)使用什么样的HASH函数,这里使用fibonacci散列法。
HashCode=n*265435769>>18。为什么是左移18位,因为2^14=16384>10000,满足10000个不同自然数的要求
2)如何处理寻址冲突,这里使用顺延法。当然顺延会导致存取的效率略慢。
代码如下,参考题目南开onlinejudge:1833,自然数统计
#include<iostream> #include<string.h> #include<algorithm> using namespace std; class nodePair { public: unsigned num; unsigned value; nodePair() { } nodePair(unsigned num,unsigned value) { this->num=num; this->value=value; } }; const unsigned fibonacci=2654435769; const unsigned tableMax=21911; nodePair* HashTable[tableMax]; unsigned list[200002]; unsigned getHashCode(unsigned n) { unsigned a=(n*fibonacci)>>18; return a; } void putHashTable(unsigned code,unsigned c) { if(HashTable[code]!=NULL) { if(HashTable[code]->value==c) HashTable[code]->num++; else { code=(code+1)%tableMax; putHashTable(code,c); } } else { nodePair* p=new nodePair(1,c); HashTable[code]=p; } } unsigned findHashTable(unsigned code,unsigned c) { if(HashTable[code]==NULL) return 0; else { if(HashTable[code]->value==c) return HashTable[code]->num; else { code=(code+1)%tableMax; return findHashTable(code,c); } } } void initHashTable() { for(int i=0;i<tableMax;i++) { if(HashTable[i]!=NULL) { delete HashTable[i]; HashTable[i]=NULL; } } } int main() { int m,n; unsigned c; for(int i=0;i<tableMax;i++) HashTable[i]=NULL; while(cin>>n&&n) { initHashTable(); for(int i=0;i<n;i++) { scanf("%u",&c); list[i]=c; unsigned code=getHashCode(c); putHashTable(code,c); //HashTable[getHashCode(c)]++; //cout<<c<<"'s HashCode="<<getHashCode(c)<<endl; //cout<<"count is "<<HashTable[getHashCode(c)]->num<<endl; } sort(list,list+n); int flag=0;; while(1) { cout<<list[flag]<<" "; unsigned code=getHashCode(list[flag]); unsigned q=findHashTable(code,list[flag]); cout<<q<<endl; flag=flag+q; if(flag>=n) break; } } return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1242http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1652http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1720http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1325Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 875首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1289朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1677题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2497AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1196二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2144网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 873trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 924bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1080我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1667LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2853zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1376染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 763线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 783快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3087斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1292本文大量 ...
相关推荐
HashTable源码
WinFormHashTable最简单用法,.net hashtable ,hashtable ,hashtable用法
自己写的json字符串转hashtable,或者把hashtable转为json字符
hashMap和hashTable的区别,大家可以下载学习学习。
记得刚毕业那会准备面试,看过不少面试题,里面有个说出HashMap和HashTable不同的题目,我那会面试的时候也遇到不少次这个问题,还隐约记得当时的回答是这样的: HashTable是比较旧的版本;HashTable是线程安全的,...
C#之Json字符串转换Hashtable,DataTable,DataSet方法和反转换方法.
经典讲解List和ArrayList和Vector和HashTable和HashMap区别
HashTable不支持空键值对! 而HashMap支持空键值对!
Java集合专题总结:HashMap和HashTable源码学习和面试总结 本文总结了Java集合专题中的HashMap和HashTable,涵盖了它们的源码学习和面试总结。HashMap是一种基于哈希表的集合类,它的存储结构是一个数组,每个元素...
利用asp.net遍历hashtable中的值
java Hashtable的泛型化 java Hashtable的泛型化 java Hashtable的泛型化
Hashtable存储数据例子,希望大家多多指教
// Hashtable2.cs // 给Hashtable添加元素的示例 using System; using System.Collections; public class Test { public static void Main() { Hashtable table = new Hashtable(); table.Add("Sunday", "星期...
该文档实现了Hashtable在C#中的常用的函数
hashtable和hashmap的区别
各种语言的Hash算法都很多,这是用纯C语言定情的Hash算法,不包含任何其他相关的库。... * create_hashtable * hashtable_insert * hashtable_search * hashtable_remove * hashtable_count * hashtable_destroy
今天小编就为大家分享一篇关于HashMap和HashTable底层原理以及常见面试题,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
易语言 HashTable 数据效验算法,使用内联汇编,数次优化。速度快且稳定
初级程序员面试经常问道的问题,HashMap与HashTable区别,希望有帮助