README.md · starry陆离/Java集合源码

# 为什么要有集合

```java
/**
 * 数组的不足
 * 1.长度一旦确定就无法变化（不能动态扩容）
 * 2.保存的数据类型必须相同
 * 3.增加和删除麻烦
 */
```

# 集合的遍历

可以看到Collection接口继承了Iterable接口（接口与接口之间的关系是继承）

![image-20221114165510809](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141655926.png)

在Iterable接口中有一个Iterator类型的iterator()方法，所以继承了Iterable接口，或者说继承了Collection的所有子类都会实现这个方法

![image-20221114170146901](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141701025.png)

在Iterator接口中有两个重要的方法hasNext()和next()；

> hasNext()：如果迭代有更多的元素，则返回true。(换句话说，如果next将返回一个元素而不是抛出异常，则返回true。)如果迭代有更多的元素，返回:true
>
> next()：返回迭代中的下一个元素。如果迭代中没有更多的元素，则抛出NoSuchElementException异常

![image-20221114170538572](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141705718.png)

```java
//迭代器Iterator  主要用于遍历实现Iterator接口的集合中的元素
//实现Iterator接口的集合必须实现iterator()方法，返回值是一个Iterator对象
```

```java
package collection_;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class Collection1 {
    public static void main(String[] args) {
        Collection list=new ArrayList();

//迭代器Iterator  主要用于遍历实现Iterator接口的集合中的元素
        //实现Iterator接口的集合必须实现iterator()方法，返回值是一个Iterator对象

//添加元素
        list.add("黎旭");
        list.add(16);
        list.add(true);
        //1.得到list的迭代器
        Iterator iterator=list.iterator();
        //2.遍历集合元素  hasNext()方法判断是否还有下一个元素
        while (iterator.hasNext()) {
            //3.next()返回下一个元素
            Object next =  iterator.next();
            System.out.println(next);
        }
        //快捷键 itit+回车
        //ctrl+j->显示所有快捷键的快捷键
        iterator.next();
        //抛出异常：NoSuchElementException
        //因为此时iterator指向的是list集合的最后一个元素，再调用iterator.next();取下一个元素为空
        //所以再使用next()前要调用hasNext()判断
    }

}

```

# 集合框架

单列集合：放单个元素Set(有序),List(无序)

双列元素：放键值对Map

> 学习方法：结合源码去记忆继承与实现关系

![image-20221103190836298](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211031908514.png)

# collection接口的常用方法

# 迭代器Iterator

![image-20221103192710967](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211031927110.png)

# 增强for循环

![image-20221103193253978](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211031932123.png)

值得注意的是我们的增强for循环底层也是调用了iterator()，返回了一个迭代器（因为我这里定义的是ArrayList实现类，所以debug会来到ArrayList类的iterator()方法中，再次证实继承了Collection的所有子类都会实现这个方法）

![image-20221103193525231](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211031935380.png)

![image-20221114171016345](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141710536.png)

# List接口的方法

![image-20221103194229507](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211031942296.png)

# ArrayList的特点与扩容机制

```java
package list_;

import java.util.ArrayList;

public class ArrayList_ {
    public static void main(String[] args) {
        ArrayList arrayList=new ArrayList();

//1.可以放入空值
        arrayList.add(null);
        arrayList.add(null);
        arrayList.add(null);
        arrayList.add(null);
        //2.底层是用数组实现的
        //3.ArrayList是线程不安全的（看源码）
        /*没有加synchronized(用来进行线程互斥操作)
        todo 
            public boolean add(E e) {
                ensureCapacityInternal(size + 1);  // Increments modCount!!
                elementData[size++] = e;
                return true;
               }
        */

System.out.println(arrayList);

}
}
```

ArrayList是线程不安全的（看源码）
add操作没有加synchronized(用来进行线程互斥操作)

![image-20221114171545869](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141715987.png)

![image-20221103195623159](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211031956218.png)

