集合接口
Map接口 定义解释

1. 为什么要有集合框架？

早在 Java 2 中之前，Java 就提供了特设类。比如：Dictionary, Vector, Stack, 和 Properties 这些类用来存储和操作对象组。
虽然这些类都非常有用，但是它们缺少一个核心的，统一的主题。由于这个原因，使用 Vector 类的方式和使用 Properties 类的方式有着很大不同。
集合框架被设计成要满足以下几个目标。

1. 该框架必须是高性能的。基本集合（动态数组，链表，树，哈希表）的实现也必须是高效的。
   
2. 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性。
   
3. 对一个集合的扩展和适应必须是简单的。
   

为此，整个集合框架就围绕一组标准接口而设计。你可以直接使用这些接口的标准实现，诸如： LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通过这些接口实现自己的集合。

2. 集合框架有哪些东西？

主要是Collection和Map接口，和其子类 组成了完整的集合框架。

文章图片


文章图片


文章图片


文章图片

Java集合框架为程序员提供了预先包装的数据结构和算法来操纵他们。
集合是一个对象，可容纳其他对象的引用。集合接口声明对每一种类型的集合可以执行的操作。
集合框架的类和接口均在java.util包中。
任何对象加入集合类后，自动转变为Object类型，所以在取出的时候，需要进行强制类型转换。
如何使用
想怎么用就怎么用，不过要根据实际情况，选择合适的集合类。
源码原理
源码只能去各个实现类去看
总结
Collection 和 Map 是Java集合框架的根接口。 Set, List, Queue接口是Collection的子接口。 HashMap, Hashtable,SortedMap等都是Map接口的实现。

1. Java集合分为 Set, List, Queue, Map四种体系。
   
2. Set : 无序，不可重复的集合；
   
3. List： 有序，可以重复的集合；
   
4. Queue： 队列集合；
   
5. Map： 有映射关系的集合。
   
6. Collections和Arrays是2个工具类用于查找和排序等
   

所到底集合框架 考验的就是 数据结构基础。如果不熟悉 数组，链表，队列，栈，树，查找，排序等 就很难 看懂源码。
List接口
定义解释

1. 什么是list接口？

List接口是Collection的子类。主要有以下方法：

文章图片

2. list接口有哪些特点？

有序-数据存储的顺序就是你添加的顺序
可重复
每个元素都有其对应的顺序索引
可以添加Null元素

3. list接口有哪些实现类？

有2个抽象子类：AbstractList和AbstractSequentialList。实现子类有：ArrayList LinkedList Stack Vector CopyOnWriteArrayList。

4. list接口常用的有哪些？

ArrayList
LinkedList
Vector
Stack
CopyOnWriteArrayList
如何使用

public static void println(T msg) { System.out.println("MainCollection=" + msg.toString()); }public static void main(String[] args) { ArrayList> arrayList=new ArrayList>(); arrayList.add("我"); arrayList.add("是"); arrayList.add("白"); arrayList.add("嫖"); println(arrayList.toString()); }

使用非常的简单，基本没什么难度。不会的看下文档就知道他们那些方法是什么意思了。
源码原理

1. ArrayList

使用数组实现数据的存储

文章图片

第一个构造函数

文章图片

第二个构造函数，无参数，默认数组大小其实是零

文章图片

第三个 传入集合参数，则把数据拷贝过来

文章图片

最普通的添加元素方法put(Object obj):

文章图片

首先检测当前容量能否再加1，不能则扩容 。

文章图片

如果当前的数组大小为0，传入进来的值小于默认的10，则取 10.

文章图片

增加容量也很简单
首先获取一个新的容量值：原来的+原来的/2. 可以说是1.5倍。
然后判断新容量值是否合法。如果超过最大值，则取最大值

文章图片

clear方法直接把大小至为0，同时会把每个元素也置空，防止内存泄漏。

文章图片

add(int index,E element)方法也很简单，首先判断index的范围是否合法。 然后保证正确的容量。然后用System.arraycopy的方法，把目标的位置给空出来 放新元素。

文章图片

remove方法有2个参数为index和object。先看index

文章图片

