千锋教育Java入门全套视频教程(java核心技术，适合java零基础，Java

HashMap源码分析

transient Node<K,V>[] table;//HashMap的底层实现

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

        boolean evict) {

  Node<K,V>[] tab; //临时数组   存放所有hash桶中的头节点

  Node<K,V> p; //临时节点 某一个桶的头节点（一个单向链表）

  int n, i;

  if ((tab = table) == null || (n = tab.length) == 0)//先赋值后判断

    n = (tab = resize()).length;//第一次初始化容量（16），之后为扩容

  if ((p = tab[i = (n - 1) & hash]) == null)

    //取hash后log n 位决定数值放在哪个位置

    //为了防止漏桶，n（容量）必须为2的多次方

    //无参，默认为16，扩容是翻倍

    //带参时，通过tableSizeFor方法获取设定容量最接近的大于容量的2的多次方，扩容是翻倍

    tab[i] = newNode(hash, key, value, null);//如果这个桶里一个元素都没有，则直接放入元素

  else {

    //指向的hash桶里有东西时

    Node<K,V> e; 

    K k;

    if (p.hash == hash &&//如果加入的key与第一个是一样的

      ((k = p.key) == key || (key != null && key.equals(k))))

      e = p;//用e暂存相同的节点

    else if (p instanceof TreeNode)//如果头结点是一个树节点

      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

    //调用红黑树的方法往树里添加节点，如果没有重复，返回null

    //如果有返回这个节点并用e暂存 

    else {//如果是链表

      for (int binCount = 0; ; ++binCount) {

        if ((e = p.next) == null) {//判断p的下一节点是否为空

          p.next = newNode(hash, key, value, null);//如为空，将数值放到此位置

          if (binCount >= TREEIFY_THRESHOLD - 1) // 是否树化

            treeifyBin(tab, hash);

          break;

        }

        if (e.hash == hash &&//找到相同节点

          ((k = e.key) == key || (key != null && key.equals(k))))

          break;

        p = e;

      }

    }

    if (e != null) { // 有相同节点时返回被覆盖的值

      V oldValue = e.value;

      if (!onlyIfAbsent || oldValue == null)

        e.value = value;

      afterNodeAccess(e);

      return oldValue;

    }

  }

  ++modCount;

  if (++size > threshold)//到达阈值后扩容

    resize();

  afterNodeInsertion(evict);

  return null;

}