黑马程序员技术交流社区
标题:
问一下哈希值的问题
[打印本页]
作者:
盖保宁
时间:
2011-9-27 13:54
标题:
问一下哈希值的问题
看了HashSet 这么多年总算知道哈希表的用武之地了
可是还是那句话，万一哈希值有冲突怎么办
比如北京人口2000万，假设一个人的头发有0到1000万根，肯定会有两个人的头发数目一样
以前知道有这个问题，不知道专家们是怎么解决的啊。
虽然哈希运算不可逆，但是冲突肯定会有的吧
作者:
匿名
时间:
2011-9-27 14:09
hash值是用来分组的，不是用来作为对象的唯一标示的。
如果任何一个对象都返回一个唯一的值，则这个hash编码是比较失败的。
与hash值相关的是散列技术。散列技术的目的是快速定位对象，即查询效率比线性结构要高。
好比100个人，如果 排成一列，则要确定某一个人的位置，就要成第一个人开始查询，一个个人的来确定所有人的位置。
散列技术就是，把这100个人分成10组，每个组的编号唯一（就相当于是hash码），如果要确定某个人的位置，则只要计算他的hash码，然后根据hash码找到组号，然后与这个组里的10个人比较就行了。
其实，现实世界中的集体与个体关系很多都是散列的，像学生和班级，班级号就是hash码。员工和部门，等等
作者:
匿名
时间:
2011-9-27 14:14
呵呵，且听我慢慢道来：
HashSet保证元素的唯一性是根据元素的hashCode和equals方法。HashSet集合的底层是哈希表数据结构，哈希表中有哈希值。每一个对象都有自己的hashCode方法算出自己的哈希值，哈希表存储对象时必须使用对象的hashCode方法获取该对象的哈希值来确定该对象在哈希表中的位置。如果hashCode方法算出的值相等则会继续判断两个元素的equals方法是否为true，若为true则表示此时这两个要存储的对象是同一个元素，此时就只会存储这两个对象中的一个，如果equals方法为false则表示这个两个对象不是同一个，此时就会将后一个对象元素加一进行顺延存储到集合中。
作者:
匿名
时间:
2011-9-27 14:23
。。HashSet 存元素时。。如果两个元素 hashCode 值相同， equals() 返 回为false，那么存放时，在同一个hashCode 处 就有两个元素了，，
作者:
匿名
时间:
2011-9-27 18:12
标题:
回复 沙发 的帖子
有道理，你说 用来分组？ 这可能值是咱在java这边用的吧 我说的是广泛的哈希算法——散列表。
哈希可以加密，比如网络通信里的”握手“的实现，都是用的hash运算
作者:
匿名
时间:
2011-9-27 18:26
标题:
回复 沙发 的帖子
我感觉不对 我认为哈希运算就应该保证唯一性 就算分组也应该不冲突啊 我在矛盾中
作者:
匿名
时间:
2011-9-28 12:04
当初上数据结构的时候，就没怎么去过，唉。
查了下数据结构的书《数据结构——用C语言描述》作者：唐策善，李龙澍，黄刘生，P211
散列技术的基本思想是：
以节点的关键字 k 为自变量，通过一个确定的函数关系 f ，计算出对应的函数值 f（k）,把这个值解释为节点的存储地址，将节点存入 f（k）所致的存储位置上。查找时再根据要查找的关键字用同样的函数计算地址，然后到相应的单元里去取要找的节点。用散列法存储的线性表叫散列表（Hash Table），上述的函数 f 称为散列函数，f（k）称为散列地址。
如果散列函数F 对于不相等的关键字key1和key2得到相同的散列地址（F（key1）=F（key2））,该现象称为冲突，发生冲突这两个关键字则称为该散列函数 F 的同义字。
然后说下我的理解。
在原则上来说，我们设计的散列函数 应该返回一个唯一 的值，这是散列表这种结构设计的初衷（不通过比较获得key所对应的地址），每个key对应一个唯一的地址，我拿到key就拿到了地址，不用通过比较就可以获得这个key所对应的值，这样效率是最高的。
但是，现实中，因为key的取值范围一般远远大于表空间的地址集（容量），所以 对于绝大多数 散列函数，产生冲突是在所难免的。
所以，通常散列函数是个多对一的函数，冲突是不可避免的。
因此，就有了处理冲突的方法。主要有两种方法：1 开放地址法 2 拉链法
java中用的就是拉链法。
拉链法解决冲突的做法是：将所有关键字为同义词的节点连接在同一个单链表中。
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2