```java
/**
 * 1.维护的是一个Object  elementData[]数组
 * 2.有三个构造函数，无参构造
 *   - 会初始化elementData容量为0
 *   - 第一次添加则扩容为10
 *   - 如果再添加扩容为elementData的1.5倍
 * 3.如果使用的是指定大小的构造器
 *   - 初始化elementData容量为指定大小
 *   - 如果需要扩容，则直接按elementData的1.5倍扩容
 *   - 例如指定初始大小为8，则8-》8*1.5=12-》12*1.5=18-》18*1.5=27
 */
```

### 无参构造

```java
//待debug的代码
ArrayList arrayList=new ArrayList();
for(int i=1;i<=10;++i){
    arrayList.add(i);
}
arrayList.add(100);

/**
 * 无参构造
 * 1.创建一个空的elementData数组={}
 * 2.执行list.add
 *      (1)先确定是否需要扩容
 			Explicit：确切的，清楚明白的  Internal:内部的，本质的
 *          - 调用ensureCapacityInternal先确定elementData是否是一个空数组 
 *          - 如果是那就确定需要扩容的大小，第一次扩容是10（DEFAULT_CAPACITY = 10）
 *          - 最后调用ensureExplicitCapacity 确认是否真的需要扩容
 *          modCount记录集合被修改的次数 防止多个线程修改minCapacity
 *      (2)如果需要扩容那就调用grow(),否则直接赋值
 *
 * 3.需要扩容执行grow()
 *   grow()真正扩容
 *      采用扩容机制
 *      第一次初始容量为0时 扩容到10
 *      之后每次都是按1.5倍扩容
 *      Array.copyOf()
 */
```

第一次加入数据触发第一次扩容：

![image-20221114174626958](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141746261.png)

扩容的关键代码：

> 增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量。minCapacity—所需的最小容量

每次都先获取原来的数组容量，然后将其oldCapacity + (oldCapacity >> 1);也就是乘1.5倍（因为是无符号右移相当于除2）

每次扩容都会执行这个操作，当然除第一次扩容时，数组为空=0，所以我们代码逻辑执行这一行逻辑代码

```java
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
```

将所需的最小容量，其实也就是10赋值给newCapacity，作为第一次扩容的容量大小。

![image-20221114175122338](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141751510.png)

### 有参构造

```java

/*有参构造
1.创建的不再是一个空，而是一个指定大小的elementData数组={指定大小}
2.其后操作相同*/

ArrayList arrayList1=new ArrayList(8);
for (int i=0;i<=8;++i){
    arrayList1.add(i);
}

```

> 构造具有指定初始容量的空列表。如果指定的初始容量为负数，则抛出:IllegalArgumentException

![image-20221114180158896](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211141801060.png)

https://edrawcloudpubliccn.oss-cn-shenzhen.aliyuncs.com/viewer/self/28828983/share/2022-11-14/1668418152/main.svg

> 注意关闭IDEA的debugger的简略输出模式并且不隐藏空值
>
> ![image-20221104091746060](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211040917175.png)

# Vector底层结构和源码分析

Vector是线程安全的

![image-20221104094819510](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211040948542.png)

### 比较Vector和ArrayList

![image-20221104094939115](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211040949202.png)

```java
无参构造器
* //1.默认扩容10，其实这里的无参构造调用的也是有参构造this(10),不过默认传入的是10而已
* /**
*      public Vector() {
*         this(10);
*     }
* /
* 2.执行add()方法
* /**
*      public synchronized boolean add(E e) {
*         modCount++;
*         ensureCapacityHelper(elementCount + 1);
*         elementData[elementCount++] = e;
*         return true;
*     }
* 3.执行ensureCapacityHelper确认是否真的需要扩容
* /**
*      private void ensureCapacityHelper(int minCapacity) {
*         // overflow-conscious code
*         if (minCapacity - elementData.length > 0)
*             grow(minCapacity);
*     }
* 4.如果需要扩容，就执行grow()方法
* /** 每次扩容都是2倍扩容
*     int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
*                    capacityIncrement : oldCapacity);
*
*     }         
```

1.默认扩容10，其实这里的无参构造调用的也是有参构造this(10),不过默认传入的是10而已

![image-20221104100213290](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041002336.png)

![image-20221104100235391](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041002452.png)

真正的初始化Vector是调用的这个构造函数，创建了一个容量为initialCapacity（10）的数组。

