HashTable和HashMap键值如何存储在内存中？

Question

我知道有一种散列技术应用于一个键,用于将其值存储在内存地址中.

但是我不明白碰撞是怎么发生的？Java使用哪种哈希算法来创建内存空间？是MD5吗？

Answer 1

基本思路HashMap是这样的:

1. A HashMap实际上是一组包含Key和Value的特殊对象.
2. 阵列有一些桶(槽),比如16.
3. 散列算法由hashCode()每个对象具有的方法提供.因此,当您编写新内容时Class,您应该注意正确hashCode()和equals()方法实现.默认值(Object类的)将内存指针作为数字.但这对我们想要使用的大多数类都不好.例如,String该类使用一种算法,该算法从字符串中的所有字符生成哈希 - 想象如下hashCode = 1.char + 2.char + 3.char...:(简化).因此,两个相等的字符串,即使它们位于存储器中的不同位置,也具有相同的字符串hashCode().
4. 结果hashCode(),比如说"132",那么如果我们有一个很大的数组,那么应该存储对象的存储桶数量.但我们没有,我们的只有16桶.因此,我们使用明显的计算'hashcode % array.length = bucket'或'132 mod 16 = 4'将Key-Value对存储在4号桶中.
5. • 如果还没有其他配对,那没关系.
   • 如果有一个Key等于我们拥有的Key,我们删除旧的.
   • 如果存在另一个键值对(碰撞),我们将旧的键值对链接到链接列表中.
6. 如果支持数组变得太满,那么我们必须制作太多链表,我们创建一个双倍长度的新数组,重新散列所有元素并将它们添加到新数组中,然后我们处理旧数组.这很可能是最昂贵的操作HashMap,所以你想告诉你Maps如果你以前知道它将使用多少桶.
7. 如果有人试图得到一个值,他提供一个密钥,我们哈希,修改它,然后通过潜在的链表进行完全匹配.

一张图片,由维基百科提供:

在这种情况下,

• 有一个256桶的数组(编号,当然,0-255)
• 有五个人.它们的哈希码在接通后mod 256指向阵列中的四个不同的槽.
• 你可以看到Sandra Dee没有一个免费的插槽,所以她被John Smith锁定了.

现在,如果您试图查找Sandra Dee的电话号码,您可以将她的名字哈希,将其修改为256,并查看存储桶152.在那里您可以找到John Smith.那不是桑德拉,再往前看......啊哈,桑德拉在约翰之后被束缚住了.