HashTable 和 HashMap key-value 是如何存储在内存中的? [英] How HashTable and HashMap key-value are stored in the memory?

问题描述

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

I understand there is a hashing technique is applied to a key to store its value in the memory address.

但我不明白这里的碰撞是如何发生的?Java 使用哪种哈希算法来创建内存空间?是MD5吗?

But I don't understand how the collision is happening here? Which hashing algorithm does Java use to create a memory space? Is it MD5?

推荐答案

HashMap的基本思路是这样的:

1. 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，我们会删除旧的.
   • 如果存在另一个键值对(冲突)，我们将新的键值对在旧键之后链接到一个链表中.

1. A HashMap is really an array of special objects that hold both Key and Value.
2. The array has some amount of buckets (slots), say 16.
3. The hashing algorithm is provided by the hashCode() method that every object has. Therefore, when you are writing a new Class, you should take care of proper hashCode() and equals() methods implementation. The default one (of the Object class) takes the memory pointer as a number. But that's not good for most of the classes we would like to use. For example, the String class uses an algorithm that makes the hash from all the characters in the string - think of it like this: hashCode = 1.char + 2.char + 3.char... (simplified). Therefore, two equal Strings, even though they are on a different location in the memory, have the same hashCode().
4. The result of hashCode(), say "132", is then the number of bucket where the object should be stored if we had an array that big. But we don't, ours is only 16 buckets long. So we use the obvious calculation 'hashcode % array.length = bucket' or '132 mod 16 = 4' and store the Key-Value pair in a bucket number 4.
5. • If there's no other pair yet, it's ok.
   • If there's one with Key equal to the Key we have, we remove the old one.
   • If there's another Key-Value pair (collision), we chain the new one after the old one into a linked list.

图片，由维基百科提供:

在这种情况下，

• 有一个包含 256 个桶的数组(编号当然是 0-255)
• 有五个人.它们的哈希码经过 mod 256 后，指向数组中的四个不同槽.
• 您可以看到 Sandra Dee 没有空位，因此她被锁在 John Smith 之后.

• there is an array with 256 buckets (numbered, of course, 0-255)
• there are five people. Their hashcodes, after being put through mod 256, point to four different slots in the array.
• you can see Sandra Dee didn't have a free slot, so she has been chained after John Smith.

现在，如果您尝试查找 Sandra Dee 的电话号码，您将对她的姓名进行哈希处理，将其修改为 256，然后查看存储桶 152.在那里您会找到 John Smith.那不是 Sandra，再看远点……啊哈，Sandra 被锁在 John 身后.

Now, if you tried to look up a telephone number of Sandra Dee, you would hash her name, mod it by 256, and look into the bucket 152. There you'd find John Smith. That's no Sandra, look further ... aha, there's Sandra chained after John.

这篇关于HashTable 和 HashMap key-value 是如何存储在内存中的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！