基础知识

数据结构基础

  1. 数组：连续的内存块，不支持动态扩容，查询简单，直接通过下标即可获取对应元素【寻址容易，插入和删除困难】；
  2. 链表：非连续内存块，可动态扩容，但是不能通过下标查询【寻址困难，插入和删除容易】；

  3. 散列表：数组里保存的元素是链表，也叫哈希表，具体是通过Hash算法将数据内容和数据地址进行映射对应

    HashMap继承图

    image.png
    image.png

    什么是Hash

  4. 一种将数据内容和数据地址对应起来的算法；

  5. 把任意长度的内容通过Hash算法转化为统一长度的输出；
  6. 可以通过输入值唯一确定一个HashCode，但是不能通过HashCode唯一确定输入值，因为输入值的长度远远大于输出值，所以必然会有不同的输入值产生同一个输出值的情况；

  7. 多对一；

    HashMap数据结构

    HashMap的底层主要是数组和链表【也就是散列表】
    image.png

    Hash碰撞

    出现HashCode相同的情况

    树化

  8. 当散列表中的链表长度超过了8【这个值是固定的 -> TREEIFY_THRESHOLD】或者数组的长度大于64，HashMap将会对链表内容进行树化，将链表数据结构转化为红黑树；

    路由算法

    ( table.length - 1) & node.length

    源码分析

    基础参数

    1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // HashMap初始化容量大小，值为16
    2. static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量为32，是int的最大正值
    3. static final float DEFAULT_LOAD_FACTOR = 0.75f; // HashMap负载因子
    4. static final int TREEIFY_THRESHOLD = 8; // 链表树化阀值
    5. static final int UNTREEIFY_THRESHOLD = 6; // 树退化阀值
    6. static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化的数组长度
    8.  transient Node<K,V>[] table;
    10.  transient Set<Map.Entry<K,V>> entrySet;
    12.  transient int size;
    14.  transient int modCount;
    16.  int threshold;
    18.  final float loadFactor;

    构造方法

    ```java public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)

    1.  throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

    if (initialCapacity > MAXIMUM_CAPACITY)

    1.  initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <= 0 || Float.isNaN(loadFactor))

    1.  throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); // 无论传入的是什么数值，返回一个比这个数值大的2的次方数 }

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

  1. <a name="0owdI"></a>
  2. #### Node/TreeNode
  4. <a name="c8rrj"></a>
  5. #### tableSizeFor
  6. ```java
  7.     static final int tableSizeFor(int cap) {
  8.         int n = cap - 1; // 注意想想为什么要减一，不减一会造成什么情况
  9.         n |= n >>> 1;
  10.         n |= n >>> 2;
  11.         n |= n >>> 4;
  12.         n |= n >>> 8;
  13.         n |= n >>> 16;
  14.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  15.     }

putVal

reSize

get/remove/replace