实际上，根据我的计算，“完美”的负载系数更接近于log 2(~ 0.7)。尽管任何负载系数小于这个值都会产生更好的性能。我觉得点75手枪可能是从帽子里拿出来的。

证明:

可以避免连锁，并通过预测分支预测 桶是否为空。一个桶可能是空的，如果它的概率 空的超过。5。

s表示键的大小，n表示添加的键的数量。使用二项式 定理，一个桶为空的概率为:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

因此，如果小于，则桶可能是空的

log(2)/log(s/(s - 1)) keys

当s达到无穷大时，如果添加的键数等于 P(0) = .5，则n/s迅速逼近log(2):

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...

从文档中可以看到:

负载因子衡量的是在哈希表的容量自动增加之前允许达到的满度

这实际上取决于您的特定需求，没有“经验法则”来指定初始负载系数。

我会选择n * 1.5或n + (n >> 1)的表大小，这将给出不除法的负载因子。66666~，这在大多数系统上是很慢的，特别是在硬件中没有除法的便携式系统上。

实际上，根据我的计算，“完美”的负载系数更接近于log 2(~ 0.7)。尽管任何负载系数小于这个值都会产生更好的性能。我觉得点75手枪可能是从帽子里拿出来的。

证明:

可以避免连锁，并通过预测分支预测 桶是否为空。一个桶可能是空的，如果它的概率 空的超过。5。

s表示键的大小，n表示添加的键的数量。使用二项式 定理，一个桶为空的概率为:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

因此，如果小于，则桶可能是空的

log(2)/log(s/(s - 1)) keys

当s达到无穷大时，如果添加的键数等于 P(0) = .5，则n/s迅速逼近log(2):

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...

HashMap的默认初始容量为16，负载因子为0.75f(即当前映射大小的75%)。负载因子表示HashMap容量应该在哪个级别加倍。

例如，容量与负载系数的乘积为16 * 0.75 = 12。这表示在HashMap中存储了第12个键值对后，其容量变为32。

如果桶太满了，我们就得翻一翻

一个非常长的链表。

这有点违背了重点。

这是一个有四个桶的例子。

到目前为止，我的HashSet中有大象和獾。

这是个很好的情况，对吧?

每个元素有0个或1个元素。

现在我们将另外两个元素放入HashSet中。

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

这也不算太糟。

每个桶只有一个元素 ． 如果我想知道，这里面有熊猫吗?

我可以很快地看一下1号桶，它不是

那里,

我就知道这不是我们的收藏。

如果我想知道里面是否有猫，我会看桶

3号,

我找到猫，我很快就知道它是不是在我们的

收集。

如果我加上考拉，那还不错。

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

也许现在不是在1号桶里只看

一个元素,

我需要看两个。

但至少我不用看大象，獾和

cat.

如果我再找熊猫，它只能在桶里

1号和

我什么都不用看除了水獭和

考拉。

但是现在我把鳄鱼放在1号桶里，你可以

看看接下来会发生什么。

如果第一桶变得越来越大 而且

更大，那么我基本上要看遍所有的

找到这些元素

应该在1号桶里的东西。

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

如果我开始往其他桶里添加字符串，

是的，问题越来越大，在每一个

单桶。

我们如何阻止我们的桶太满?

这里的解决方法是

          "the HashSet can automatically

        resize the number of buckets."

HashSet意识到桶正在得到

太满了。

它失去了一次查找的优势

元素。

它只会创建更多的存储桶(通常是以前的两倍)和

然后将元素放入正确的存储桶中。

这是我们的基本HashSet实现

链接。 现在我要创建一个“自我调整大小的HashSet”。

这个HashSet会意识到桶是

吃得太饱

它需要更多的桶。

loadFactor是HashSet类中的另一个字段。

loadFactor表示每个元素的平均数量

桶,

上面我们要调整大小。

loadFactor是空间和时间之间的平衡。

如果桶太满了，我们会调整大小。

这当然需要时间，但是

