我不会详细介绍HashMap是如何工作的，但是会给出一个例子，这样我们就可以通过将HashMap与现实联系起来来记住它是如何工作的。

我们有Key, Value,HashCode和bucket。

在一段时间内，我们将把它们与以下内容联系起来:

一个社会 HashCode ->社会地址(总是唯一的) 社会中的房子 Key ->房屋地址。

使用Map.get(key):

Stevie想去他的朋友(Josse)的房子，他住在一个VIP社会的别墅里，让它成为javalavers社会。 Josse的地址是他的SSN(每个人都不一样)。 有一个索引，我们可以根据社会安全号找到协会的名字。 这个索引可以被认为是一个找出HashCode的算法。

SSN协会名称 92313(Josse’s) -爪哇 13214—AngularJSLovers 98080—javalover 53808 -生物爱好者

这个SSN(密钥)首先给我们一个HashCode(来自索引表)，它只是社会的名字。 现在，多个房子可以在同一个社会中，所以HashCode可以是公共的。 假设，社会对两个房子都是公用的，我们如何识别我们要去哪个房子，是的，通过使用(SSN)密钥，它只是房子的地址

使用Map.put(关键字,值)

这将通过查找HashCode为该值找到一个合适的社会，然后存储该值。

我希望这能有所帮助，而且这是可以修改的。

哈希映射的工作原理是哈希

HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array) where keys and values are stored in form of a nested class called Entry (Map.Entry) . So you have concluded that from the previous line that Both key and value is stored in the bucket as a form of Entry object . So thinking that Only value is stored in the bucket is not correct and will not give a good impression on the interviewer .

每当我们调用HashMap对象上的get(Key k)方法时。首先，它检查key是否为空。注意，HashMap中只能有一个空键。

如果key为null，则null键总是映射到哈希0，因此索引为0。

如果key不为空，那么它将在key对象上调用hashfunction，参见上述方法中的第4行，即key. hashcode()，因此在key. hashcode()返回hashValue之后，第4行如下所示

            int hash = hash(hashValue)

现在，它将返回的hashValue应用到自己的哈希函数中。

我们可能想知道为什么要再次使用hash(hashvalue)计算哈希值。答案是它可以防御低质量的哈希函数。

现在使用final hashvalue来查找存储Entry对象的bucket位置。条目对象像这样存储在桶中(哈希，键，值，bucketindex)

下面是针对Java 8版本的HashMap机制的粗略描述(它可能与Java 6略有不同)。

数据结构

哈希表 哈希值通过key上的Hash()计算，它决定对给定的键使用哈希表的哪个桶。 链表(单个) 当桶中的元素数量较小时，使用单链表。 红黑树 当一个桶中的元素数量很大时，使用红黑树。

类(内部)

地图。条目 在map中表示单个实体，即键/值实体。 HashMap。节点 节点的链表版本。 它可以表示: 哈希桶。 因为它有哈希属性。 单链表中的节点(因此也是链表的头)。 HashMap。TreeNode 节点的树版本。

字段(内部)

节点[]表 桶表(链表的头)。 如果一个bucket不包含元素，那么它就是null，因此只占用一个引用的空间。 设置<地图。入口> entrySet 实体的集合。 int大小 实体数量。 负载系数浮动 在调整大小之前，指示允许的哈希表有多满。 int阈值 下一个要调整大小的大小。 公式:阈值=容量* loadFactor

方法(内部)

int散列(关键) 按键计算哈希值。 如何映射哈希到桶? 使用以下逻辑: static int hashToBucket(int tableSize, int hash) { return (tableSize - 1) & hash; ｝

关于能力

在哈希表中，容量是指桶数，可以从table.length中获取。 Also可以通过threshold和loadFactor计算，因此不需要定义为类字段。

可以通过:capacity()得到有效容量

操作

按键查找实体。 首先通过哈希值找到桶，然后循环链表或搜索排序树。 用键添加实体。 首先根据key的哈希值找到桶。 然后试着找出它的值: 如果找到，则替换该值。 否则，在链表的开头添加一个新节点，或插入到排序树中。 调整 当达到阈值时，将哈希表的容量(table.length)翻倍，然后对所有元素重新哈希以重建表。 这可能是一次昂贵的手术。

性能

获取并放置 时间复杂度为O(1)，因为: 桶通过数组索引访问，因此是O(1)。 每个桶中的链表长度较小，可见为O(1)。 树的大小也是有限的，因为当元素数量增加时将扩展容量并重新哈希，所以可以将其视为O(1)，而不是O(log N)。

你在第三点上错了。两个条目可以具有相同的哈希码，但不相等。看一下HashMap的实现。从OpenJdk中获取。你可以看到它检查哈希值是否相等键值是否相等。如果第三点成立，那么检查键值是否相等就没有必要了。哈希码在键之前进行比较，因为前者是更有效的比较。

如果您有兴趣进一步了解这方面的知识，请参阅Wikipedia关于开放寻址冲突解决的文章，我认为这是OpenJdk实现使用的机制。这种机制与另一个答案中提到的“桶”方法略有不同。

每个Entry对象表示键值对。如果一个桶有多于1个Entry，则字段next指向其他Entry对象。

有时候，两个不同对象的hashcode可能是相同的。在这种情况下，2个对象将保存在一个桶中，并将显示为LinkedList。入口点是最近添加的对象。该对象引用具有next字段的其他对象，等等。最后一项为空。 当您使用默认构造函数创建HashMap时

数组的大小为16，默认负载平衡为0.75。

(源)

HashMap是一个Entry对象数组。

把HashMap看作是一个对象数组。

看看这个对象是什么:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

每个Entry对象表示一个键值对。如果一个桶有多个Entry，下一个字段引用另一个Entry对象。

有时候，两个不同对象的哈希码可能是相同的。在这种情况下，两个对象将保存在一个bucket中，并将显示为链表。 入口点是最近添加的对象。该对象引用具有下一个字段的另一个对象，以此类推。最后一项指向null。

当使用默认构造函数创建HashMap时

HashMap hashMap = new HashMap();

数组的大小为16，默认负载平衡为0.75。

添加新的键-值对

计算键的hashcode 计算元素应该放置的位置哈希% (arrayLength-1)(桶号) 如果你试图用一个已经保存在HashMap中的键添加一个值，那么值将被覆盖。 否则元素被添加到桶中。

如果存储桶已经有至少一个元素，则添加一个新元素并将其放置在存储桶的第一个位置。它的下一个字段指向旧元素。

删除

计算给定键的hashcode 计算桶号哈希% (arrayLength-1) 获取桶中第一个Entry对象的引用，并通过equals方法遍历给定桶中的所有条目。最终我们会找到正确的入口。 如果没有找到所需的元素，则返回null