# Java集合源码
**Repository Path**: starry_lixu/java-collection-source-code
## Basic Information
- **Project Name**: Java集合源码
- **Description**: Java集合类源码学习代码笔记
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: https://ahoy-starry.blog.csdn.net
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-11-04
- **Last Updated**: 2023-11-05
## Categories & Tags
**Categories**: Uncategorized
**Tags**: Java
## README
# 为什么要有集合
```java
/**
* 数组的不足
* 1.长度一旦确定就无法变化（不能动态扩容）
* 2.保存的数据类型必须相同
* 3.增加和删除麻烦
*/
```
# 集合的遍历
可以看到Collection接口继承了Iterable接口（接口与接口之间的关系是继承）
在Iterable接口中有一个Iterator类型的iterator()方法，所以继承了Iterable接口，或者说继承了Collection的所有子类都会实现这个方法
在Iterator接口中有两个重要的方法hasNext()和next()；
> hasNext()：如果迭代有更多的元素，则返回true。(换句话说，如果next将返回一个元素而不是抛出异常，则返回true。)如果迭代有更多的元素，返回:true
>
> next()：返回迭代中的下一个元素。如果迭代中没有更多的元素，则抛出NoSuchElementException异常
```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
> 学习方法：结合源码去记忆继承与实现关系
# collection接口的常用方法
# 迭代器Iterator
# 增强for循环
值得注意的是我们的增强for循环底层也是调用了iterator()，返回了一个迭代器（因为我这里定义的是ArrayList实现类，所以debug会来到ArrayList类的iterator()方法中，再次证实继承了Collection的所有子类都会实现这个方法）
# List接口的方法
# 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(用来进行线程互斥操作)
```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()
*/
```
第一次加入数据触发第一次扩容：
扩容的关键代码：
> 增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量。minCapacity—所需的最小容量
每次都先获取原来的数组容量，然后将其oldCapacity + (oldCapacity >> 1);也就是乘1.5倍（因为是无符号右移相当于除2）
每次扩容都会执行这个操作，当然除第一次扩容时，数组为空=0，所以我们代码逻辑执行这一行逻辑代码
```java
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
```
将所需的最小容量，其实也就是10赋值给newCapacity，作为第一次扩容的容量大小。
### 有参构造
```java
/*有参构造
1.创建的不再是一个空，而是一个指定大小的elementData数组={指定大小}
2.其后操作相同*/
ArrayList arrayList1=new ArrayList(8);
for (int i=0;i<=8;++i){
arrayList1.add(i);
}
```
> 构造具有指定初始容量的空列表。如果指定的初始容量为负数，则抛出:IllegalArgumentException
https://edrawcloudpubliccn.oss-cn-shenzhen.aliyuncs.com/viewer/self/28828983/share/2022-11-14/1668418152/main.svg
> 注意关闭IDEA的debugger的简略输出模式并且不隐藏空值
>
> 
# Vector底层结构和源码分析
Vector是线程安全的
### 比较Vector和ArrayList
```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而已
真正的初始化Vector是调用的这个构造函数，创建了一个容量为initialCapacity（10）的数组。
# LinkedList双向链表底层机制
1. 实现了双向链表和双端队列
2. 元素可以是重复的，可以为null
3. 线程不安全的
底层维护了一个双向链表
维护了了两个属性 first和last 分别指向首节点和尾节点
每个节点中维护prev next item三个属性
LinkedList的添加和删除的效率高，没有扩容的时间开销
## add
执行完add("liXu")；
```java
LinkedList list=new LinkedList();
list.add("liXu");
```
```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 l = last;
* final Node 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 f = first;
* if (f == null)
* throw new NoSuchElementException();
* return unlinkFirst(f);
* }
* 分析：取出头节点不为空才删除
* 3.unlinkFirst(f)真正干活了
* //todo
* private E unlinkFirst(Node f) {
* // assert f == first && f != null;
* final E element = f.item;
* final Node 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 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 node(int index) {
* // assert isElementIndex(index);
* if (index < (size >> 1)) { //index x = first;
* for (int i = 0; i < index; i++)
* x = x.next;
* return x;
* } else { //index>=size/2会从尾节点开始找
* Node x = last;
* for (int i = size - 1; i > index; i--)
* x = x.prev;
* return x;
* }
* }
* 4.找到后更新此节点的val值
* 5.并将旧值返回
```
# ArrayList与LinkedList的比较
# Set接口常用方法
1. 无序（即取出的顺序添加的顺序是不一致的，但是每次取出的顺序是一样的）底层是什么算法实现的这个功能呢？？？
2. 没有索引
3. 不允许重复元素
4. 可以使用增强for和迭代器遍历
# 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底层结构
```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[] tab; Node p; int n, i;
//transient Node[] 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 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)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中
第二次添加数据，根据hash值算出的索引得到的对象也为null
，说明没有冲突
第三次添加数据“java"，发生冲突
这一次e不再为空，这里很复杂（看源码）
......前面的代码分析过程与没有发生冲突是一样的，这里主要看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 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)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;
}
```
# 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[] newTab = (Node[])new Node[newCap];
```
```java
resize()源码
final Node[] resize() {
Node[] 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[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node 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)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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为空
加入了第一个元素，扩容到16
一直添加到第七个元素，所有元素都添加在了第一个索引位置并构成了一个链表
再添加第8个元素，table扩容到了32，而且扩容后所有元素重新根据hash值算出一个索引
添加第九个元素，再次触发扩容，此时table的大小已经是64
再添加第10个元素，链表会进化成树，可以看到已经是一颗红黑树的结构了
# LinkedHashSet
1. LinkedHashSet是HashSet的子类
2. LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表，正是这个特点使得插入的元素是有序的。
3. LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，所以元素的插入与取出顺序一致
4. LinkedHashSet不允许添加重复元素
```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维护散列表中某一索引下的单向链表指向关系
## remove源码分析
# Map接口
set接口也是键值对【k，v】:【e，present】只不过之前的set中的value值填充的是默认的present
key-value存放在HashMap$Node这样的数据结构中
在putVal()方法中：
```java
tab[i] = newNode(hash, key, value, null);
```
看源码可以确认，嗯！！没错就是存放在HashMap的Node中
而为了方便程序员的遍历我们有entrySet()方法，它存放的是是引用，并没有真正的存放数据。创建了一个EntrySet集合，存放的元素是Entry类型，EntrySet>
输出验证entrySet方法的类型：是HashMap中的一个静态内部类EntrySet
```java
System.out.println("4 map.entrySet().getClass() "+map.entrySet().getClass());
//class java.util.HashMap$EntrySet
```
而其存放的数据是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
```
在Map.Entry接口中提供了getKey()与getValue()方法，方便我们获取键值
## 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接口小结
注意添加相同的key，则会覆盖原来的key-value，但是key不会替换，这从HashSet的分析中可得知，而value会被替换
在HashMap源码的putVal()方法中，如果出现hash冲突，我们会将原来的旧值取出，用新值覆盖，并返回旧值。
# HashMap底层机制
## 触发扩容的链表长度临界值是8还是9
可以看到我们的链表长度以及是8了但是并未触发扩容
再添加一个元素
因此当一条链表的长度等于8时，如果再往此链表添加数据，第9个元素才会触发树化