![image-20221104100349222](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041003264.png)

# LinkedList双向链表底层机制

1. 实现了双向链表和双端队列

2. 元素可以是重复的，可以为null

3. 线程不安全的

![image-20221104101407124](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041014223.png)

底层维护了一个双向链表

维护了了两个属性  first和last 分别指向首节点和尾节点

每个节点中维护prev next item三个属性

LinkedList的添加和删除的效率高，没有扩容的时间开销

![image-20221104102118864](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041021018.png)

## add

执行完add("liXu")；

```java
LinkedList list=new LinkedList();
        list.add("liXu");
```

![image-20221104104133875](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041041974.png)

```java

* 1.调用无参构造器，啥也没干
         * //todo
         *      public LinkedList() {}
         *      此时size=0 first=last=null
         *2.add
         * //todo
         *      public boolean add(E e) {
         *         linkLast(e);
         *         return true;
         *     }
         *3.执行linkLast(e)方法
         * //todo
         *      void linkLast(E e) {
         *         final Node<E> l = last;
         *         final Node<E> newNode = new Node<>(l, e, null);
         *         last = newNode;
         *         if (l == null)
         *             first = newNode;
         *         else
         *             l.next = newNode;
         *         size++;
         *         modCount++;
         *     }
         *    分析此时last\first\newNode都指向为e的节点
         
```

将新节点加在链表最后
1. 先取出链表的尾节点，用临时变量l存放last

2. 创建一个新的节点
   - 前指针指向l
   - 后指针为空
3. 更新尾节点last为新加进来的节点，因为链表是尾插

4. 如果是第一次添加节点，那么l=last=null，所以首节点也指向newNode

5. 否则存放原来尾节点的临时变量l的后指针指向newNode，从而构成双向链表

## remove

```java
//删除节点remove()
 
list.remove();//默认删除第一个

* 1.调用的是removeFirst()
 * //todo
 *      public E remove() {
 *         return removeFirst();
 *     }
 * 2.调用removeFirst()
 * //todo
 *      public E removeFirst() {
 *         final Node<E> f = first;
 *         if (f == null)
 *             throw new NoSuchElementException();
 *         return unlinkFirst(f);
 *     }
 *     分析：取出头节点不为空才删除
 * 3.unlinkFirst(f)真正干活了
 * //todo
 *      private E unlinkFirst(Node<E> f) {
 *         // assert f == first && f != null;
 *         final E element = f.item;
 *         final Node<E> next = f.next;
 *         f.item = null;
 *         f.next = null; // help GC
 *         first = next;
 *         if (next == null)
 *             last = null;
 *         else
 *             next.prev = null;
 *         size--;
 *         modCount++;
 *         return element;
 *     }

```

## set

```java
//修改某个节点对象

list.set(0,"黎旭");

* 1.调用set()
 * //todo
 *      public E set(int index, E element) {
 *         checkElementIndex(index);//检查下标是否合法
 *         Node<E> x = node(index);//找到下标对应的节点，看源码可知index>=size/2会从尾节点开始找
 *         E oldVal = x.item;
 *         x.item = element;
 *         return oldVal;
 *     }
 * 2.
 *    分析首先检查下标 下标应当小于0且小于size
 *    //todo
 *          private void checkElementIndex(int index) {
 *         if (!isElementIndex(index))
 *             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 *         }
 *     //todo
 *          private boolean isElementIndex(int index) {
 *         return index >= 0 && index < size;
 *          }
 * 3.根据下标找到节点
 * //todo
 *      Node<E> node(int index) {
 *         // assert isElementIndex(index);
 *         if (index < (size >> 1)) {  //index<size/2会从头节点开始找
 *             Node<E> x = first;
 *             for (int i = 0; i < index; i++)
 *                 x = x.next;
 *             return x;
 *         } else {  //index>=size/2会从尾节点开始找
 *             Node<E> x = last;
 *             for (int i = size - 1; i > index; i--)
 *                 x = x.prev;
 *             return x;
 *         }
 *     }
 * 4.找到后更新此节点的val值
 * 5.并将旧值返回

```

# ArrayList与LinkedList的比较

