Suppose we have a set of keys: <54, 18, 10, 25, 28, 36, 38, 41, 12, 90>. Use the hashing function key % N to map each key into the following array. If there is a collision, use the separate chaining technique.
下面只是数组的图片,数组标记为 A
,大小为 13,因此图片是列出 0-12 的数组单元格。 N=13.
到目前为止,我对这个问题的哈希理解是,我需要使用函数 key % 13
(N 等于 13)将给定的键排列到数组中。但是我的书没有给出不同函数的例子。它使用的唯一示例是按字母顺序排列的姓氏首字母。
谁能给我一个简短的解释而不只是给我答案?
最佳答案
正如你提到的,你的哈希函数是 h=key%13;
假设有一个从地址 0 到 20 开始的内存位置。 因此,将此函数应用于数组中的每个元素。 1) h1= 54 % 13 = 2 => 这将转到第二个地址位置。
2) h2= 18 % 13 = 5 => 这将转到第 5 个位置。
3) h3= 10 % 13 = 10 => 这将转到第 10 个位置。
4) h4= 25 % 13 = 14 => 这将转到第 14 个位置。
5) h5= 28 % 13 = 2 => 这里发生了碰撞,因为 54 已经出现在第二个位置。
现在的解决方案是使用分离链。
Separate Chaining 意味着只将当前元素添加到 2nd Location 的链表中的下一个位置。意味着当有碰撞时,在每个位置都意味着一个新的链表。
下面是图例。单独的链接。
希望您能得到答案。上图中的元素不同,但效果相同。
有关更多详细信息,请访问此链接:enter link description here
关于java - 哈希函数和哈希表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20715481/