很简单，先检测参数的合法性，然后获取目标位置的元素，最后返回出去。还是利用System.arraycopy方法把目标位置给填了，再把最后一个重复的元素置空。object一样很简单就不看了。
总的来说ArrayList的源码还是很简单的，从源码来看 数据量很大的时候就不要使用了。因为它不会缩小容量。如果知道数据大概的大小，建议传入准确值，提高效率。

2. LinkedList

底层使用链表实现：

文章图片

是双向链表 ：

文章图片

添加元素：

文章图片

很简单，就链表的尾部插入，注意是双向。

3. Vector

这个就是 AarrayList的 同步版本，但是由于它是直接在方法上增加synchronized关键字去同步所以效率不高，目前已经很少使用

3. Stack

是Vector的子类，不过它可以作为数据结构栈使用，就是可以入栈和出栈。但是效率也不高。
总结

1. 查找比较多，添加删除少 时使用ArrayList
2. 有重复元素添加时使用List
3. ArrayList底层是通过数组实现,LinkedList是双向链表实现
4. 要注意线程同步问题

Set接口 定义解释
Set 接口实例存储的是无序的，不重复的数据
Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变
接口方法有：

文章图片

主要实现类：HashSet,TreeSet，LinkedHashSet，EnumSet
如何使用

public static void main(String[] args) { HashSet> hashSet=new HashSet<>(); hashSet.add("我"); hashSet.add("爱"); hashSet.add("太"); hashSet.add("阳"); println(hashSet.toString()); }

使用 大同小异。这里的运行结果是：我爱阳太。和加入的顺序是不同的。但是其实顺序也是固定的。这个和其内部的数据结构有关。
源码原理

1. HashSet

这个基本是个皮包类，里面是通过 关联了一个HashMap实现所有的Set接口功能
HashSet按照Hash算法存储集合中的元素。 HashSet有以下特点：
不能保证元素的排列顺序 HashSet不是同步的，多个线程访问时，如果有多线程同时修改，需要代码来保证同步。 集合元素值可以是null 向HashSet 添加元素时，会调用该对象的 hashCode()得到该对象的hashCode值，根据hashCode值决定 HashSet的存储位置。 判断两个元素相等的标准是 通过 equals（）方法比较相等，并且hashCode()返回的值也相等。

2. TreeSet

这个基本也是个皮包类，里面是通过 关联了一个TreeMap实现所有的Set接口功能
SortedSet 是 Set的子接口。 TreeSet是 SortedSet接口的实现类，保证集合元素处于排序状态。
TreeSet支持两种排序规则： 自然排序和定制排序。 TreeSet会调用集合元素的 compareTo()方法比较元素的大小关系，然后按照升序排列， 这种为自然排序。 定制排序需要创建TreeSet时，提供一个 Comparator对象， 实现排序逻辑。

3. LinkedHashSet

LinkedHashSet是 HashSet的子类，LinkedHashSet根据元素的hashCode值决定元素的存储位置，同时使用链表维护元素的次序。使元素看起来是按照插入顺序保存的。 由于要维护插入顺序，性能略低于HashSet性能，但迭代访问时有很好的性能。

3. EnumSet

EnumSet是专门给枚举类设计的集合类。 所有元素必须是枚举类型的枚举值
总结

1. Set底层都是通过HashMap实现。
2. 不能存储重复元素
3. 无序，因为是用的哈希表。
4. 我们可以利用特点 来过滤相同的元素。

