在 hashmap 或 hashtable 中重新散列过程 [英] Rehashing process in hashmap or hashtable

问题描述

当大小超过 maxthreshold 值时，hashmap 或 hashtable 中的重新散列过程如何完成?

是否所有对都被复制到一个新的存储桶数组中?

重新散列后同一个bucket(链表中)的元素会发生什么变化?我的意思是重新散列后它们会留在同一个桶中吗?

解决方案

问题中的最大阈值称为负载因子.

建议将负载因子设置为 0.75 左右.负载因子定义为 (m/n)，其中 n 是哈希表的总大小，m 是在需要增加基础数据结构的大小之前可以插入的首选条目数.

可以在两种情况下进行重新散列:

1. 当当前的 m'/n 比增加超过负载系数时

2. M'/n 比率下降到一个非常低的值，比如 0.1

在这两种情况下，m' 都是当前条目数.此外，这两种情况都需要将当前条目转移到更大或更小的哈希表中.

在问题的上下文中，重新散列是将散列函数应用于条目以将它们移动到另一个散列表的过程.可以使用之前使用过的哈希函数，也可以一起使用新的函数.

请注意:发生碰撞时也会进行重新散列.(这也是处理冲突的一种方式.)

要添加更多上下文和详细讨论，请访问我的博客 哈希基础

How is the rehashing process done in a hashmap or hashtable when the size exceeds the maxthreshold value?

Are all pairs just copied to a new array of buckets?

EDIT:

What happen to the elements in the same bucket (in linked list) after rehashing? I mean will they remain in same bucket after rehashing?

解决方案

The maximum threshold in the question is called the load factor.

It is advisable to have a load factor of around 0.75. Load factor is defined as (m/n) where n is the total size of the hash table and m is the preferred number of entries which can be inserted before a increment in size of the underlying data structure is required.

Rehashing can be done in two cases:

1. When the present m'/n ratio increases beyond the load factor

2. M'/n ratio falls to a very low value say 0.1

In both the cases m' is the current number of entries. Also, both the cases demand the shifting of the present entries into a bigger or a smaller hash table.

In the question's context rehashing is the process of applying a hash function to the entries to move them to another hash table. It is possible to use the hash function which was used earlier or use a new function altogether.

Please note: Rehashing is also done when a collision occurs. (It's a way of handling collisions too.)

To add some more context and a detailed discussion please visit my blog Hashing Basics

这篇关于在 hashmap 或 hashtable 中重新散列过程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！