这可能会节省我们的时间如果桶是一个

再空一点。

让我们看一个例子。

这是一个HashSet，到目前为止我们已经添加了四个元素。

大象，狗，猫和鱼。

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

此时，我已经确定loadFactor和

阈值,

每个桶的平均元素数就可以了

等于0.75。

桶数就是桶数。长度是6，然后

此时我们的HashSet有四个元素，所以

当前大小为4。

我们会调整HashSet的大小，也就是说我们会添加更多的桶，

当每个桶的平均元素数超过

负载系数。

即当前大小除以桶数。长度是

大于loadFactor。

此时，每个桶的平均元素数

是4除以6。

4个元素，6个桶，等于0.67。

这比我设置的0.75的阈值要小，所以我们

好吧。

我们不需要调整大小。

现在我们加入土拨鼠。

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

土拨鼠会被放在第三桶里。

此时，currentSize为5。

现在是每个桶的平均元素数

是currentSize除以buckets.length。

5个元素除以6个桶等于0.83。

这超过了负荷因子0.75。

为了解决这个问题，为了使

桶可能会有一点

更空的操作，如确定是否a

桶包含

元素会变得不那么复杂，我想调整大小

我的哈希集。

调整HashSet的大小需要两个步骤。

首先我把桶数翻倍，我有6个桶，

现在我有12个桶。

注意，我设置为0.75的loadFactor保持不变。

但是改变的桶数是12，

元素的数量保持不变，是5。

5除以12大约是0.42，这比我们的

负载系数,

所以我们现在没事了。

但这还没完，因为有些元素还在

现在桶错了。

例如，大象。

大象在2号桶里，因为它的数量

大象的文字

是8。

我们有6个桶，8减6是2。

这就是为什么它最终排名第二。

但现在我们有12个桶，8对12取余是8，所以

大象不再属于第二桶了。

大象属于8号桶。

土拨鼠呢?

这一切都是土拨鼠挑起的。

土拨鼠最后在三号桶里。

因为9对6取余等于3。

现在是9对12取余。

9 mod 12 = 9，土拨鼠去了9号桶。

你可以看到这一切的好处。

现在3号桶只有两个元素，而之前 它有3个。

这是我们的代码，

我们的HashSet有单独的链

没有做任何大小调整。

现在，这是我们使用调整大小的新实现。

大部分代码都是一样的，

我们仍然要确定它是否包含

值了。

如果没有，我们就会找出是哪个桶

应该进入和

然后把它添加到那个bucket中，添加到LinkedList中。

但是现在我们增加currentSize字段。

currentSize是记录数字的字段

HashSet中的元素。

我们要增加它，然后我们要看

在平均负荷下，

每个桶的平均元素数。

我们在下面做除法。

我们必须在这里做一点选角来确定

我们得到了一个double。

然后，我们将平均载荷与电场进行比较

我设置为

0.75，例如，当我创建这个HashSet时

负载系数。

如果平均负载大于loadFactor，

这意味着每个桶上有太多的元素

平均，我需要重新插入。

这是我们对重新插入方法的实现

所有的元素。

首先，我将创建一个名为oldBuckets的局部变量。

这是指现在的桶吗

在我开始调整大小之前。

注意，我还没有创建一个新的链表数组。

我只是把桶重命名为oldBuckets。

现在记住水桶是我们课上的一个领域，我要走了

现在创建一个新数组

但是这个有两倍的元素

就像第一次一样。

现在我需要重新插入，

我要遍历所有的旧桶。

oldBuckets中的每个元素都是字符串的LinkedList

那是一个桶。

我将遍历这个桶，得到其中的每个元素

桶。

现在我要把它重新插入到newBuckets中。

我将得到它的hashCode。

我就能算出它是哪个下标。

现在我得到了新的桶，新的LinkedList

字符串和

我会把它添加到新桶中。

概括一下，哈希集是Linked的数组

列表或桶。

一个自调整大小的HashSet可以使用一些比例或