queue接口 定义
Queue用于模拟队列数据结构。 通常指先进先出（FIFO）的容器。 新元素插入到队尾， 获取元素会返回队头的元素， 通常，不允许随机访问队列中的元素。
Queue 是继承于 Collection接口。
Queue接口中定义了如下的方法：
add() ：指定元素加入到队列的尾部
element(): 获取头部元素，但不删除该元素
offer（）：指定元素加入到队列尾部，如果发现队列已满无法添加的话，会直接返回false。
peek(): 获取头部元素， 但是不删除， 队列为空，返回 null
poll(): 获取头部元素，并删除该元素， 队列为空，返回Null
remove（）：获取头部元素，并删除该元素， 队列为空时抛出异常NoSuchElementException
主要的实现类：ArrayBlockQueue,LinkedBlockingQueue,DelayQueue，PriorityQueue等。
Deque集合
Deque接口 是 Queue 接口的子接口。 代表双端队列。
Deque 还可当做栈来使用， 包含了 pop() 出栈 和 push（）入栈两个方法。 主要包括以下方法：
addFirst() ：插入开头
addLast(): 插入末尾
descendingIterator(): 返回对应的迭代器，以逆向顺序来迭代队列
getFirst(): 获取不删除第一个元素
getLast(): 获取不删除最后一个元素
offerFirst(): 插入开头
offerLast(): 插入末尾
peekFirst():获取不删除第一个元素
peekLast(): 获取不删除最后一个元素
pollFirst(): 获取，删除第一个
pollLast(): 获取， 删除最后一个
removeFirst()： 获取， 删除一个
removeFirstOccurrence(): 删除第一次出现的元素
removeLast（）:获取，删除最后一个
removeLastOccurrence(): 删除最后一个出现的元素
ArrayDeque 是 Deque的实现类。是基于数组实现的双端队列。 采用动态，可重分配的Object[]数组来存储元素。 可以指定Object[]数组长度，默认为16.
主要的实现类有：ArrayDeque,LinkedBlockingDeque，LinkedList。
当然后还有阻塞队列。
整个Queue接口的结构如下：

文章图片

使用
和使用 列表类似
比如使用PriorityQueue：

PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.offer(4); priorityQueue.offer(-2); priorityQueue.offer(8); priorityQueue.offer(6); System.out.println(priorityQueue); System.out.println(priorityQueue.poll());

PriorityQueue 不是绝对标准的队列实现。 PriorityQueue 保存元素的顺序不是按照加入队列的顺序， 而是按照元素的大小重新排序。
上面输出并没有完全按照大小排序输出，这只是受到toString()方法返回值的影响， 实际上多次 poll(),元素是按照从小到大移出队列。 PriorityQueue 不允许插入 null元素，需要对元素进行排序， 排序有 自然排序 和 定制排序 两种， 和 TreeSet 基本一致。
比如使用ArrayDeque ：

ArrayDeque> stack = new ArrayDeque<>(); stack.push("A"); stack.push("B"); stack.push("C"); System.out.println(stack); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack);

推荐使用 ArrayDeque代替 Stack，Stack是古老的集合， 性能较差。
ArrayDeque 也可以当做队列使用， 先进先出。

ArrayDeque queue = new ArrayDeque(); queue.offer("A"); queue.offer("B"); queue.offer("C"); System.out.println(queue); System.out.println(queue.peek()); System.out.println(queue); System.out.println(queue.poll()); System.out.println(queue);

LinkedList 是 List接口的实现类，可以根据索引随机访问， LinkedList还是实现类 Deque的接口。 可以当做双端队列，即可以当 栈， 也可以当 队列
原理
整体和上面的Arrylist差不多
总结

1. 需要排队的时候可以使用
2. 有阻塞队列和非阻塞队列
3. 生产者和消费者

Map接口 定义
Map集合用于保存映射关系的数据，Map集合中保存了两组值，一组是 key， 一组是 value。 Map的key不能重复。 key和value之间存在单向一对一的关系， 通过key，能找到唯一的，确定的value。
map接口中定义的方法：

文章图片

使用

public static void main(String[] args) { HashMap, String> hashMap=new HashMap<>(); hashMap.put("a", "我"); hashMap.put("b", "爱"); hashMap.put("c", "太"); hashMap.put("d", "阳"); println(hashMap.toString()); Set> entrySet = hashMap.entrySet(); Iterator> iterator = entrySet.iterator(); while (iterator.hasNext()) { Entry, String> entry=iterator.next(); println(entry.getKey()+"---"+entry.getValue()); } }

运行结果：

文章图片

使用也是非常简单的，就是 put 和get。关键还是源码。Key的存储是根据hashcode来的。
原理
构造函数

文章图片

默认的话。构造因子就是0.75，意思就是 数组的容量是100，如果当前已有75个数据时就要 扩容数组了。初始默认的数组容量是16.最大容量是2的30次方。10亿。 整个结构类似：

文章图片

【Java体系|Java进阶08-集合框架】怎么实现存储数据？
其实就是看Put方法的实现：

