实现原理
Iterator 的实现
- ArrayList 有内部类 Itr，
- 三变量：cursor、lastRet、expectedModCount，
- cursor 表示下个元素索，lastRet 表示上个元素的索引
- 初始化,astRet 比 cursor 少一
- hasNext() 判断 cursor 和 lastRet 是否相等。
- next() 返回 cursor 索引元素，修改 cursor、lastRet (+1),modCount != expectedModCount,抛出异常 ，实现快速失败(fail-fast)，
ArrayList 实现
2.26介绍一下ArrayList的数据结构?
- 底层是数组，第一次插入元素时创建大小为10的数组，超出限制时会增加50%的容量,并且数据以System.arraycopy()复制到新的数组。
- 按数组下标访问元素的性能很高。直接在数组末尾加入元素的性能高，按下标插入、删除元素，则要用System.arraycopy()来移动部分受影响的元素，性能差。
HashMap实现
HashMap put的过程 xx
- 1.首次扩容: (判断数组是否为空),数组为空进行扩容(resize) ;
- 2.计算索引:hash算法计算键值对在数组中的索引;
- 3.插入数据:
- 当前位置元素为空，则直接插入数据;
- 当前位置元素非空，且key已存在，则直接覆盖其value;
- 当前位置元素非空，且key不存在，则将数据链到链表末端;
- 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中;
- 4.再次扩容 (如果数组中元素个数(size）)超过阀值(threshold,现有容量*加载因子),再次扩容。
HashMap xxx
- 键值对存储的容器
- 无序，key不重复；可空键，值；
- 非线性安全
- 初始长度是16,加载因子0.75
HashMap原理 xxx
- 底层数据结构：数组+(链表、红黑树)
- 内部实现数组是Node[]数组
- put的过程
- get方法就是计算出要获取元素的hash值，去对应位置获取即可
- 扩容机制 长度变为原来的两倍,重新插入到新数组。1.7(重新计算hash) 1.8((原)hash和(原)长度求与,第一位为1=索引+长度，否则原索引)
- HashMap大小是2的幂次方？效率高+空间分布均匀 (x)
HashMap原理 *****
- 底层是数组+(链表、红黑树)实现，数组每一个元素是链表结构，链表中的每个元素是Entry对象，存储真正k，v。
put方法实现
- ( 首次扩容: ,(判断数组是否为空) 数组为空进行扩容(resize) ;)
- 1(计算索引: ) (hash方法)计算key的hash值，10进制数字，数字和数组长度-1取模获取数组下标，根据数组下标找到对应单向链表
- 2 把链表中的每个元素和插入的key进行equals比较，相等则更新value值，不相等put到链表末端，
- 3 put过程中，键值对个数超过容量*负载因子，数组扩容2倍
- 4 若链表长度达到默认预值(8)，则将链表转换成红黑树，
- (找不到对应key的hash值，直接插入数据)
get方法
- 计算key的hash值，找到对应数组下标，遍历对应下标的链表元素进行equals比较，key相等取出元素
最核心实现
- 利用hash计算下标位置，使用equals比较解决hash冲突
为什么使用红黑树
LinkedHasMap实现
说一说你对LinkedHashMap的理解
- 使用双向链表维护元素插入顺序， 与迭代顺序一致。
- 避免对key-value排序，又避免使用TreeMap的成本。
- 需要维护元素的插入顺序，性能略低于HashMap的性能。
- 迭代访问全部元素时将有较好的性能。
2.20请介绍LinkedHashMap的底层原理
- 继承于HashMap，
- 通过维护一条双向链表,解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。
- 很多方法直接继承自HashMap，仅为维护双向链表重写了部分方法。
2.21请介绍TreeMap的底层原理
- 红黑树实现。根据键的自然顺序或者提供的Comparator排序
- root是根节点。Entry类型节点根据根据Key排序，包含的内容是value。key比较大小是根据comparator进行判断的。size是节点个数。
- TreeMap的基本操作 时间复杂度是log(N)。
2.27谈谈CopyOnWriteArrayList的原理
- 线程安全且读操作无锁的ArrayList。
- 在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。。
- 优点:读操作性能很高，迭代器遍历不会抛出ConcurrentModificationException异常了。
- 缺点:一是内存占用高，写操作复制原容器 ，二是无法保证实时性，写操作执行时读取的老数据
HashSet实现
2.29说一说HashSet的底层结构
- 基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75的HashMap。它封装了一个HashMap 对象来存储所有的集合元素，所有放入 HashSet中的集合元素实际上由HashMap 的 key来保存，而HashMap 的 value 则存储了一个PRESENT，它是一个静态的Object对象。
面试题
集合是什么
- 存放对象的容器
- 存放的是引用
- 存放不同类型，不限数量的数据。
1.7,1.8 HashMap的区别?
- 1.7 数组+链表实现，同一hash值在一个链表，hash值相等的较多,查找效率低.O(n)
- 1.8，长度超过8，链表转为红黑树,O(logn)
拉链法(链地址法)：
- 数组+链表实现，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
扩容
- 扩容:重新分配更大的内存,数据复制到新内存。
- 加载因子: 长度超过(容量*加载因子)扩容
- 初始容量 ，ArrayList 10; HashMap,16
- 加载因子，ArrayList 无(1)； HashMap,0.75
- 扩容增量： ArrayList为1.5 ,HashMap为2，
HashMap的扩容机制
- 初始容量为16，容量以2的次方扩充 (1 更大的数组，2 位运算)
- 是否需要扩充通过负载因子判断，默认为0.75
- 解决碰撞，链表长度到达阈值时(7或8)，转换成红黑树。缩小到另一个阈值时(6),转换回单向链表。
- 数组到达阈值（64)才会转换红黑树。
HashMap1.8 优化，扩容后不需要重新计算hash值
- 使用 元素原hash码，与原始长度（例如8）进行 &(按位与) 运算，
- 第一位为0，放在原索引 的位置上
- 第一位不为0，放在 【原索引+原长度】
HashMap中 循环链表 的产生 ?
- 1.8之前采用头插法，多线程环境下，同时进行put操作，同时进行扩容时，会出现链表环，导致死循环，新加入的冲突元素将会插到原有链表的头部。
- 1.8采用尾插法解决头插法造成的死循环，也会出现死循环(链表转换为树，对树进行操作时)
解决哈希冲突，碰撞
- 链表长度到达阈值时(7或8)，转换成红黑树。缩小到另一个阈值时(6),转换回单向链表。
HashMap和 ConcurrentHashMap 的区别
- hashmap 线程不安全， 多线程下，put会形成环导致死循环
- CoucurrentHashMap 线程安全，1.7分段锁,减少锁的粒度。1.8 CAS+Synchronized
ConcurrentHashMap
ConcurrentHashMap 实现原理
- 底层是数组+链表+红黑树
- 1.7分段锁,减少锁的粒度。1.8 CAS+Synchronized
ConcurrentHashMap 1.8为何又放弃分段锁
- 多个分段锁浪费内存空间，竞争同一个锁的概率小，反而造成效率低。
2.22 Map和Set有什么区别?
- Set代表无序的，元素不可重复的集合;
- Map代表具有映射关系(key-value)的集合，其所有的key是一个Set集合，即key无序且不能重复。
2.23 List和Set有什么区别?
- Set代表无序的，元素不可重复的集合;
- List代表有序的，元素可以重复的集合。
2.24 ArrayList和LinkedList有什么区别
- 1.ArrayList基于数组，LinkedList基于双向链表;
- 2.对于随机访问，ArrayList要优于LinkedList,ArrayList根据下标以O(1)时间复杂度对元素进行随机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素的时间复杂度是O(N);
- 3.对于插入和删除操作，LinkedList要优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引;
- 4.LinkedList比ArrayList更占内存，因为 LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
2.25有哪些线程安全的List?
- 1.Vector 效率低
- 2.Collections.SynchronizedList，方法带有同步锁， 效率低
- 3.CopyOnWriteArrayList 复制数组，对新数组读写
2.28说一说TreeSet和HashSet的区别
- 都是不能重复的，线程不安全
- HashSet 可空，不保证排序，哈希表失效
- TreeSet 不可空，自然排序，定制排序。红黑树实现
Java集合面试题（总结最全面的面试题）_普通网友的博客-CSDN博客_java集合类面试题
50道Java集合经典面试题（收藏版）_13284304的技术博客_51CTO博客
全网最全的Java岗集合面试题（含答案） - 哔哩哔哩
java集合面试题_jit-xly的博客-CSDN博客_java集合面试
java集合面试题 - kylinwms - 博客园
重点
50道Java集合经典面试题（收藏版）_13284304的技术博客_51CTO博客