黑马程序员技术交流社区

标题: 哈希存储原理，待完善…… [打印本页]

作者: 花心々小土豆 时间: 2013-6-8 19:22
标题: 哈希存储原理，待完善……
看了论坛好多人都问有关哈希存储的问题！我觉得找个新的地方，统一大家对哈希存储的疑惑，下面是我总结的，有错的地方请大家一起改正，大家有其他想法都发表下……下面来一个数据结构中的哈希表存储的标准定义：
以线性表中的每个元素的某个数据项（最好是关键字）Key为自变量，使用一种事先选定的函数H(Key)计算出函数值，将该值解释为一块连续存储空间（如数组空间）的单元地址（如数组的下标），将数据元素存储到该单元中。
下面说点大家都能听懂的，假如在a[10]中存入1，2，4，5，7值，哈希表会事先选定一个函数，假设该函数为H(Key)=key*3，即每个要存如的值先乘以3，然后再和数组大小求余，找到对应下标存入。这个函数我们可以自己设置（不一定要乘以某个数，可以加入平方，立方，求余，怎么爽怎么来，目的是为了避免两个值对应同一个下标产生冲突），乘以300都没问题，因为和数组求余以后它的值和数组下标是对应的，估计楼主担心的是这个函数值太大会怎么怎么！
Java中HashCode()实现的就是上面怎么得到数组下标的过程，他返回的就是对应存储方式的单元地址（如数组下标）。
那么如果真的遇到冲突（得到的数组下标一样）怎么办？数据结构中提供了两种方法，开放地址法，链接法。Java中采用的就是链接法，用单链表存储，该数组下标中存入的是指向单链表的指针。
当HashCode()值相同是，就要用到 equals() 方法。
最后来一张图说明下，画太丑，将就看下。

哈希存储.jpg (55.13 KB, 下载次数: 0)

作者: 花心々小土豆 时间: 2013-6-8 19:25
突然发下3号下标应该存入的值为 1，画图工具不会用，搞乱了，抱歉！！！

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2