文章图片

计算Hash值。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; 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 { 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 = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); return null; }

这是整个Put方法。我来解释下

1. 首先判断hash表是否为空，是则resize()扩容，这个方法也比较复杂
2. 根据i = (n - 1) & hash 获取下标如果没有元素则把新的节点插入完事
3. 如果有元素了，那就是去解决冲突问题了。首先判断key是否相等，如果相等则直接替换完事
4. 如果当前节点是树节点 就是已经是红黑树结构则插入树对应的位置。
5. 如果是还是链表节点则插入末尾
6. 插入后如果节点数大于等于了7 则转化为树
7. 最后如果元素数量达到了临界值，则调用resize()扩容

怎么扩容？
扩容就是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; }

这个方法也很长，需要解释下：

1. 判断原来的表如果大于0，并且已经大于最大值2的30次方，10亿，MAXIMUM_CAPACITY，则把容量赋值为2147483647 2的31次方，20亿。
2. 否则左移一位，翻倍扩容。
3. 重新复制临界值大小
4. 接着就要把原表的数据 拷贝过来。
5. 循环遍历旧表，如果元素不为空，则把原表元素置空。
6. 如果此节点没有下一个节点那好办用 e.hash & (newCap - 1) 获取新表的下标，把元素放入就好了。
7. 如果是红黑树节点了，则分割红黑树节点到新表
8. 则分解 链表节点到新表
   总的来说还是很复杂的。

怎么解决哈希冲突？
使用的是 链地址法。通过一个链表维护。如果节点数量超过7个则转化为红黑树 提高性能。转化过程也是相当复杂，涉及了红黑的所有知识。旋转，平衡等
get的实现？
get方法相对 remove方法就简单点了。

final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

1. 首先获取传入进来的key的hash值。
2. 判断当前的表 不为空，有元素，且根据hash获取的第一个节点不为空
3. 如果此节点的hash值和传入的是一样的。则返回此节点
4. 如果不是，则判断此节点是属于链表，还是红黑树。
5. 则在链表中查询返回，后者是红黑树中查询返回。
6. 红黑树是根据hash大小来排序的。

怎么遍历？
使用迭代器模式进行遍历
最终实现：HashIterator类中

文章图片

总结

1. 哈希表
2. 红黑树
3. 单链表
4. 代码实现的还是有难度，暂时只能掌握思想。

推荐阅读

• 

  大货车离合器太重有几个原因
• 

  安卓开发平台有哪些，android发布平台有哪些
• 

  白鹭表达了作者怎样的思想感情 《白鹭》课文原文
• 

  excel折叠行怎么设置 word怎么删掉空白页，word最后一页死活删不掉
• 

  辣木籽的功效是真是假 辣木籽的功效是真是假?
• 

  陌耳是正规平台吗
• 

  php实现插入二维数组数据到数据库|php实现插入二维数组数据到数据库 原生sql语句
• 

  苏打水能当正常水喝吗
• 

  睡莲可以种在室内吗
• 

  抖音啊呀呀coco是什么歌？
• 

  网络连接错误代码104怎么解决 阿里斯顿错误代码104
• 

  重温《灵异第六感》——愿你走出孤独仍少年
• 

  g4900为什么贵,g4900有核显吗
• 

  阳台一般什么颜色好看，阳台做什么颜色好看呢
• 

  深度技术Win7系统假死
• 

  茄子菌核病如何防治 茄子菌核病的防治方法
• 

  率土之滨铁城雄兵赛季新机制介绍 全新征服赛季改动一览
• 

  婚纱是属于礼服吗？
• 

  mysql定时执行语句 mysql定时维修
• 

  佳能ef70-200mm镜头 佳能ef70-200mm

• 源码阅读|HashMap原理及常见考点
• python|100天精通Python（基础篇）——第29天（标准库sys）
• JAVA中的|JAVA中的 map,list,set
• JavaSE进阶|JavaSE08_泛型&Set$TreeSet&数据结构
• STL|C++ STL（第十四篇（Set 和 Map））
• C++修炼|C++ STL list、vector、deque、set、map、multimap、multiset、priority queue
• C-C++易混知识点|C++容易忘记的知识点——map和set（六）
• list
• java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