我想知道当调整大小或重新散列时，如果我们尝试在地图中放置一个元素会发生什么。它是进入新增加的地图还是旧地图。
还有 hashmap 中额外的可用空间有什么用，即原始地图大小的 25%，负载因子为 75%？
问问题
182 次
2 回答
2
也许这需要一个连贯的答案。
我想知道在调整大小或重新散列时如果我们尝试在地图中放置一个元素会发生什么。
只有当您有两个或更多线程在HashMap. 如果你这样做，你的代码不是线程安全的。它的行为是未指定的，特定于版本的，并且您可能会在不可预知的时间发生不好的事情。诸如条目丢失，莫名其妙的 NPE，甚至您的一个线程进入无限循环之类的事情。
您不应该在没有适当外部同步的情况下编写两个或多个线程在 a 上运行的代码，HashMap以避免同时操作。如果你这样做，我不能告诉你会发生什么。
如果您只有一个线程使用HashMap，那么您担心的场景是不可能的。调整大小发生在更新操作期间。
如果您有多个线程并同步以防止任何同时操作，那么您担心的场景是不可能的。另一种选择是使用ConcurrentHashMap设计为在多个线程可以同时进行红色和写入时正常工作的方法。（当然，调整 a 大小的代码要ConcurrentHashMap复杂得多。但它确保条目最终出现在正确的位置。）
它是去新增加的地图还是旧地图。
假设您正在谈论多线程非同步情况，答案是未指定的并且可能是特定于版本的。（我没有检查代码。）对于其他情况，这种情况是不可能的。
还有 hashmap 中额外的可用空间有什么用，即原始地图大小的 25%，负载因子为 75%？
它不被使用。如果负载因子为 75%，则至少 25% 的哈希槽将是空的/从未使用过。（直到你达到由于架构原因无法进一步扩展哈希数组的地步。但你很少会达到那个地步。）
这是一个性能权衡。Sun 工程师确定/判断 75% 的负载因子将在使用的内存和在HashMap. 随着负载因子的增加，空间利用率会提高，但大多数操作HashMap会变慢，因为哈希链的平均长度会增加。
如果需要，您可以自由使用不同的负载因子值。请注意潜在的后果。
于 2020-02-02T14:50:31.493 回答
0
调整大小和多线程
如果您从单个线程访问哈希映射，则不会发生。调整大小不是由计时器触发，而是由更改哈希映射中元素数量的操作触发，例如，它由put()操作触发。如果您调用put()并且 hash map 发现需要调整大小，它将执行调整大小，然后它将执行您的新元素。意味着，调整大小后将添加新元素，不会丢失任何元素，任何方法都会出现不一致的行为。
如果从多个线程访问您的哈希图，那么可能会出现多种问题。例如，如果两个线程同时调用put()，则两者都可以触发调整大小。后果之一可能是其中一个线程的新元素将丢失。即使不需要调整大小，多线程也会导致丢失某些元素。例如，两个线程生成相同的桶索引，并且还没有这样的桶。两个线程都创建这样的存储桶并将其添加到存储桶数组中。但是最近的胜利，另一个将被覆盖。
它不是特定于哈希映射的。当您通过多个线程修改对象时，这是一个典型的问题。要在多线程环境中正确处理哈希映射，您可以实现同步或使用已经是线程安全的类ConcurrentHashMap。
负载系数
哈希图中的元素存储在桶中。如果每个哈希对应一个桶索引，则访问时间为O(1)。您拥有的哈希值越多，两个哈希值产生相同存储桶索引的概率就越高。然后它们将存储在同一个桶中，访问时间会增加。
减少此类冲突的一种解决方案是使用另一个散列函数。但是 1) 设计适合特定要求的哈希函数可能是一项非常重要的任务（除了减少冲突，它应该提供可接受的性能），以及 2) 您只能在自己的类中改进哈希，但不能在您使用的库中改进。
另一个更简单的解决方案是为相同数量的哈希使用更多的桶。当您减少关系(散列数) / (桶数)时，您会减少冲突的可能性，从而使访问时间接近O(1)。但代价是，您需要更多内存。例如，对于 75% 的负载因子，未使用 25% 的桶数组；对于 10% 的负载系数，将不使用 90%。
没有适合所有情况的解决方案。尝试不同的值并测量性能和内存使用情况，然后确定哪种情况更适合您的情况。
于 2020-02-02T14:46:01.033 回答