HashTables 如何处理冲突? [英] How do HashTables deal with collisions?

问题描述

我在学位课程中听说，如果新的 Key 条目与另一个条目发生冲突，HashTable 会将新条目放入下一个可用"存储桶中.

I've heard in my degree classes that a HashTable will place a new entry into the 'next available' bucket if the new Key entry collides with another.

如果在使用碰撞键调用返回值时发生这种碰撞，HashTable 如何仍然返回正确的值?

How would the HashTable still return the correct Value if this collision occurs when calling for one back with the collision key?

我假设 Keys 是 String 类型并且 hashCode() 返回由 Java 生成的默认值.

I'm assuming that the Keys are String type and the hashCode() returns the default generated by say Java.

如果我实现自己的散列函数并将其用作查找表(即HashMap 或Dictionary)的一部分，则存在哪些处理冲突的策略?

If I implement my own hashing function and use it as part of a look-up table (i.e. a HashMap or Dictionary), what strategies exist for dealing with collisions?

我什至看过关于素数的笔记！Google 搜索中的信息不太清楚.

I've even seen notes relating to prime numbers! Information not so clear from Google search.

推荐答案

哈希表以两种方式之一处理冲突.

Hash tables deal with collisions in one of two ways.

选项 1: 通过让每个存储桶包含散列到该存储桶的元素的链表.这就是为什么一个错误的哈希函数会导致哈希表中的查找非常缓慢.

Option 1: By having each bucket contain a linked list of elements that are hashed to that bucket. This is why a bad hash function can make lookups in hash tables very slow.

选项 2: 如果哈希表条目都已满，则哈希表可以增加其拥有的桶数，然后重新分配表中的所有元素.哈希函数返回一个整数，哈希表必须采用哈希函数的结果并根据表的大小对其进行修改，这样才能确保它会进入存储桶.因此，通过增加大小，它将重新散列并运行模计算，如果幸运的话可能会将对象发送到不同的存储桶.

Option 2: If the hash table entries are all full then the hash table can increase the number of buckets that it has and then redistribute all the elements in the table. The hash function returns an integer and the hash table has to take the result of the hash function and mod it against the size of the table that way it can be sure it will get to bucket. So by increasing the size, it will rehash and run the modulo calculations which if you are lucky might send the objects to different buckets.

Java 在其哈希表实现中同时使用选项 1 和选项 2.

Java uses both option 1 and 2 in its hash table implementations.

这篇关于HashTables 如何处理冲突?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！