![image-20221104112821284](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041128519.png)

# Set接口常用方法

1. 无序（即取出的顺序添加的顺序是不一致的，但是每次取出的顺序是一样的）底层是什么算法实现的这个功能呢？？？
2. 没有索引
3. 不允许重复元素
4. 可以使用增强for和迭代器遍历

![image-20221104113551889](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041135967.png)

# HashSet

怎么理解HashSet不能加入重复对象？？？

```java
HashSet的底层实现其实是HashMap
 //todo 调用的是HashMap的构造器
      public HashSet() {
         map = new HashMap<>();
     }
可以放入null值，但是只能存放一个空值，元素不能重复
```

## 案例一

结论：HashSet可以放入null值，不可以放重复元素

疑问：那么放入重复元素的时候，我们是用重复的新值覆盖掉原来的，还是直接舍弃新的重复元素呢？

```java
//案例1
HashSet set=new HashSet();
set.add(null);
set.add(null);
set.add("");
set.add("");
set.add('a');
set.add('a');
/**
 * [null, , a]
 * [null, , a]
 */
System.out.println(set);
System.out.println(set);
```

## 案例2

结论：加入的是两个对象，他们在HashSet眼里是不同的值

```java
//案例2
set=new HashSet();
set.add(new Person("黎旭"));//T
set.add(new Person("黎旭"));//T
System.out.println(set);
System.out.println(set);//[Person{name='黎旭'}, Person{name='黎旭'}]
```

## 案例3

疑问：为什么创建两个值相同的String对象，他们为什么又不能都添加进HashSet中呢？

```java
//案例3
//为什么这里添加第二次添加String不成功呢？
set=new HashSet();
set.add(new String("lx"));//T
set.add(new String("lx"));//F
System.out.println(set);//[lx]
```

# HashSet底层结构

![image-20221104170251683](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041702893.png)

![image-20221104171500678](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041715854.png)

```java
//分析案例：
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println(hashSet);//[java, php]
```

源码分析：

```java
1.调用HashMap的构造器(证实HashSet的底层实现就是HashMap)
// todo
	public HashSet() {
		map = new HashMap<>();
	}
```

```java
2.调用add方法
//todo
	public boolean add(E e) {//e:"java"
         return map.put(e, PRESENT)==null;//PRESENT用来占位
	}
//PRESENT是hashMap中的一个静态共享常量 private static final Object PRESENT = new Object();
  - (1)如果返回值为空说明添加成功
  - (2)返回值若为一个查询到的对象，说明添加失败

```

```java
3.执行put方法
    这里调用了hash(key)函数,目的是求出key的hash值
//todo
      public V put(K key, V value) {//k:"java" value:
         return putVal(hash(key), key, value, false, true);
     }
```

```java
4.进入hash函数  为非空对象计算出一个hash值，key与hash值对应
//hash值并不等价于hashCode
//算法 (h = key.hashCode()) ^ (h >>> 16)按位异或 无符号右移16位（避免冲突）
//todo
    static final int hash(Object key) {
    	int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
```

```java
5.putVal方法
// todo
@para hash 根据key值计算出来的hash值
@para key  需要存放的key值 key:"java"
@para value  等于HashMap中的共享静态常量 value=PRESENT 用来占位
@para onlyIfAbsent  false
@para evict  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;
         //transient Node<K,V>[] table;table是HashMap中的一个Node数组
         if ((tab = table) == null || (n = tab.length) == 0)
         //(1)第一次扩容，调用的是resize方法   第一次扩容为 16 并且有一个加载因子0.75*16=12
         //(2)当table已经添加了12个元素就会触发扩容
         //(3)最后返回值resize的返回值是一个大小为16的Node数组
         //(4)然后赋值给tab
         n = (tab = resize()).length;
         //(1)根据key计算出来的hash值去计算，此key应该存放在table表的哪个索引位置
         //(2)并把这个位置的Node对象赋值给 p(Node类型)
         //   (2.1) 如果p=null 说明这个索引位置还没有放过任何元素
         //   
         if ((p = tab[i = (n - 1) & hash]) == null)
         	tab[i] = newNode(hash, key, value, null);
         //这个else里的代码是存在冲突时的代码逻辑，稍后再分析
    	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) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
         		}
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
         }
         if (e != null) { // existing mapping for key
             V oldValue = e.value;
             if (!onlyIfAbsent || oldValue == null)
                e.value = value;
             afterNodeAccess(e);
             return oldValue;
         }
     }
    ++modCount;
    //判断此时table的数据量是不是大于扩容临界值
    //大于临界值了就需要扩容了，那么就调用resize()
    if (++size > threshold)
        resize();
    //此方法是HashMap中的空方法，用于给给子类实现
    afterNodeInsertion(evict);//evict:true传进来的时候是true
    return null;
}
```

