Java集合5 - Map2

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

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 为空，先进行初始化
  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)
                      treeifyBin(tab, hash);
                  break;
              }
              if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                  break; // 覆盖
              p = e;
          }
      }
      if (e != null) { // 如果找到匹配的 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;
}

public HashMap(int initialCapacity, float loadFactor) {
 ...
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}

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

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

public class TestHashMap<K,V>{
  /**
   * 节点类
   *
   * @param <K>
   * @param <V>
   */
  class Node<K, V> {
      //键值对
      private K key;
      private V value;

      //链表，后继
      private Node<K, V> next;

      public Node(K key, V value) {
          this.key = key;
          this.value = value;
      }

      public Node(K key, V value, Node<K, V> next) {
          this.key = key;
          this.value = value;
          this.next = next;
      }
  }

  //默认容量
  final int DEFAULT_CAPACITY = 16;
  //负载因子
  final float LOAD_FACTOR = 0.75f;
  //HashMap的大小
  private int size;
  //桶数组
  Node<K, V>[] buckets;

  /**
   * 无参构造器，设置桶数组默认容量
   */
  public ThirdHashMap() {
    buckets = new Node[DEFAULT_CAPACITY];
    size = 0;
  }

  /**
   * 有参构造器，指定桶数组容量
   *
   * @param capacity
   */
  public ThirdHashMap(int capacity) {
    buckets = new Node[capacity];
    size = 0;
  }

   /**
   * 哈希函数，获取地址
   *
   * @param key
   * @return
   */
  private int getIndex(K key, int length) {
    //获取hash code
    int hashCode = key.hashCode();
    //和桶数组长度取余
    int index = hashCode % length;
    return Math.abs(index);
  }

  /**
   * put方法
   *
   * @param key
   * @param value
   * @return
   */
  public void put(K key, V value) {
    //判断是否需要进行扩容
    if (size >= buckets.length * LOAD_FACTOR) resize();
    putVal(key, value, buckets);
  }

  /**
   * 将元素存入指定的node数组
   *
   * @param key
   * @param value
   * @param table
   */
  private void putVal(K key, V value, Node<K, V>[] table) {
    //获取位置
    int index = getIndex(key, table.length);
    Node node = table[index];
    //插入的位置为空
    if (node == null) {
        table[index] = new Node<>(key, value);
        size++;
        return;
    }
    //插入位置不为空，说明发生冲突，使用链地址法,遍历链表
    while (node != null) {
        //如果key相同，就覆盖掉
        if ((node.key.hashCode() == key.hashCode())
                && (node.key == key || node.key.equals(key))) {
            node.value = value;
            return;
        }
        node = node.next;
    }
    //当前key不在链表中，插入链表头部
    Node newNode = new Node(key, value, table[index]);
    table[index] = newNode;
    size++;
  }

   /**
   * 扩容
   */
  private void resize() {
    //创建一个两倍容量的桶数组
    Node<K, V>[] newBuckets = new Node[buckets.length * 2];
    //将当前元素重新散列到新的桶数组
    rehash(newBuckets);
    buckets = newBuckets;
  }

  /**
   * 重新散列当前元素
   *
   * @param newBuckets
   */
  private void rehash(Node<K, V>[] newBuckets) {
    //map大小重新计算
    size = 0;
    //将旧的桶数组的元素全部刷到新的桶数组里
    for (int i = 0; i < buckets.length; i++) {
      //为空，跳过
      if (buckets[i] == null) {
          continue;
      }
      Node<K, V> node = buckets[i];
      while (node != null) {
          //将元素放入新数组
          putVal(node.key, node.value, newBuckets);
          node = node.next;
      }
  }

  /**
     * 获取元素
     *
     * @param key
     * @return
     */
  public V get(K key) {
    //获取key对应的地址
    int index = getIndex(key, buckets.length);
    if (buckets[index] == null) return null;
    Node<K, V> node = buckets[index];
    //查找链表
    while (node != null) {
      if ((node.key.hashCode() == key.hashCode())
              && (node.key == key || node.key.equals(key))) {
          return node.value;
      }
      node = node.next;
    }
    return null;
  }
}