哈希映射最初是否与轮询或喜欢的列表一起放置/获取？

Question

我正在使用hashmap制作一个图形函数来存储所有节点。我知道散列是如何工作的，但对于散列映射，我不知道它们是否使用lin/quad探测来放置/获取节点，或者它是否是一个链表。我希望它使用轮询，因为我只希望每个散列有一个节点，而不是链表格式（或任何其他将多个节点散列到同一位置的格式）。这是正常的操作方式，还是需要设置一些值才能将链表方法更改为lin/quad探测方法。

我基本上想知道我的一个节点是否映射到了与前一个节点相同的位置，

>

它是否会用新节点替换旧节点（映射的删除方法），如果不替换，则。。。

它只是将其附加到内存中包含两个节点的链接列表的末尾，还是。。。

它会使用某种类型的轮询方法来获取地图中不包含新节点的新位置吗

我只希望在地图中的每个可用位置都有一个节点

Answer 1

我指的是Java 8（具体来说是1.8.0_66-b18）中的HashMap的实现。

HashMap维护Nodes的表。

当您为一个键输入一个值时，该键将被散列，并使用table映射到bucket（表中的一个节点）。长度-1

如果此索引中没有节点，将创建一个新节点。

如果此索引处有一个节点，则该值将被替换（如果我们有相同的键）或附加一个新节点。桶被组织为节点结构。首先，它类似于链表，但如果节点的数量大于某个阈值，它将被“树化”，即转换为树状结构。

要回答您的问题：

1. 不，它不会用新节点替换旧节点。如果这个键已经有一个节点，它的值将被替换。
2. 是的，一个新节点将附加到节点结构（链表状或树状）。链表状结构可能因此转换为树状结构。
3. 不。将哈希映射到表的索引是硬编码的。

我基本上想知道我的一个节点是否映射到地图中与前一个节点相同的位置

如果不深入研究HashMap（私有）的内部，您就无法确定这一点。微创可能是找出HashMap的表的容量/长度，以及每个键的哈希值的计算索引。但即使是容量（）也无法访问。所以这是一个很好的迹象，表明它是一个实现细节，您不应该真的这样做。

您也很难影响每个桶是否只获得一个节点或更多。这甚至不是哈希冲突，而是HashMap为哈希计算的索引的冲突。您不会遇到这种冲突的唯一方法是：

• 条目数小于容量并且
• 所有键的散列给出不同的table.length-1

这很难保证。