盘点 HashMap 源码中的那些优雅的设计！

今日推荐
程序员被公司辞退12天，领导要求回公司讲代码
感受 lambda 之美！
彻底搞懂 Nginx 的五大应用场景
低代码杀疯了
批处理框架 Spring Batch 这么强，你会用吗？华为，被谷歌正式“除名”

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 初始化桶数组 table， table 被延迟到插入新数据时再进行初始化
        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;
            //如果hash相等，并且equals方法返回true，这说明key相同，此时直接替换value即可，并且返回原值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
             //如果第一个节点是树节点，则调用putTreeVal方法，将当前值放入红黑树中
            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);
                        //判断链表中节点树是否超多了阈值8，如果超过了则将链表转换为红黑树（当然不一定会转换，treeifyBin方法中还有判断）
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果在链表中找到，完全相同的key，则直接替换value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //e!=null说明只是遍历到中间就break了，该种情况就是在链表中找到了完全相等的key,该if块中就是对value的替换操作
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //加入value之后，更新size，如果超过阈值，则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. 
Because the table uses power-of-two masking, 
sets of hashes that vary only in bits above the current mask will always collide.
(Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) 
So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed,
utility, and quality of bit-spreading. 
Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), 
and because we use trees to handle large sets of collisions in bins, 
we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, 
as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

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);

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);

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;
  }

f (++size > threshold)
       resize();

Java网站推荐：www.java1000.com，网站包括Java基础、进阶、源码、面试等各个系列文章，欢迎浏览！Github仓库推荐：https://github.com/OUYANGSIHAI/JavaInterview，复制链接直达，该仓库是本人面试一年的面试记录与分享，相信对你有一定的帮助！
推荐文章

1、14个项目！
2、Spring Boot + Security + MyBatis + Thymeleaf + Activiti 快速开发平台项目
3、推荐几个支付项目！
4、写博客能月入10K？
5、一款基于 Spring Boot 的现代化社区（论坛/问答/社交网络/博客）
更多项目源码
1、推荐两个项目！2、重磅推荐：一套开源的网校系统，无论是自建网校还是接副业都很方便
3、一款基于 Spring Boot 的现代化社区（论坛/问答/社交网络/博客）
4、13K点赞都基于 Vue+Spring 前后端分离管理系统ELAdmin，大爱5、想接私活时薪再翻一倍，建议根据这几个开源的SpringBoot