问一个哈希表处理冲突的有关问题

问一个哈希表处理冲突的问题
问题1：哈希表如果冲突太多了怎么办，使用哪种方法解决更好？怎么解决？
问题2：哈希表很小，数据太多的话怎么办，怎么存储？
希望各位能回答得详细点，感激不尽！ 存储
[解决办法]
我也是初学者，感觉冲突太多应该用链表表示，又叫开链，就是把冲突的元素放到一个链表上，貌似stl上用的就是这种表示方法，你的两个问题感觉区别不打啊
[解决办法]

引用:

问题1：采用拉链法，将h（k）相同的关键字都统一放到一个链中。这个数据结构上由讲的 
问题2:哈希表很小，数据太多可能引起很大的冲突，方法类似于拉链法，建一个溢出表，专门用来存放上述哈希表中放不下的记录

数据太多就可能会有冲突，所以需要将这些冲突的关键字存起来。
拉链法的好处
  拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
　
  由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
　
  开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
 
  当将冲突的关键字插入到链中是很快的，因为是在链的头部插入，所以时间复杂度O(1)。

  如果关键字分布较均匀的话，假设关键字有n个，哈希表的大小为m,那平均的话差不多每个链有n/m个元素，所以查找关键字的时间复杂度为O（1+ n/m) ,查找很快了 

你可以看下这个文章，里面不仅有个百度笔试题，分析的很好，并且详细介绍了哈希，并给出了实现代码
http://blog.csdn.net/penaiyan/article/details/9165503

查看更多 下一篇