常言道，一图胜千言。我说:有些代码胜过1000字。下面是HashMap的源代码。获得方法:

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

因此，很明显，哈希是用来寻找“桶”的，并且总是在该桶中检查第一个元素。如果不是，则使用键的equals来查找链表中的实际元素。

让我们看看put()方法:

  /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

它稍微复杂一些，但很明显，新元素被放在选项卡中基于哈希计算的位置:

I = (n - 1) & hash这里I是新元素将被放置的索引(或者它是“桶”)。N是TAB数组(“桶”数组)的大小。

首先，尝试将其作为“bucket”中的第一个元素。如果已经有一个元素，则向列表中追加一个新节点。

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html上找到很好的信息

总结:

HashMap的工作原理是哈希

put(key, value): HashMap将key和value对象都存储为Map.Entry。Hashmap应用hashcode(key)来获取桶。如果有碰撞，HashMap使用LinkedList存储对象。

get(key): HashMap使用key Object的hashcode来查找桶的位置，然后调用keys.equals()方法来识别LinkedList中的正确节点，并在Java HashMap中返回该键的相关值对象。

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

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是这样工作的(这有点简化，但它说明了基本机制):

它有许多“桶”，用来存储键值对。每个桶都有一个唯一的编号——用来标识该桶。当您将一个键值对放入映射时，hashmap将查看键的哈希码，并将该对存储在标识符为键的哈希码的bucket中。例如:密钥的哈希码为235 ->，存储在桶号为235的桶中。(注意，一个桶可以存储多个键-值对)。

当您在hashmap中查找一个值时，通过给它一个键，它将首先查看您给出的键的哈希代码。然后，hashmap将查看相应的存储桶，然后它将通过equals()比较您给出的键与存储桶中所有对的键。

现在，您可以看到这对于在map中查找键-值对是多么高效:通过键的哈希代码，哈希映射立即知道要在哪个bucket中查找，因此它只需要测试该bucket中的内容。

看看上面的机制，你也可以看到对键的hashCode()和equals()方法有什么必要的要求:

If two keys are the same (equals() returns true when you compare them), their hashCode() method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket). If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use equals() to tell them apart.

这将是一个很长的答案，拿着饮料继续阅读…

哈希就是在内存中存储一个键-值对，可以更快地读写。它将键存储在数组中，值存储在LinkedList中。

假设我想存储4个键值对

{
“girl” => “ahhan” , 
“misused” => “Manmohan Singh” , 
“horsemints” => “guess what”, 
“no” => “way”
}

为了存储键，我们需要一个4元素的数组。现在我如何将这4个键中的一个映射到4个数组索引(0,1,2,3)呢?

因此java找到单个键的hashCode并将它们映射到特定的数组索引。 哈希码公式是-

1) reverse the string.

2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .

3) So hashCode() of girl would be –(ascii values of  l,r,i,g are 108, 114, 105 and 103) . 

e.g. girl =  108 * 31^0  + 114 * 31^1  + 105 * 31^2 + 103 * 31^3  = 3173020

哈希和女孩!!我知道你在想什么。你对狂野二重唱的迷恋可能会让你错过一件重要的事情。

为什么java要把它乘以31 ?

因为，31是奇数质数形式为2^5 - 1。奇素数降低了哈希碰撞的概率

这个哈希码是如何映射到数组下标的呢?

答案是，哈希码%(数组长度-1)。在我们的例子中，“girl”被映射为(3173020 % 3)= 1。它是数组的第二个元素。

值“ahhan”存储在与数组索引1相关的LinkedList中。

HashCollision -如果您尝试使用上面描述的公式查找密钥“误用”和“horsemints”的hasHCode，您将看到两者都给出相同的1069518484。Whooaa ! !〇教训

2个相等的对象必须具有相同的hashCode，但如果没有保证 hashCode匹配，则对象相等。所以它应该存储 这两个值都对应于1号桶的“误用”和“horsemints” (1069518484% 3)。

现在哈希图看起来是-

Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 – 

现在，如果有人试图找到键“horsemints”的值，java很快就会找到它的hashCode，对它进行模块化，并开始在LinkedList对应的索引1中搜索它的值。因此，这样我们就不需要搜索所有的4个数组索引，从而使数据访问更快。

但是，等一下。有3个值在那个linkedList对应的数组索引1，它如何找出哪一个是值为关键“horsemints”?

其实我撒谎了，我说HashMap只是在LinkedList中存储值。

它将两个键值对存储为映射条目。实际上Map是这样的。

Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 – 

现在你可以看到，当遍历对应于ArrayIndex1的linkedList时，它实际上会将linkedList的每个条目的key与horsemints进行比较，当它找到一个时，它会返回它的值。

希望你读得开心:)