[请教]哈希表本身除了要存储h(k)对应的value以外，也要存储key本身?

Question

哈希表的每个存储元素，是不是要存储一个Pair<key,value>?
例如，
(1)用哈希表存储key=字符串,value=某类型obj的对象。
(2)为了解决冲突的问题，在每个key对应的存储地址我们使用一个list(也就是bucket的角色)，这个list存储所有key计算出来的hash整数值相冲突的各个元素。
(3)现在，有两个字符串"abc"和"xyz"，我假设他们经过hash函数算出来的值相同(都是12345)
那么12345就要对应一个List的指针，里面有两个元素,("abc",obj_1),("xyz",obj2).
------------------------------------问题
(a) 也就说，哈希表本身除了要计算key的hash值以外，也要存储key本身? 必须再对key本身进行字符串匹配的比较，对么?
(b) 如果是我自己设计一个哈希表(Java)，那么我如何让h(k)的值和一个存储对象/地址联系起来? 
    (b.1)例如我开始构造一个新的哈希表，key="abc"计算出h(k)=12345，那么我new一个list对象出来，怎么关联呢? 
    (b.2)下次我查找"abc"的时候，计算出h(k)=12345，如何根据这个值来跳转到相应的存储了list位置?
    因为h(k)是稀疏分布的，我不可能用一个固定的位图来存储每个h(k)对应的list指针的位置，更不能用一个数据结构来排序(这样就没有了hash的意义了)。怎么实现管理这个存储呢? 想不明白还请各位高人指教!

Answer 1

问题a，是的， 需要存储key值，原因是哈希表有一种情况：冲突，也就是经过哈希函数运算后，2个不同的对象产生了一样的哈希值.问题b，可以参考一些ArrayList,HashMap实现，哈希表在本职上来讲是数据组，因此可以通过哈希运算获取数据存储的数组下标，如果想深入了解，去看JDK源代码吧。

Answer 2

一楼说很好。
不是说答案。
而是建议楼主去看JDK源代码。
里面有你所有问题的解决方案！
要是还不行。回复我就行了。

Answer 3

所谓存储，恐怕不是你理解的概念。(a) 也就说，哈希表本身除了要计算key的hash值以外，也要存储key本身? 必须再对key本身进行字符串匹配的比较，对么?
—— 这里其实无论是key还是value，只需要存储其所引用对象的内存地址而已，消耗空间是恒定的；(b) 如果是我自己设计一个哈希表(Java)，那么我如何让h(k)的值和一个存储对象/地址联系起来? 
—— 完全没必要，你很难写出性能比HashMap高的；具体可以去把你大学的数据结构翻出来就有。
 
  (b.1)例如我开始构造一个新的哈希表，key="abc"计算出h(k)=12345，那么我new一个list对象出来，怎么关联呢? 
  —— h(k) 只是用来快速定位索引表中的位置的，建立关联是要一个键队，你可以立即为一个带有两个属性的值对象：key和value，其实HashMap就是这么做的，你可以看看：Map.Entry<K,V> 这个类
 
  (b.2)下次我查找"abc"的时候，计算出h(k)=12345，如何根据这个值来跳转到相应的存储了list位置?
  —— 索引表类似于一个大数组arr，比如长度为 100；那么初步定位就是： arr[h(k) % 100]
楼主你大学的数据结构完全还给老师了还是去找回来认真看看吧，比你在论坛上问效率高太多了。 

Answer 4

问题就在这个索引表上面: 首先索引表必须是连续存储的，否则又要付出一次查询的代价，hash没有了意义。而既然索引表是连续存储的，就有两个问题:
(1) 一开始就要建立一个很大的索引表，否则不够放h(k)
(2) 索引表当中有很多空洞是永远也用不了的。感觉问题还是没有解决啊。