集合源码小随笔

矫情吗；* 2023-03-01 12:20 3阅读 0赞

# 集合源码学习 #

## ArrayList ##

> DEFAULT\_CAPACITY初始容量大小默认是**10**；

int size;(表示当前数组大小，非线程安全)；

modCount统计当前数组被修改的版本次数，结构有变化就+1；

### 注释 ###

1.  **允许put null值；**
2.  随机访问时间复杂度为O（1）；
3.  非线程安全，多线程使用Collections下的synchronizedList；（也可以使用JUC下的CopyOnWriteList）;
4.  foreach和迭代器中数组大小改变，会抛出异常；

### 初始化 ###

1.  无参数构造器（**数组大小为空，并不是10，10是第一次add扩容时候的数据**）；
2.  指定大小初始化（会对elementData进行实例化，elementData的数组长度就是传入的int）；
3.  指定初始化数据初始化（传入一个集合）；

### 添加和扩容 ###

添加时先判断是否需要扩容，需要就执行扩容操作；否则直接赋值；

public boolean add(E e) {
        
            ensureCapacityInternal(size + 1);//判断是否扩容
            elementData[size++] = e;//赋值
            return true;
        }
    
    private void ensureCapacityInternal(int minCapacity) {
        
      //如果初始化给了默认值，以初始化大小为主；     
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    				//确保容积足够
            ensureExplicitCapacity(minCapacity);
        }
    
    private void ensureExplicitCapacity(int minCapacity) {
        
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    //扩容
    private void grow(int minCapacity) {
        
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);//每次扩容1.5倍
      			//如果扩容后的数值<期望值  
      			//扩容后的值就=期望值
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
      			//如果扩容后的数值>JVM所能分配的最大值，就使用Integer最大值
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
      //数组拷贝
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

Tips：

>  *  扩容规则：原来的容量+（原来容量\*0.5）；
>  *  数组最大值是Integer.MAX\_VALUE；
>  *  可以添加null；
>  *  扩容时候数组大小溢出判断，下标不能小于0，不能大于Integer.MAX\_VALUE；
>  *  elementDate\[size++\] （线程不安全）；

扩容调用的方法是arraycopy（native）；

### 删除 ###

多种删除方式：

*  根据索引删除；
 *  根据值删除；
 *  批量删除；

//根据值删除
    public boolean remove(Object o) {
        
      		//删除null
            if (o == null) {
        
                for (int index = 0; index < size; index++)
                  //遍历数组找到第一个为null的元素删除	  
                  if (elementData[index] == null) {
        
                        fastRemove(index);
                        return true;
                    }
            } else {
        
                for (int index = 0; index < size; index++)
                  	//找到要第一个要删除值，进行删除  
                  if (o.equals(elementData[index])) {
        
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
    //传入索引位置删除
    private void fastRemove(int index) {
        
      //记录结构改版次数
            modCount++;
      //计算需要移动的元素
            int numMoved = size - index - 1;
            if (numMoved > 0)
              //元素移动调用arraycopy
                System.arraycopy(elementData, index+1, elementData, index,numMoved);
      		//数组的最后一个位置赋值null，GC就可以清理了
            elementData[--size] = null; // clear to let GC do its work
        }

Tips：

>  *  **删除时是允许删除null的；**
>  *  **其中判断值相等使用的是equals，如果数组不是基本类型，需要重写equals；**

### 迭代器(实现Iterator接口) ###

参数

//下一个元素的位置
    int cursor;       // index of next element to return
    //上次迭代过程中索引的位置，-1代表已经删除
    int lastRet = -1; // index of last element returned; -1 if no such
    //期望的版本号
    int expectedModCount = modCount;

方法

*  hasNext（判断还有没有可以迭代的值）；
 *  next（如果有可以迭代值，返回迭代的值）；
 *  remove（删除当前迭代的值）；

**ArrayList只有作为共享变量时，才会有线程安全问题；局部变量是不存在线程安全问题的；**

## LinkedList ##

底层数据结构是双向链表

*  链表节点是Node，里面有prev和next；分别指向前一个节点和后一个节点；
 *  first为双向链表的头指针，它的前一个节点是null；
 *  last为双向链表的尾指针，它的下一个节点是null；
 *  当链表中没有数据的时候，first和last是同一个节点，前后都为null；
 *  双向链表只要机器内存足够大，是没有大小限制的；

//Node节点内部类
    private static class Node<E> {
        
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
        
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

### 新增（头部与尾部） ###

> **add默认尾部追加；**（add方法和addLast方法调用的都是linkLast，addLast是void）
> 
> addFirst从头部添加；

//尾部追加元素 
    void linkLast(E e) {
        
      //暂存last指针
            final Node<E> l = last;
      //新建节点，l为prev，e为追加的节点，null为next      
      final Node<E> newNode = new Node<>(l, e, null);
      //尾指针指向追加节点      
      last = newNode;
      //如果链表为空（尾指针为空，即链表为空）
            if (l == null)
              //头指针也指向追加节点
                first = newNode;
            else
              //链表不为空，前尾节点指向追加节点
                l.next = newNode;
      //更新大小和版本
            size++;
            modCount++;
        }
    
    //头部添加元素
    private void linkFirst(E e) {
        
      //暂存first指针
            final Node<E> f = first;
      //新建节点
            final Node<E> newNode = new Node<>(null, e, f);
      //first指向新添加的头结点
            first = newNode;
      //如果first指针为null，即链表为空
            if (f == null)
              //尾指针也指向新增的节点
                last = newNode;
            else
              //之前链表头结点的prev节点即新增节点
                f.prev = newNode;
      //更新大小和版本
            size++;
            modCount++;
        }

### 删除 ###

//从头部删除     f是链表的first
    private E unlinkFirst(Node<E> f) {
        
            // assert f == first && f != null;
      //拿到头结点的值，作为返回值
            final E element = f.item;
      //存储删除后的链表
            final Node<E> next = f.next;
      //头结点赋值null
            f.item = null;
      //头结点的next指向null  方便GC
            f.next = null; // help GC
      //更新first指针，指向删除后的链表
            first = next;
      //如果删除后的链表为null
            if (next == null)
              //尾节点也指向null
                last = null;
            else
              //删除后的链表的prev指向null
                next.prev = null;
      //更新大小和版本
            size--;
            modCount++;
            return element;
        }
    
    //删除尾节点   l=last
     private E unlinkLast(Node<E> l) {
        
            // assert l == last && l != null;
       //存储删除节点的值
            final E element = l.item;
       //存储删除节点之前的链表
            final Node<E> prev = l.prev;
       //删除的节点赋值null
            l.item = null;
       //删除链表的prev指向null  方便GC
            l.prev = null; // help GC
       //更新last指向删除后的链表
            last = prev;
       //如果删除后的链表为null
            if (prev == null)
              //first也指向null
                first = null;
            else
              //删除后链表的next指向null
                prev.next = null;
       //更新大小和版本
            size--;
            modCount++;
            return element;
        }

> **LinkedList新增删除均为O（1）；**

### 查询 ###

//查询，获取指定索引的值
    public E get(int index) {
        
      //检查index是否合法
            checkElementIndex(index);
      //返回index节点的值
            return node(index).item;
        }
        
    //返回index索引的节点
    Node<E> node(int index) {
        
            // assert isElementIndex(index);
    //如果index处于链表的前一半
            if (index < (size >> 1)) {
        
                Node<E> x = first;
              //从头向inde遍历，返回index节点
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
        //如果index处于链表的后半部分
                Node<E> x = last;
              //从后向index遍历，返回index节点
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

> **采取简单二分法（分为前半部分查找或者者后半部分查找）**
> 
> 并不是完全的二分查找（二分查找针对数组）；

### 方法对比（LinkedList实现了Deque接口） ###

<table> 
 <thead> 
  <tr> 
   <th>含义</th> 
   <th>one</th> 
   <th>two</th> 
   <th>区别</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>新增</td> 
   <td>add(e)</td> 
   <td>offer(e)调用的add(e)</td> 
   <td>无区别</td> 
  </tr> 
  <tr> 
   <td>删除</td> 
   <td>remove()删除头结点</td> 
   <td>poll()出队头结点</td> 
   <td>链表为null，remove会抛出异常，poll返回null；</td> 
  </tr> 
  <tr> 
   <td>查找</td> 
   <td>element()获取头结点的值</td> 
   <td>peek()获取头结点的值</td> 
   <td>链表为null，element会抛出异常，peek会返回null；</td> 
  </tr> 
 </tbody> 
</table>

### 迭代器（双向迭代访问，实现ListIterator接口） ###

<table> 
 <thead> 
  <tr> 
   <th>顺序</th> 
   <th>方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>从尾到头</td> 
   <td>hasPrevious、previous、previousIndex</td> 
  </tr> 
  <tr> 
   <td>从头到尾</td> 
   <td>hasNext、next、nextIndex</td> 
  </tr> 
 </tbody> 
</table>

//上次调用next和previous迭代的节点		
    				private Node<E> lastReturned;
    //下一个节点
            private Node<E> next;
    //下一个节点索引
            private int nextIndex;
    //期望的版本号
            private int expectedModCount = modCount;

## List面试题 ##

> #### 谈谈你对ArrayList理解 ####

1.  ArrayList底层是动态数组，线性存储；
2.  初始化构造器主要有三种，一是默认无参构造器，初始化数组为空，在第一次添加元素后数组容量扩容至默认值10；二是传入int类型，也就是数组的容量；三是传入集合，转换为数组进行使用；
3.  其API都做了一层对数组底层访问的封装，比如add方法，先判断数组是否需要扩容，然后再做元素的添加，并且可以添加null；提供了多种删除操作，根据索引，根据值，批量删除等，最终实现都是先拿到删除的元素索引，是允许删除null的，判断删除元素是否相等调用的是equals方法，调用native方法arraycopy进行剩余元素位置的移动，保证顺序性；
4.  由于ArrayList底层没有加锁，也没有使变量可见，当ArrayList作为共享变量时会引发线程安全问题；
5.  ArrayList随机访问时间复杂度达到O（1），删除和修改最差会达到O（n）；

#### 数组初始化，加入一个值后，如果使用addAll方法，一次加入15个值，那么最终数组大小是多少？ ####

数组初始化后加入一个值后，实际大小是1，第一次扩容默认值为10；加入15个后，数组容量依旧不够，需要进行扩容，扩容公式为：旧容量+（旧容量\*0.5）=15；但是需要放16个元素还是不够，源码中对这种情况做了处理，当扩容后的容量<期望扩容的最小容量，那么本次扩容的容量就=期望扩容的大小=15+1=16；

// newCapacity 本次扩容的大小，minCapacity 我们期望的数组最小大小
    // 如果扩容后的值 < 我们的期望值，我们的期望值就等于本次扩容的大小
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

#### 扩容为什么消耗性能 ####

底层调用arraycopy方法，会进行数组数据拷贝，性能消耗严重；

#### 扩容值得借鉴的地方？ ####

*  自动扩容的思想值得借鉴，根据容量大小自动处理，无需手动调用；1.5倍扩容速度，前期缓慢，后期速度快，大部分使用数组数据量并不是很大，所以缓慢增长也有利于节省资源；
 *  有数组大学溢出的意识，数组最大是Integer.MAX\_VALUE,最小是0；

#### 有一个 ArrayList，数据是 2、3、3、3、4，中间有三个 3，现在我通过 for (int i=0;i<list.size ();i++) 的方式，想把值是 3 的元素删除，请问可以删除干净么？最终删除的结果是什么，为什么？ ####

List<String> list = new ArrayList<String>() {
        {
        
      add("2");
      add("3");
      add("3");
      add("3");
      add("4");
    }};
    for (int i = 0; i < list.size(); i++) {
        
      if (list.get(i).equals("3")) {
        
        list.remove(i);
      }
    }

删除不干净，每次删除的时候，剩余的元素都会前移，但是i是不断增长的，导致最后一个3被遗漏无法删除；

#### 为什么增强for循环删除元素会抛出异常？ ####

增强for循环调用的是迭代器的next方法，调用list\#remove方法时候，modCount++，版本变化，但是迭代器中期望版本号没有变化，就会抛出异常；

#### 使用Iterator.remove可以删除吗？ ####

可以，因为这个remove方法每次删除的时候对期望版本号做了更新；

> **LinkedList上述三个问题答案一致；**

## HashMap ##

底层是数组+链表+红黑树

链表长度>=8&数组大小>64，链表会转换为红黑树；

红黑树大小<=6，红黑树会转化成链表；

### 注释 ###

*  **允许null值**，线程不安全的；
 *  load fator（负载因子）默认是**0.75**，是均衡了时间和空间损耗算出来的，较高的值会减少空间开销，但是增大了查找成本（哈希冲突增加，链表长度变长）影响查询效率，**不扩容条件：数组容量>需要数组大小/负载因子**；
 *  如果有很多数据需要存储到hashmap中，可以将容量直接设置足够，避免不断扩容的性能开销；
 *  如果在迭代过程中，hashmap结构修改，会快速失败；

### 属性 ###

//hashmap初始容量16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //链表长度大于等于8，转化红黑树
    static final int TREEIFY_THRESHOLD = 8;
    //红黑树大小小于等于6，转化链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //数组容量大于64，链表才会转化红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
    //版本
    transient int modCount;
    //扩容门槛两种计算方式
    //在初始化时候给定数组大小，通过tableSizeFor方法计算，数组大小接近2*幂次方，比如给定19，实际大小是2*5=32
    //resize自动扩容，大小=负载因子*数组容量
    int threshold;
    //存储数据的数组
    transient Node<K,V>[] table;
    //链表节点
    static class Node<K,V> implements Map.Entry<K,V> {
        
    //红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

//添加
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
      //如果数组为空，使用resize初始化数组
            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 {
        
              //如果当前索引位置不为空，解决hash冲突
                Node<K,V> e; K k;
              //如果key的hash和值都相等
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                  //把当前下标位置的node赋值给临时变量
                    e = p;
              //如果是红黑树节点，进行新增
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
              //如果是链表，新节点放入链表尾
                else {
        
                  //binCount计算链表长度
                    for (int binCount = 0; ; ++binCount) {
        
                      //遍历链表，直到尾节点
                        if ((e = p.next) == null) {
        
                          //赋值
                            p.next = newNode(hash, key, value, null);
                          //如果链表长度 >= 8
                            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;
                    }
                }
              //如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                  // 当 onlyIfAbsent 为 false 时，才会覆盖值 
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
      //版本更新
            ++modCount;
      //是否需要扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

> 链表长度>=8，数组大小>64才会转换红黑树，如果数组大小<64，会扩容，不会转换红黑树；
> 
> 链表查询为O（n），红黑树为O（logn）；在链表长度不长的时候效率也是比较高的，只要链表足够长才会转换红黑树，因为红黑树占用空间是链表的2倍，基于空间和时间的损耗，最后确定为8；

> **红黑树特点**

1.  节点是红色或黑色
2.  根是黑色
3.  所有叶子都是黑色
4.  从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
5.  从每个叶子到根的所有路径上不能有两个连续的红色节点

> **HashMap和HashTable区别**

*  HashMap 允许 key 和 value 为 null，Hashtable 不允许。
 *  HashMap 的默认初始容量为 16，Hashtable 为 11。
 *  HashMap 的扩容为原来的 2 倍，Hashtable 的扩容为原来的 2 倍加 1。
 *  HashMap 是非线程安全的，Hashtable是线程安全的。
 *  HashMap 的 hash 值重新计算过，Hashtable 直接使用 hashCode。
 *  HashMap 去掉了 Hashtable 中的 contains 方法。
 *  HashMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类。

### 查找 ###

1.  通过hash函数计算hash值，通过数组找到目标节点first（比较hash值和key值），符合条件就返回first；
2.  如果first不是目标节点，并且first节点的next节点不为空
3.  判断first是红黑树（走4）还是链表（走5）；
4.  是红黑树调用红黑树的getTreeNode方法；
5.  是链表就遍历链表，找到key值相同的节点返回；
6.  找不到返回null；

//链表遍历
    do {
        
      //如果hash值相等，key值相等，就返回节点
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
      //继续遍历
                    } while ((e = e.next) != null);

Tips：

*  HashMap每次扩容2倍；
 *  扩容之后，会根据新的数组容量重新计算hash值；

static final int hash(Object key) {
        
            int h;
       //将hash的hashcode的高16位参与异或（^）运算，重新计算hash值
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

> **定位到hash桶数组的步骤：**

1.  先计算key的hash值；
2.  将 hashCode 的高位参与运算，重新计算 hash 值（**hashcode的高16位参与运算，让数组下标更加散列**）；
3.  将计算出来的 hash 值与 (table.length - 1) 进行 & 运算（**length基本都小于2^16，所以是hashcode的低16位参与运算**）；

## TreeMap ##

底层是红黑树；

TreeMap使用红黑树对key进行排序；

> 排序的两种方式（需要自行定义排序规则）

1.  传入外部比较器Comparator；
2.  实现Comparable的compareTo方法；

## LinkedHashMap ##

增加了链表结构，继承HashMap，拥有HashMap的所有特性，在这个基础上增加了两大特性：

1.  按照插入顺序进行访问；
2.  实现了访问最少最先删除功能，其目的就是删除很久没有访问的节点；

//键值对继承hashmap
    static class Entry<K,V> extends HashMap.Node<K,V> {
        
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
        
                super(hash, key, value, next);
            }
        }
    //默认是false
    //true是按照访问顺序，会把经常访问的数据放在前面
    //false是按照插入顺序访问
    final boolean accessOrder;
    //链表尾   
    transient LinkedHashMap.Entry<K,V> tail;
    //链表头       
    transient LinkedHashMap.Entry<K,V> head;

LinkedHashMap的节点类似于HashMap的节点，链表每次使用尾插法就能保证插入顺序；

### 添加 ###

插入方法使用的是HashMap的put方法，按照顺序新增；

LinkedHashMap主要重写hashmap的newTreeNode方法（新建节点）、afterNodeAccess（将每次访问的元素移动到链表尾）方法和afterNodeAccess方法（删除链表头不经常访问的元素）；

//重写hashmap的newTreeNode方法、afterNodeAccess方法和afterNodeAccess方法；
        TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        
          //新建节点
            TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
          //追加链表尾部
            linkNodeLast(p);
            return p;
        }
    
    
     // 链表尾部添加元素
        private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        
          //存储之前的尾节点
            LinkedHashMap.Entry<K,V> last = tail;
          //更新tail  
          tail = p;
          //如果之前链表为null
            if (last == null)
              //头指针也指向新添加的节点
                head = p;
            else {
        
              //链表不为null
              //更新链表结构
                p.before = last;
                last.after = p;
            }
        }

### 迭代访问 ###

> **LinkedHashMap只支持单向访问，即按照插入顺序从头到尾访问；**

可使用 `LinkedHashMap.entrySet().iterator()` 这种写法直接返回 LinkedHashIterator 迭代器；

//构造器   头结点是第一个访问的节点
    LinkedHashIterator() {
        
                next = head;
                expectedModCount = modCount;
                current = null;
            }
                 
    final LinkedHashMap.Entry<K,V> nextNode() {
        
                LinkedHashMap.Entry<K,V> e = next;
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
                current = e;
                //向后遍历
                next = e.after;
                return e;
            }

### 访问最少删除策略（LRU，最久未被使用） ###

> 如果**设置了accessOrder为true**，将经常访问的元素追加到链表尾，不经常访问的元素就会靠近链表头，然后删除头结点；

//afterNodeAccess方法将每次访问的节点移动到队尾，不经常访问的元素自然会压到链表头；
      
      
    //删除链表头
      void afterNodeInsertion(boolean evict) {
         // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
        //accessOrder为true
            if (evict && (first = head) != null && removeEldestEntry(first)) {
        
                K key = first.key;
              //删除头结点  调用hashmap的removeNode方法
                removeNode(hash(key), key, null, false, true);
            }
        }

### Map面试题 ###

> #### HashMap、TreeMap、LinkedHashMap的相同点和不同点？ ####

相同点：

1.  三者底层在特定情况下都会用到红黑树；
2.  底层的hash算法相同；
3.  在迭代过程中，如果map结构发生变化，就会快速失败抛出ConcurrentModificationException异常；

不同点：

1.  HashMap的结构以数组为主，查询最快是O（1）；TreeMap数据结构以红黑树为主，可以实现key的排序；LinkedHashMap继承了HashMap，增加了链表的结构，实现了可以根据插入顺序访问和最少访问删除策略；
2.  使用场景不同，TreeMap适用于需要对key进行排序的场景，LinkedHashMap适用于按照插入顺序访问或者要删除最近最少访问元素的场景，其余场景使用HashMap即可；
3.  由于三种Map底层数据结构不同，封装的api也略有不同；

#### Map的hash算法解释 ####

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

主要是为了计算的hashcode更加散列，无符号右移16位再进行异或，达到高16位和低16位都参与运算；

#### 解决hash冲突办法？ ####

1.  好的hash算法，例如hashcode^(hashcode>>>16);
2.  自动扩容，数组快满时，自动扩容减少hash冲突；
3.  hash冲突发生时，采用链表解决；
4.  hash严重时，链表转换红黑树；

#### hash冲突时怎么办？ ####

hash冲突是指hashcode相同，但是key值不同的情况；

如果数组中节点已经是链表了，就在尾部追加；

如果已经是链表并且长度大于8：

1.  数组大小大于64，转换为红黑树；
2.  数组大小小于64，数组再次扩容；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70][]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]

## HashSet（组合HashMap封装复用） ##

1.  底层是基于HashMap的，不保证插入顺序；
2.  不考虑hash冲突，时间复杂度为O（1）；
3.  线程不安全；
4.  迭代过程中结构改变，快速失败；

> **HashSet使用的是组合HashMap，而非继承**

1.  由于Java是单继承，继承之后很难扩展；
2.  组合会更加灵活，组合就是在HashSet的方法内部调用HashMap的方法;

//hashmap作为变量
    private transient HashMap<E,Object> map;
    //hashmap的value
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

> hashset基于hashmap实现，add方法只有一个入参，\*\*将value设置为默认值（final修饰的object）；\*\*将复杂或者无用的参数

### 初始化 ###

1.  无参构造；
2.  传入int容量构造；
3.  传入int容量和float负载因子构造；
4.  传入集合构造；

//传入集合构造
    //如果集合容量<16,初始化选择16；
    //反之选择扩容阈值+1，+1的话就刚好比扩容阈值（期望值/0.75）大1，不会扩容；
    public HashSet(Collection<? extends E> c) {
        
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

> 如果往hashmap中拷贝大集合时，可以借鉴上面的方法，**取最大值（期望值/0.75+1，默认值16）**；

### 添加 ###

//调用put方法
    public boolean add(E e) {
        
        return map.put(e, PRESENT)==null;
    }

## TreeSet（组合TreeMap封装复用） ##

> **TreeSet组合TreeMap两种实现**
> 
> 1.  TreeSet中的简单方法（例如add调TreeMap的put）直接调用TreeMap的方法；（适用于**简单**场景）
> 2.  TreeSet实现了NavigableSet接口定义实现方法的规范，让TreeMap中的内部类KeySet也实现了Navigable接口并进行方法实现内部逻辑；（适用于**复杂**场景）

### Set面试题 ###

#### TreeSet使用场景 ####

需要对元素进行排序时使用，使用时元素最好实现Comparable接口，这样方便底层的TreeMap对key进行排序；

#### 如果要按照key插入顺序进行遍历怎么办？ ####

使用LinkedHashSet（底层是LinkedHashMap）；

> #### TreeSet和HashSet底层结构和原理？ ####

HashSet（将hashmap中的value定义为final object固定值）：

1.  底层对hashmap进行了封装复用，准确说是组合hashmap，也就是直接在内部定义hashmap调用hashmap的方法，例如hashset的add方法就是调用hashmap的put方法；
2.  hashset不保证添加元素的顺序；
3.  不是线程安全的；
4.  迭代时结构改变，会快速失败；

TreeSet（思路与hashset稍有区别）：

1.  （对于简单的方法）底层组合了TreeMap进行封装复用，定义treemap并且进行方法调用；
2.  （对于复杂的方法）TreeSet实现了NavigableSet接口并且进行了对实现方法进行了规范，然后让TreeMap的内部类keySet也去实现NavigableSet接口并且实现了方法的内部逻辑，然后TreeSet就可以直接复用TreeMap实现的复杂方法了；

## 集合使用经验 ##

#### 1. 集合批量新增/删除（新增推荐使用addAll/putAll，删除推荐removeAll） ####

在list和map需要新增大量数据的时候，不用使用for循环+add/put方法来新增；这样会导致多次扩容，性能开销很大；尽量使用addAll或者putAll方法新增大量数据，这样只会扩容一次。

> **在使用集合的时候最好能给集合赋上初始值，避免多次扩容造成性能开销。**

#### 2. 当集合的元素是自定义类时，强制重写hashcode和equals方法； ####

#### 3. 所有集合类在迭代过程中使用集合类的remove删除元素都会快速失败，抛出ConcurrentModificationException异常，**推荐使用迭代器的删除方法**； ####

> #### 4.数组转集合list使用**Arrays.asList（array）**，使用这个方法时需要注意两点： ####
> 
> 1.  修改数组的值，会直接影响list；
> 2.  转换后的list使用add、remove等操作的时，会报异常；

> #### 5.集合list转数组的时候，一般调用**toArray**方法；无参方法会报错，这个方法必须使用有参方法（定义一个数组去接受结果）： ####
> 
> 1.  数组长度<list.size，得到的数组是null；
> 2.  数组长度=list.size，得到的数组正确；
> 3.  数组长度>list.size，多出的数组元素是null；

## JDK7与JDK8变化 ##

所有集合都新增了forEach方法（其实JDK7就有了，default修饰，无需强制实现）；

forEach入参是函数式接口，更加简洁；

### ArrayList ###

ArrayList JDK7无参初始化容量是10；

JDK8初始化为空，第一次add才扩容至10；

### HashsMap ###

1.  JDK8中无参构造器中丢弃了JDK7中直接初始化16的做法，而是采用第一次put才开始扩容至16；
2.  hash算法不同，JDK7更加简单，JDK8使用hashcode^（h>>>16）;
3.  JDK7结构是数组+链表；JDK8是链表+数组+红黑树；
4.  JDK8新增了getOrDefault（如果存在key就返回key，不存在返回期望值）、putIfAbsent（如果存在key，就不覆盖）方法等；

### LinkedHashMap ###

个别方法名改变；例如recordRemoval——afterNodeRemoval；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200725084626978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200725084645920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70