第一次添加数据到HashMap中

![image-20221104195025839](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041950164.png)

第二次添加数据，根据hash值算出的索引得到的对象也为null

，说明没有冲突

![image-20221104195745548](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211041957826.png)

第三次添加数据“java"，发生冲突

![image-20221104200014131](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211042000418.png)

这一次e不再为空，这里很复杂（看源码）

![image-20221104200307418](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211042003687.png)

......前面的代码分析过程与没有发生冲突是一样的，这里主要看else{}里的代码逻辑
看看是如何处理冲突的

```java

//(1)根据key计算出来的hash值去计算，此key应该存放在table表的哪个索引位置
//(2)并把这个位置的Node对象赋值给 p(Node类型)
//   (2.1) 如果p=null 说明这个索引位置还没有放过任何元素
//   (2.2) 如果不为空，说明这个索引位置有对象了，返回这个对象给 p
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node<K,V> e; K k;
    //当前位置的对象 p 和准备新添加进来的对象的hash值相同
    //&&并且
    //  (1) 当前位置的对象 p 和准备新添加进来的对象是同一个对象 == 比较的是地址
    //  (2) 当前位置的对象 p 和准备新添加进来的对象的值是一样的 equals比较的是值
    //  先比较hash值，再比较是不是同一个对象，或者两个对象的值是否相等
    //  因此其实思考一下可以发现不同的对象的hash值可能也会相同
    //  而equals()常用于给程序员重写用来按不同的标准确定两个对象的等价关系
    //  这也是为什么之前我们两次执行hashset.add(new String("lixu"))最终只添加了一次，这是因为String重写了equals
    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 {
        //  如果table对应的索引位置已经是一个链表，就for循环遍历每个节点
        //  (1)与每个节点对象比较都不同，则将此节点加入到链表尾部,break;
        //  (2)如果hash值相同，再比较是不是同一个对象，或者两个对象的值是否相等，就不添加，break;
        //注意：
        //   - TREEIFY_THRESHOLD(8) 当前索引位置构成的链表长度已经达到8个就需要树化treeifyBin(tab, hash);
        //   - treeifyBin方法树化前会判断if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY
        //   MIN_TREEIFY_CAPACITY的值是(64) table数组的容量是否已经大于64了，大于64才会树化，否则就扩容resize();
        //   所以并不是满足 链表长度已经达到8个就立马树化（并不是第九个）
        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;
        }
    }
    if (e != null) { // existing mapping for 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;
}
```

![image-20221104204033474](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211042040997.png)

# HashSet的扩容机制

## 案例一：table的扩容机制

```java
//案例1：查看扩容机制
for(int i=0;i<100;++i){
    hashSet.add(i);
}

```

```java
//第一次添加数据扩容到 16
(1)调用resize方法，直接将预值 16 创建一个大小为16的table[Node]数组
```

```java
(2.1)当执行到添加第12个元素的时候会再次扩容，这是是在此处调用的resize()函数
//todo
    ++modCount;
	if (++size > threshold)
    	resize();
	afterNodeInsertion(evict);
	return null;
```

```java
(2.2)调用resize扩容，这次扩容是 将原来的table表空间进行2倍扩容
    - (newCap = oldCap << 1) newCap是新的空间大小
    - newThr = oldThr << 1;  同样的阈值也扩大为2倍
```

```java
(2.3)扩容之后底层创建了一个容量为之前两倍的newTab[Node]数组
并进行循环将之前的table数组中的数据赋值给新表
	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
```

