Ash*_*dal 7 java algorithm equals hashcode
// The worst possible legal hash function - never use!
@Override public int hashCode() { return 42; }
这是合法的,因为它确保了相等的对象具有相同的哈希码.这很糟糕,因为它确保每个对象都具有相同的哈希码.因此,每个对象都会散列到同一个存储桶,并且散列表会退化为链接列表.应该以线性时间运行的程序改为以二次方运行.
我试图弄清楚如何(引自第47页,第9项,Joshua Bloch的Effective Java).
我看到它的方式如下(考虑以下代码):
Map<String, String> h = new HashMap<String,String>();
h.put("key1", "value1");
h.put("key1", "value2");
什么与第二发生h.put("key1",...)命令如下:1.获取的散列码key1
2.获取到表示上述哈希码3.在该桶桶中,为每个对象,调用equals方法找到相同的对象是否存在.
这有点快,因为首先你找到对象的"组"(桶),然后找到实际的对象.
现在,当哈希码实现42为ALL对象返回相同的整数(如上所述)时,只有一个桶,并且需要在整个hashmap中的每个对象上逐个调用equals方法/哈希表.这与链表一样糟糕,因为如果链表中的对象也是如此,则必须逐个比较(调用equals)每个对象.
有人说,这就是哈希表退化为链表的原因吗？
(我为上述文本的冗长而道歉.我的概念中我不够清楚地说明它更简洁)
是的,你的理解似乎是准确的.但是,它不像链接列表.共享一个公共存储桶的条目的实际内部实现是一个普通的旧链表.存储桶将Map.Entry保存在列表的开头,每个条目都有一个指向其存储桶下一个占用者的前向指针.(当然,为了实现内置于Java中的HashMap.)
HashTable是一个具有映射功能(hashCode)的数组.插入数组时,您可以计算位置并在此处插入元素.
但是,hashCode不保证每个元素都有不同的位置,因此一些对象可能会发生碰撞(具有相同的地址),而hashTable必须解决它.有两种常见的方法,如何做到这一点.
单独链接
在单独的链接(在Java中使用)中,数组的每个索引都包含一个链表 - 因此每个存储桶(位置)都具有无限容量.因此,如果你的hashCode只返回一个值,你只使用一个like list => hashTable是一个链表.
线性探测
第二种方法是线性探测.在线性探测中,内部数组实际上是正常的元素数组.当您发现该位置已被占用时,您将迭代数组并将新元素放在第一个空位置.
所以我你的hashCode的impl为每个元素生成了一个含有的值,你只生成了colisions,因此你试图将所有元素放在同一个索引上,因为它总是被占用,你迭代所有放置的元素并放置新元素在结束时this structure.如果你再读一遍,你在做什么,你必须看到,你只使用链表的另一个(你可以说是隐含的)实现.
为什么不这样做
你真的不应该返回常量值,因为哈希表是为了提供O(1)搜索和插入操作的预期复杂性而构建的(因为哈希函数为(几乎)每个不同的对象返回一个不同的地址).如果只返回一个值,则实现会降级为链接列表,但O(n)对于这两个操作.