（一）所有集合的描述（二）集合体系图fail—fast和fail—safeEnumeration 和 Iterator（一）Iterable和iterator1．检查迭代器里面是否包含指定的元素CollectionVectorStackMap集合1．Map架构,Map.Entry,AbstractMap,SortedMap,NavigableMap,Dictionary2．Map集合遍历(entrySet效率最高)3．Map集合总结(HashMap, Hashtable, TreeMap, WeakHashMap等使用场景)4．map转成list或者是set5．初始化一个不可变的MapHashMap1．详细介绍2．API 遍历方式3．源码分析4．并发下的扩容(死循环)5．扩容6．排序HashTableLinkedHashMap（一）原理（二）其它1．HashMap、TreeMap和HashTable的区别IdentityHashMapTreeMap1．排序WeakHashMap集合&迭代器（一）Properties集合（二）集合判断元素的唯一性1．list集合判断元素唯一性的依据2．set集合判断元素唯一性的依据3．判断元素唯一性的原理分型 （一）所有集合的描述 集合类型 描述 ArrayList 一种可以动态增长和缩减的索引序列 LinkedList 一种可以在任何位置进行高效地插入和删除操作的有序序列 ArrayDeque 一种用循环数组实现的双端队列 HashSet 一种没有重复元素的无序集合 TreeSet 一种有序集 EnumSet 一种包含枚举类型值的集 LinkedHashSet 一种可以记住元素插入次序的集 PriorityQueue 一种允许高效删除的最小元素的集合 HashMap 一种存储键值对关系的数据结构 TreeMap 一种键值对有序排列的映射表 EnumMap 一种键值对属于枚举类型的映射表 LinkedHashMap 一种可以记住键值项添加顺序的映射表 WeakHashMap 一种其值无用武之地后可以被垃圾回收器回收的映射表 IdentityHashMap 一种用==而不是用equals比较键值对的映射表 （二）集合体系图 fail—fast和fail—safe 一：快速失败（fail—fast）在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。二：安全失败（fail—safe）采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。 两者比较: Fail Fast Iterator Fail Safe Iterator Throw ConcurrentModification Exception Yes No Clone object(克隆对象) No Yes Memory Overhead(内存开销) No Yes Examples(案例) HashMap,Vector,ArrayList,HashSet CopyOnWriteArrayList,ConcurrentHashMap | 两者详细区别参考下面: https://www.yuque.com/docs/share/7d44d9cb-e37d-4cc0-a60e-0c0d9473e52d?#https://www.yuque.com/docs/share/a8c922b6-ce76-4429-92bc-d8b3333982e9?# Enumeration 和 Iterator Enumeration已经被Iterator替代了,不要研究过深了.它是JDK 1.0引入的抽象类。作用和Iterator一样，也是遍历集合；但是Enumeration的功能要比Iterator少。在上面的框图中，Enumeration只能在Hashtable, Vector, Stack中使用。 参考: https://www.yuque.com/docs/share/c01da62a-c915-4763-a5a7-7057b2a612ea?# Iterator(迭代器)” 或 “Enumeration(枚举类)” 去遍历集合. 区别: 1.函数接口不同 Enumeration只有2个函数接口。通过Enumeration，我们只能读取集合的数据，而不能对数据进行修改。 Iterator只有3个函数接口。Iterator除了能读取集合的数据之外，也能数据进行删除操作。 2. Iterator支持fail-fast机制，而Enumeration不支持。Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类，这些类都是JDK 1.0中加入的，Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步，而在Vector、Hashtable实现Enumeration时，添加了同步。Iterator 是JDK 1.2才添加的接口，它也是为了HashMap、ArrayList等集合提供遍历接口。Iterator是支持fail-fast机制的：当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。 Enumeration 比 Iterator的遍历集合速度更快 ??? 这里我测试效率感觉好像差距并不大.Hashtable中Iterator是通过Enumeration去实现的，而且Iterator添加了对fail-fast机制的支持；所以，执行的操作自然要多一些。 （一）Iterable和iterator Iterable是接口,iterator是这个接口里面的方法. public interface Iterable { / * Returns an iterator over elements of type {@code T}. @return *an Iterator. / Iterator iterator(); 一个集合对象要表明自己支持迭代，能有使用foreach语句的特权，就必须实现Iterable接口，表明我是可迭代的！然而实现Iterable接口，就必需为foreach语句提供一个迭代器。这个迭代器是用接口定义的 iterator方法提供的。也就是iterator方法需要返回一个Iterator对象。 Iterator 包含3个方法: hasNext , next , remove。remove按需求实现，一般它很少用到，以至于Eclipse接口方法自动补全时，都忽略了remove放方法。1、每次在迭代前 ，先调用hasNext()探测是否迭代到终点（本次还能再迭代吗？）。2、next方法不仅要返回当前元素，还要后移游标cursor3、remove()方法用来删除最近一次已经迭代出的元素4、迭代出的元素是原集合中元素的拷贝（重要）5、配合foreach使用 1．检查迭代器里面是否包含指定的元素org.springframework.util.CollectionUtils ArrayList objects = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 4));Iterator iterator = objects.iterator(); boolean contains = CollectionUtils.contains(iterator, 1);//trueboolean asas = CollectionUtils.contains(iterator, 99); //false CollectionCollection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作：添加、删除、清空、遍历(读取)、是否为空、获取大小、是否保护某元素等等。它主要的两个分支是：List 和 Set。List和Set都是接口，它们继承于Collection。List是有序的队列，List中可以有重复的元素；而Set是数学概念中的集合，Set中没有重复元素！List和Set都有它们各自的实现类。为了方便，我们抽象出了AbstractCollection抽象类，它实现了Collection中的绝大部分函数；这样，在Collection的实现类中，我们就可以通过继承AbstractCollection省去重复编码。AbstractList和AbstractSet都继承于AbstractCollection，具体的List实现类继承于AbstractList，而Set的实现类则继承于AbstractSet。另外，Collection中有一个iterator()函数，它的作用是返回一个Iterator接口。通常，我们通过Iterator迭代器来遍历集合。ListIterator是List接口所特有的，在List接口中，通过ListIterator()返回一个ListIterator对象。 详细介绍:https://www.yuque.com/docs/share/3c55e350-8007-40ac-bfa2-d3f693fc5d4c?# Vector实现自List接口，内部实现是个数组，线程安全，扩容策略是(capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2)。 简介,API,源码,使用示例,遍历方式参考:https://www.yuque.com/docs/share/b971e9e2-65cf-4cd3-8d4b-0fdcecf83fcc?# Stack简介,继承关系,构造函数,API,源码,使用案例 参考: https://www.yuque.com/docs/share/094de3c1-2f2b-41c7-ad70-aa5972aac84c?# Map集合 1．Map架构,Map.Entry,AbstractMap,SortedMap,NavigableMap,Dictionary AbstractMap类是一个抽象类,提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作。SortedMap是一个继承于Map接口的接口。它是一个有序的SortedMap键值映射。SortedMap的排序方式有两种：自然排序 或者 用户指定比较器。 插入有序 SortedMap 的所有元素都必须实现 Comparable 接口（或者被指定的比较器所接受）。NavigableMap是继承于SortedMap的接口。它是一个可导航的键-值对集合，具有了为给定搜索目标报告最接近匹配项的导航方法。 Dictionary是JDK 1.0定义的键值对的接口，它也包括了操作键值对的基本函数。 参考:https://www.yuque.com/docs/share/70735211-b502-41f8-b134-2840511177b3?# 2．Map集合遍历(entrySet效率最高)map遍历方式效率问题总结大量数据查找时候entrySet速度更快,建议用entrySet方式 ,其中iterator遍历的方式最快,然后就是for遍历的方式第二快entrySet利用foreach遍历(效率高)/遍历map EntrySet /public void traversalMapToEntrySet(){ Map map = new HashMap<>(); map.put(“AAA”,“aaa”); map.put(“BBB”,“bbb”); map.put(“CCC”,“ccc”); map.put(“DDD”,“ddd”); Set> entries = map.entrySet(); for (Map.Entry entry : entries) { String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + “————“ +value); }} 3．Map集合总结(HashMap, Hashtable, TreeMap, WeakHashMap等使用场景) 参考: https://www.yuque.com/docs/share/a4920654-3cce-469c-90c6-2f4e7fb3d85d?# 4．map转成list或者是set转成set的方法和转成list的方法几乎是一样的 HashMap map = new HashMap<>();map.put(1,10);map.put(2,20);map.put(3,30); /list集合里面装的数据都是map的key/ArrayList keyList = new ArrayList<>(map.keySet()); /list集合里面装的数据都是map的value/ArrayList valueList = new ArrayList<>(map.values()); /list集合里面装的数据都是map的keyvalue 类似这样的格式 [1=10, 2=20, 3=30] /ArrayList entryList = new ArrayList<>(map.entrySet()); 5．初始化一个不可变的Map public class lmxiTest { private static Map map1 = new HashMap<>(); static { map1.put(8, 9); map1.put(88, 99); map1 = Collections.unmodifiableMap(map1); } }使用方法: 直接类名.方法名就调用了. 初始化的map只有在未调用Collections.unmodifiableMap方法之前的以上两个属性. Collections.unmodifiableMap 是产生了一个只读的map,调用map的put方法就会报异常, HashMap HashMap是无序的,保存数据是键值对.key如果重复那么它对应的value就会被后面添加的相同的key的value覆盖掉.当访问的值不存在的时候，方法就会抛出一个NoSuchElementException异常,当对象的类型和Map里元素类型不兼容的时候，就会抛出一个 ClassCastException异常当在不允许使用Null对象的Map中使用Null对象，会抛出一个NullPointerException 异常。当尝试修改一个只读的Map时，会抛出一个UnsupportedOperationException异常。 HashMap的内部实现是数组加链表 横向的数组结构,数组是存放链表的头结点的 , 头结点会有指向下一个链表的指针. 所以在元素里面,它的组成是 一个key value 以及链表的下一个节点的指针.理论上hash查找 只需要一次查找就可以定位到指定数据内部数组的长度默认是16 加载因子是 0.75 空间换时间,HashMap存放顺序不是从0索引开始存的 加载因子0.75是指当我存放元素的个数是我们内部数组的长度的0.75倍,我们就要进行数组的扩容 什么是加载因子:如果哈希表中的元素放得太满，就必须进行rehashing(再哈希)。再哈希使哈希表元数增倍，并将原有的对象重新导入新的哈希表元中，而原始的哈希表元被删除 1．详细介绍 https://www.yuque.com/docs/share/9a81dc2c-66ca-4117-97fd-c1f10e9a4c55?# 2．API 遍历方式 https://www.yuque.com/docs/share/9a81dc2c-66ca-4117-97fd-c1f10e9a4c55?# 3．源码分析https://www.yuque.com/docs/share/e49f8989-a63a-445b-80ae-2efb302a8be0 4．并发下的扩容(死循环) 参考:https://www.yuque.com/docs/share/cd7130ea-49d1-4e4c-a001-af036c80eb7b 5．扩容 https://www.yuque.com/docs/share/c3239f75-d57a-4fed-92bb-5f1d7d3112d5?# HashMap的加载因子默认是 0.75 0.75是指当我存放元素的个数是我们内部数组的长度的0.75倍,我们就要进行数组的扩容 综合来说，HashMap一次扩容的过程：1、取当前table的2倍作为新table的大小2、根据算出的新table的大小new出一个新的Entry数组来，名为newTable3、轮询原table的每一个位置，将每个位置上连接的Entry，算出在新table上的位置，并以链表形式连接4、原table上的所有Entry全部轮询完毕之后，意味着原table上面的所有Entry已经移到了新的table上，HashMap中的table指向newTable 6．排序 HashTableHashTable已经过时了,建议不要太深入研究和HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的。Hashtable 的实例有两个参数影响其性能：初始容量 和 加载因子。容量 是哈希表中桶 的数量，初始容量 就是哈希表创建时的容量。注意，哈希表的状态为 open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括 get 和 put 操作，都反映了这一点） API,源码,遍历方式,示例 https://www.yuque.com/docs/share/d3295e5e-567c-4438-a3ce-9dc616b2a228?# LinkedHashMap （一）原理 在LinkedHashMap中可以保持两种顺序，分别是插入顺序和访问顺序，这个是可以在LinkedHashMap的初始化方法中进行指定的。 LinkedHashMap继承HashMap，拥有HashMap的所有特性，并且额外增加了按一定顺序访问的特性。LinkedHashMap可以看成是 LinkedList + HashMap。 在HashMap的基础上，又单独维护了一个双向循环链表。有一个重要参数是accessOrder，accessOrder为true时，每次调用get方法访问行为发生后，会把最近访问的对象移动到头部，而超出容量移除对象时，是从尾部开始的，利用它并且覆写boolean removeEldestEntry方法可以实现一个LRU的队列。 参考:继承体系,存储结构,源码,总结,API,如何实现LRU缓存淘汰策略. https://www.yuque.com/docs/share/626b62b8-4b19-4e4b-858a-633d691b25c9 （二）其它 1．HashMap、TreeMap和HashTable的区别 Map接口有三个比较重要的实现类，分别是HashMap、TreeMap和HashTable。TreeMap是有序的，HashMap和HashTable是无序的。Hashtable的方法是同步的，HashMap的方法不是同步的。这是两者最主要的区别。这就意味着Hashtable是线程安全的，HashMap不是线程安全的。HashMap效率较高，Hashtable效率较低。如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap。 查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized关键字，而HashMap的源码中则没有。Hashtable不允许null值，HashMap允许null值（key和value都允许） 父类不同：Hashtable的父类是Dictionary，HashMap的父类是AbstractMapHashtable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。 IdentityHashMap不是线程安全的HashMap. 比较key不是使用equals来比较，而是使用“==”来比较，只要地址不等（即不是同一个对象）即可共存，也就是说，key是可以重复的(不同的内存地址但内容相等)。 参考: 官方说明:https://docs.oracle.com/javase/6/docs/api/java/util/IdentityHashMap.html自己笔记:https://www.yuque.com/docs/share/3642a5fe-dea4-42fd-87df-abe76638d927?# TreeMap TreeMap 会自动根据Map的Key排序(不论是数字还是字符串),它是通过红黑树实现的。 TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。 TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。 TreeMap 实现了Cloneable接口，意味着它能被克隆。 TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。 TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。 API 构造 使用方式 遍历 参考: https://www.yuque.com/docs/share/24f9928f-d2b8-4276-9899-2603ba8533a7?# 源码 参考:https://www.yuque.com/docs/share/8a8af1df-df61-4c41-ac6c-4b18ccd34fa3?# 1．排序TreeMap默认按key进行升序排序，如果想改变默认的顺序，可以使用比较器: 按value 排序 WeakHashMapWeakHashMap的键是“弱键”,当WeakHashMap某个键不再正常使用时，会被从WeakHashMap自动删除。WeakHashMap可以作为简单缓存表的解决方案，当系统内存不足时，垃圾收集器会自动的清除没有在任何其他地方被引用的键值对。如果需要用一张很大的Map作为缓存表时，那么可以考虑使用WeakHashMap。一般用于单线程当中，非线程安全,如果想线程安全,可以使用 Collections.synchronizedMap 方法来构造同步的 WeakHashMap。 WeakHashMap的坑:WeakHashMap的可以不要用字符串常量，因为字符串常量是放在常量池中， 程序运行期间是一直都在的，如果要用String作为key的话，可以用 new String()代替 详细介绍:构造函数 api 使用示例 WeakHashMap和 HashMap区别 遍历方式 源码 数据结构https://www.yuque.com/docs/share/165fbb4c-ec18-41fa-b433-74af5e3a3bb1?# 集合&迭代器 （一）Properties集合 参考:https://www.yuque.com/docs/share/bb80d8d2-376f-4114-bd41-1f3ae74ae01b?# Properties集合是HashTable的子类,而HashTable是map的实现类,因此,map中的方法,Properties都可以直接使用;但是,在开发中,会使用Properties集合特有的方法,而不是用的方法;Properties集合虽然属于map体系,但是没有泛型,里面只保存字符串类型的键和字符串类型的值;而且Properties集合可以直接与IO流结合,将集合中的数据与硬盘上文件中的数据互转; （二）集合判断元素的唯一性 1．list集合判断元素唯一性的依据对于list集合来说,可以保存重复的元素,因此,需要需要判断元素是不是在集合中存在的方法有两个:1:contains方法;2:remove方法;这两个方法都是仅仅依赖元素的equals方法;与hashCode方法没有任何关系; 2．set集合判断元素唯一性的依据对于set集合来说,不能保存重复的元素,因此,需要需要判断元素是不是在集合中已经存在的方法有3个:1:add方法2:contains方法;3:remove方法;这3个方法都是依赖equals方法和hashCode方法共同结果;顺序是:先调用hashCode方法,如果两个对象的hash值不一致,那么直接得出结果:两个对象不一样;如果hash值一样,那么会再次使用equals方法,确认两个对象是否一致; 对于set集合来说:equals方法和hashCode方法必须同时重写,缺一不可! 3．判断元素唯一性的原理分型在Object类中默认情况下:hashCode生成规则是根据对象的物理地址生成;equals方法,默认是比较对象的物理地址; 在子类中重写的情况下:hashCode生成规则是根据对象的所有成员变量的值生成的(采用了java中的一套固定算法得到的);equals方法,默认是比较对象的物理地址;
![集合框架[笔记] - 图1](/uploads/projects/zjj1994@javabasic/1632bed68cf1a59db7cf7ae4b0073568.jpeg)