```java
resize()源码
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
```

## 案例二：table树化

```
//案例2 链表化的table进化成树
/**
 * 首先我们知道只有两个对象的hash值相同时，即发生了冲突
 * 才会放在同一个索引下形成链表，所以我们自定义一个类并重写hashCode()
 */
```

开始table为空

![image-20221105101448981](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051014147.png)

加入了第一个元素，扩容到16

![image-20221105101528332](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051015474.png)

一直添加到第七个元素，所有元素都添加在了第一个索引位置并构成了一个链表

![](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051017093.png)

再添加第8个元素，table扩容到了32，而且扩容后所有元素重新根据hash值算出一个索引

![image-20221105101926897](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051019045.png)

添加第九个元素，再次触发扩容，此时table的大小已经是64

![image-20221105102045306](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051020462.png)

再添加第10个元素，链表会进化成树，可以看到已经是一颗红黑树的结构了

![image-20221105102257510](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051022662.png)

# LinkedHashSet

1. LinkedHashSet是HashSet的子类

2. LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表，正是这个特点使得插入的元素是有序的。

3. LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，所以元素的插入与取出顺序一致

4. LinkedHashSet不允许添加重复元素

![image-20221105112131458](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051121552.png)

![image-20221105105723561](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051057753.png)

```java

import java.util.LinkedHashSet;

public class LinkedHashSet_ {
    public static void main(String[] args) {
        LinkedHashSet linkedHashSet = new LinkedHashSet();
        linkedHashSet.add("我");
        linkedHashSet.add("是");
        linkedHashSet.add("大");
        linkedHashSet.add("帅哥");
        linkedHashSet.add("帅哥");
        linkedHashSet.add("帅哥");
        System.out.println(linkedHashSet);
        //[我, 是, 大, 帅哥]
    }
}

```

## add源码分析

维护了一个散列表（hash表）

before,after维护双向链表的指向关系

next维护散列表中某一索引下的单向链表指向关系

![image-20221105114438522](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051144687.png)

## remove源码分析

# Map接口

set接口也是键值对【k，v】:【e，present】只不过之前的set中的value值填充的是默认的present

![image-20221105153222684](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051532804.png)

![image-20221105153930131](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051539336.png)

![](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211051546227.png)

key-value存放在HashMap$Node这样的数据结构中

在putVal()方法中：

```java
 tab[i] = newNode(hash, key, value, null);
```

看源码可以确认，嗯！！没错就是存放在HashMap的Node中

![image-20221115175733919](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211151757156.png)

而为了方便程序员的遍历我们有entrySet()方法，它存放的是是引用，并没有真正的存放数据。创建了一个EntrySet集合，存放的元素是Entry类型，EntrySet<Entry<K,V>>

![image-20221115180456598](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211151804694.png)

输出验证entrySet方法的类型：是HashMap中的一个静态内部类EntrySet

```java
System.out.println("4  map.entrySet().getClass()  "+map.entrySet().getClass());
//class java.util.HashMap$EntrySet
```

![image-20221115180731965](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211151807100.png)

![image-20221115180850437](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211151808609.png)

而其存放的数据是Node类型

为什么EntrySet中定义时是Map.Entry，但是存放的却是HashMap$Node，因为接口的向上转型，Node是实现了Map.Entry接口的。所以相当于我在集合中放了一群Dog，但是告诉你我放的是动物。

> 向上转型（子类对象转为父类对象，隐藏子类的特有成员）是安全的，向下转型（父类的对象转为子类对象）是不安全的。自我发问：讲一讲为什么向下转型不安全？

```java
for (Object e : map.entrySet()) {
            System.out.println("5 e="+e.getClass());
        }
//java.util.HashMap$Node
```

![image-20221115181656485](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211151816656.png)

在Map.Entry接口中提供了getKey()与getValue()方法，方便我们获取键值

![image-20221117205444955](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211172054058.png)

## entrySet在什么时候被赋值的？

