哈希表中的上/下负载因子 [英] Lower / upper load factor in hash tables

问题描述

我要用Java编写一个链式哈希集类.

I am to write a chained hash set class in java.

我知道负载系数是M/容量，其中M是表格中当前元素的数量，容量是表格的大小.

I understand the load factor is M/capacity where M is the number of elements currently in the table and capacity is the size of the table.

但是负载因子如何帮助我确定是否应该调整表的大小并重新哈希? 另外，我在任何地方都找不到如何计算低/高负荷系数.他们甚至需要吗?

But how does the load factor help me determine if I should resize the table and rehash or not? Also I couldn't find anywhere how to calculate the lower / upper load factors. Are they even needed?

我希望这是足够的信息， 谢谢！！

I hope this is enough information, Thank you!!

推荐答案

一个用于配置标准Java哈希(以及许多其他语言的hash API)的loadFactor是一种简化.

A single loadFactor used to configure standard Java hashes (and in a number of hash APIs in other languages) is a simplification.

从概念上讲，区分是合理的

Conceptually, it is reasonable to distingush

• 目标负载，指示默认内存占用量-性能折衷配置.构建已知大小的哈希时，请选择容量，以使大小/容量尽可能接近目标负载.

• Target load, indicate a default memory footprint -- performance tradeoff configuration. when you build a hash of the known size, you choose capacity so that size/capacity is as close to target load, as possible.

最大负载，您希望哈希值永远不会超过此负载.如果散列达到此负载，则触发调整大小.

Max load, you want a hash to never exceed this load. You trigger a resize, if a hash reach this load.

增长因子，这是在调整大小时将哈希值放大多少的默认配置.如果容量是2的幂，则增长因子只能是2或4.

Grow factor, a default configuration of how much to enlarge a hash on resize. If capacity is a power of 2, grow factor could be only either 2 or 4.

最小负载，您希望哈希负载永远不会低于最小负载，除非您删除元素或清除哈希.如果容量为2的幂，则最小负载不能大于0.5.此外，最大负载/最小负载比率应大于或等于增长因子.

Min load, you want a hash load to never be lower than the min load, maybe unless you remove elements or clear a hash. If capacity is a power of 2, min load couldn't be greater than 0.5. Additionally, max load / min load ratio should be greater or equal to grow factor.

以上所有与链式哈希有关的问题，因为用墓碑公开寻址哈希，事情变得更加复杂.

All the above concerns chained hash, for open addressing hash with tombstones things are getting even more complicated.

loadFactor同时扮演目标和最大负载的角色.增长因子为2，最小负载为0.0.

In java.util.HashMap loadFactor plays the roles of target and max load simultaneously. Grow factor is 2, min load is 0.0.

对于链式散列，除非您需要极其精确控制内存使用(您不信任我)或2 ^ 30到2之间的容量，否则非2的幂是过大的^ 31-1(因为在Java中无法创建大小为2 ^ 31的数组，因此它为Integer.MAX_VALUE + 1).

For chained hash non-power-of-2 capacity is overkill unless you need extremely precise control over memory usage (you don't, trust me) or a capacity between 2^30 and 2^31-1 (because you can't create an array of size 2^31 in Java, it is Integer.MAX_VALUE + 1).

这篇关于哈希表中的上/下负载因子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！