前言本文是基于Java 8的HashMap进行分析，主要是分析HashMap中的put()和get()方法。下面将会分析这部分的源码，如果觉得源码分析内容太啰嗦，可以跳过源码部分，直接看源码下面的总结。put()方法源码分析HashMap的put()方法是我们最常用的方法，但是put()方法是怎么工作的呢？put()方法 /** * HashMap的put()方法支持key/value为null / public V put(K key, V value) { //实际上是先调用HashMap的hash()方法获取到key的hash值 //然后调用HashMap的putVal()方法 return putVal(hash(key), key, value, false, true); }put()方法实际上是调用hash()方法获取到key的hash值调用putVal()方法存储key-value核心方法是putVal()方法，下面我会先分析一下hash()方法，因为这个方法涉及到hash值这个关键属性的计算。hash()方法static final int hash(Object key) { int h; // key为null时，hash值为0 // key不为null时，调用key对象的hashCode()方法并通过位运算异或和无符号右移将高位分散到低位 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }hash()方法指定了null的hash值为0。这样就可以支持key为null。(h = key.hashCode()) ^ (h >>> 16)这段代码通过位运算异或和无符号右移将高位分散到低位，这样做可以减少哈希碰撞的概率（这块不是很清楚原理，是从方法注释上了解到的）putVal()方法 /* * Map.put()方法的实际实现 * * @param hash key的hash值 * @param key 键值对中的key * @param value 键值对中的value * @param onlyIfAbsent 如果为true，则键值对中的值已经存在则不修改这个值 * @param evict 如果为false，则是处于创建模式 * @return 上一次的value，如果上一次的value不存在，则为null / final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab用于暂存散列表table。p为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引 Node<K,V>[] tab; Node<K,V> p; int n, i; //给tab和n赋值 //当tab为null或者tab的长度n为0时，触发resize()来初始化tab if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //使用(n - 1) & hash（等价于hash%n）计算命中的散列表索引，同时判断散列表对应索引的链表是否存在 if ((p = tab[i = (n - 1) & hash]) == null) //散列表对应索引的链表不存在则创建一个新的链表 tab[i] = newNode(hash, key, value, null); else {//散列表对应索引的链表已存在 Node<K,V> e; K k; // 判断头节点的hash值和key是否与入参的hash值和key一致。需要注意，null的hash值为0 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 对应的键值对已经存在，记录下来 e = p; else if (p instanceof TreeNode)//判断对应的链表是否转化为红黑树 //若是，则直接调用红黑树的putTreeVal()方法 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开始，所以为阈值-1 // 将链表转化为红黑树 treeifyBin(tab, hash); // 中断循环 break; } // 判断当前遍历的节点的hash值和key是否与入参的hash值和key一致，即key是否已经存在 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // key已经存在，中断循环 break; // 记录当前遍历的节点 p = e; } } if (e != null) { // Map中存在重复的key V oldValue = e.value;//记录下旧值 if (!onlyIfAbsent || oldValue == null)//判断值存在是否可以进行修改以及旧值是否为null e.value = value;//修改该节点的值 afterNodeAccess(e);// 链表节点的回调方法，此处为空方法 return oldValue;//返回旧值 } } // HashMap发生结构变化，变化次数累加 ++modCount; // 键值对个数自增，同时判断是否达到扩容的阈值 if (++size > threshold) resize(); // 链表节点的回调方法，此处为空方法 afterNodeInsertion(evict); // 此处返回null是因为链表新增了节点，所以上一次的值必然为null return null; }putVal()方法的关键点：若table没有初始化则调用reszie()方法初始化。计算命中的散列表索引位置，公式为(n - 1) & hash（等价于hash%n）。其中n为散列表长度，hash为插入的键值对的key的哈希值。判断散列表对应索引中的首节点是否为null，若为null，则创建链表，否则进入下一步。判断该首节点是否与插入的键值对的key和hash一致，若一致则替换该节点的值为value，否则进入下一步判断首节点是否为树节点，若是则调用树节点的putTreeVal()方法遍历红黑树，否则遍历链表。遍历红黑树时，若存在key和hash相同的节点就替换对应节点的值value，若不存在则插入新的树节点。遍历链表时，若存在key和hash相同的节点就替换对应节点的值为value。若找不到key和hash相同的节点，则链表尾部插入节点，同时进入下一步。若当前链表长度大于或等于树化阈值TREEIFY_THRESHOLD(8)时，则将链表转化为红黑树。get()方法源码分析除了HashMap的put()方法外，get()方法也是一个我们常用的方法，下面开始分析其关键的源码。get()方法/* * 返回key对应的value，如果不存在则返回null /public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }get()方法实际上是调用hash()方法获取到key的hash值调用getNode()方法通过key和hash获取对应的value，不存在则返回null。核心方法是getNode()方法，下面我会先分析一下getNode()方法。getNode()方法 /* * Map.get()方法的实际实现 * @param hash key的哈希值 * @param key 查询用的key * @return 节点或者是节点不存在是返回null */ final Node<K,V> getNode(int hash, Object key) { //tab用于暂存散列表table。first为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引 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 && ((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); } } //不存在对应的key，返回null return null; }getNode()方法的关键点：若散列表table不为null且长度大于0且其索引为(n - 1) & hash（等价于hash%n）的节点不为null。其中n为散列表长度，hash为插入的键值对的key的哈希值。则进入下一步，否则直接返回null判断首节点的key和hash是否与入参一致，若相同则返回首节点，否则进入下一步。判断节点个数只有1个，若是则返回null，否则进入下一步判断首节点是否为树节点，若是则遍历红黑树，否则为链表，进入下一步遍历链表，检索key和hash与入参相同的节点，若找到则返回该节点，否则返回null总结put()和get()方法是HashMap的常用方法，通过学习其源码了解到HashMap是如何使用拉链法解决哈希冲突。而下面将会通过两幅图展示put()和get()的执行过程：put()方法图解get()方法图解