1. idea在debug时偷偷调用toString方法，在HashMap追源码时产生的疑惑
2. HashMap的entrySet()和keySet()方法真的创建了一个存满数据的set对象吗？
3. 内部类：EntrySet类没有构造器，那它是怎么初始化的呢？
4. 为什么集合框架中一定要利用好迭代器iterator()来获取入口？
5. entrySet().size()获取的值是该set的实际大小吗？

- entrySet()和keySet()都是懒汉式，调用方法，new对象的时候并没有对其进行赋值,并且其size()方法也是一个虚假的size
- 而是在使用hashMap.entrySet().toString()、hashMap.entrySet(). toArray() 等方法的时候才调用iterator()来获取迭代器
- EntrySet类和KeySet类也都没有构造器能进行初始化
- 不得不说HashMap的设计十分精巧，entrySet()表面上获取了一个set对象，实际上这个set对象是空的，几乎所有的方法都是先直接获取迭代器入口，节约内存的同时性能大幅提升
  ————————————————
  版权声明：本文为CSDN博主「ZJH'blog」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  原文链接：https://blog.csdn.net/m0_56079407/article/details/123624985

## Map接口遍历方法

```java
package map_;

import java.util.*;
import java.util.Map.Entry;

public class MapFor {
    public static void main(String[] args) {
//        赋初值
        Map hashMap=new HashMap();
        hashMap.put("1","a");
        hashMap.put("2","b");
        hashMap.put("3","c");
        hashMap.put("4","d");
        hashMap.put("5","e");
//        通过EntrySet遍历
        System.out.println("---------通过EntrySet遍历----------");
        Set entrySet = hashMap.entrySet();
        System.out.println(entrySet.getClass());
        for (Object entry:entrySet) {
            Map.Entry m= (Entry) entry;
            System.out.println(m.getKey()+" - "+m.getValue());
        }
//        通过迭代器遍历
        System.out.println("---------通过EntrySet迭代器遍历----------");
        Iterator iterator2 = entrySet.iterator();
        while (iterator2.hasNext()) {
            Map.Entry next =  (Map.Entry) iterator2.next();
            System.out.println(next.getKey()+" - "+next.getValue() );
        }

//        通过KeySet遍历
        System.out.println("---------通过KeySet遍历----------");

Set keySet = hashMap.keySet();
        for (Object key:keySet) {
            System.out.println(key+" - "+hashMap.get(key));
        }
//        通过KeySet迭代器遍历
        System.out.println("---------通过KeySet迭代器遍历----------");
        Iterator iterator = keySet.iterator();
        while (iterator.hasNext()) {
            Object key =  iterator.next();
            System.out.println(key+" - "+hashMap.get(key));
        }
//        通过values遍历
        System.out.println("---------通过values遍历----------");

Collection values = hashMap.values();
        for (Object value:values) {
            System.out.println(value);
        }
//        通过迭代器遍历
        System.out.println("---------通过values迭代器遍历----------");
        Iterator iterator1 = values.iterator();
        while (iterator1.hasNext()) {
            Object value =  iterator1.next();
            System.out.println(value);
        }
//
        System.out.println("---------Lambda遍历-----------");
        hashMap.forEach((k,v)-> System.out.println(k+" - "+v));
    }
}

```

# Map接口小结

![image-20221118101753039](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211181017189.png)

注意添加相同的key，则会覆盖原来的key-value，但是key不会替换，这从HashSet的分析中可得知，而value会被替换

在HashMap源码的putVal()方法中，如果出现hash冲突，我们会将原来的旧值取出，用新值覆盖，并返回旧值。

![image-20221118102953659](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211181029745.png)

# HashMap底层机制

![image-20221118103819928](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211181038144.png)

## 触发扩容的链表长度临界值是8还是9

可以看到我们的链表长度以及是8了但是并未触发扩容

![image-20221118131356049](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211181313245.png)

再添加一个元素

![image-20221118131616478](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211181316630.png)

![image-20221118131723544](https://starry-lixu.oss-cn-hangzhou.aliyuncs.com/202211181317706.png)

因此当一条链表的长度等于8时，如果再往此链表添加数据，第9个元素才会触发树化

starry陆离/Java集合源码

简介

发行版

贡献者

近期动态

starry陆离/Java集合源码 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

starry陆离/Java集合源码