A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 韩慧阳 中级黑马   /  2012-5-16 15:59  /  2365 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

谁能给我具体说说哈希表。
哈希表在内存中是怎么实现的啊??哈希值和每个哈希值所对应的数据(地址)是怎样的映射关系??都分别存放在哪段内存上呢??

4 个回复

倒序浏览
   哈希表与哈希方法是选取某个函数,依该函数按关键字计算元素的存储位置,按此值存放;在查找时,由同一个函数对给定值x计算地址,将x与地址单元中的元素关键字进行比较,确定是否查找成功。
  在构造哈希函数的时候,必须要构造好,有时候会发生地址冲突,这是不可避免的,但是在构造哈希函数时,要尽可能减少发生地址冲突的次数。
例如有:关键字集合序列{100,300,500,700,800,900}
   可以构造哈希函数为:Hash(key)=key/100
在内存中的格式如下:
     0        1       2        3        4         5       6        7         8        9

        100          300              500                 700     800    900

回复 使用道具 举报
哈希表是一种数据结构,它提供了快速的插入操作和查找操作。其基于数组来实现。
哈希值和每个哈希值所对应的数据(地址)的映射关系有不同的哈希表的构造方法决定,这个在数据结构里有详细的介绍。主要包括包括直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
哈希表会有冲突的发生,即不能保证每个数据都映射到数组的空白单元。解决办法有开放地址法 ,链地址法。
回复 使用道具 举报
谢谢了,我还是找出我的数据结构再看一遍吧!
回复 使用道具 举报
如你想深入理解,应去看算法,或数据结构的相关章节。哈希表的思想:每个元素作为变量,通过一定的函数关系计算出函数的值,把这个值作为数组的下标,将元素存入对应的数组元素中。那函数称为哈希函数,函数的值称为哈希地址。
  例如,有4个数:1,30,5,12,假设用“%10"为哈希函数,那么哈希运算后得值:1,0,5,2。“%10"后的值有10种可能,所以设10个存储地址,0就保存到地址0,1就保存到地址1,2就保存到地址2,5就保存到地址5。这样做的好处是,查找非常快,如找12,12%10=2,就到地址2 去取,什么索引查找、折半查找都不能相比,特别是数据量大时。当然哈希函数是很复杂的,不会取余那么简单。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马