2020 年 5 月 23 日 Java 集合专题

关注
发布于: 2020 年 05 月 23 日
        本章节主要是集合框架进行阐述，以回顾之前的学习知识，主要是从以下几个章节进行阐述，Java集合框架，具体的集合，映射，视图与包装器，算法，遗留的集合。
﻿
1、Java集合框架       Java集合类库也是将实现与接口分离，我们可以先以队列为例，队列接口指出可以在队列的尾部添加元素，在队列的头部删除元素，并且可以查看队列中元素的个数，特点就是先进先出。
      队列的实现通常有两种：一种是使用循环数组，另一种是使用链表。循环数组比链表的效率更高，但是循环数组一个有界集合，即容量有限
﻿
1.1  Collection接口： Colleaction<E>
   1、集合接口一个泛型接口。
        2、集合类的基本接口是Collection接口，这个接口有两个比较常用的方法，一个是add，另一个是iterator（）。如果添加元素确实改变了集合就返回true，如果集合没有发生变化就返回false。
﻿
1.2  迭代器：    Iterator<E>
   迭代器接口也是一个泛型接口
        迭代器接口包含四个方法：next()，hasNext(),remove(),forEachRemaing()。
        haseNext和next的区别就是在到达尾部的时候，next方法会抛出NoSuchElementException，因此在调用next方法的时候一定要先执行hasnext方法。
        Java中迭代的查找操作与位置变更操作是紧密相连的，查找一个元素的唯一方法是next，而在执行查找操作的同时，迭代器的位置随之向前移动。应该将Java的迭代器认为是位于两个元素之间，当调用next的时候，迭代器就越过下一个元素，并返回刚刚被越过的那个元素的引用。
        remove方法移除的是当前元素不是下一个元素，如果在调用Remove方法之前没有调用next方法，是不合法的，会抛出一个IllegalStateException异常，因此remove方法将会删除上一次调用next方法时返回的元素
﻿
1.3 集合框架中的接口
      集合有两个基本接口：Collection 和  Map 
Map的继承结构
List是一个有序的集合，元素会增加到容器中特定的位置，可以采用迭代器和数组索引的方式来访问。
﻿
2、具体的集合本章节主要是对链表、数组列表、散列表、树集、队列与双端队列、优先级队列进行说明。
常见的具体集合有:
1、ArrayList                      一种可以动态增长和缩减的索引序列 
2、LinkedList                    一种可以在任何位置进行高效的插入和删除的有序序列
3、ArrayQueue                一种用循环数组实现的双端队列
4、HashSet                      一种没有重复元素的无序集合
5、TreeSet                       一种有序集
6、EnumSet                     一种包含枚举类型值的集
7、LinkedHashSet           一种可以记住元素插入顺序的集
8、HashMap                   一种存储键/值关联的数据结构
9、TreeMap                    一种存储有序队列的映射表
10、LinkedHashMap       一种可以记住键值对添加次序的映射表
﻿
注：数组和数组列表最大的缺陷就是从数组中间删除一个元素要付出很大的代价，处于被删除元素之后的数据都需要逐一向前移动一位。
2.1 链表    LinkList
       所有的链表实际上都是双端链接的，即每个节点还存着指向前驱节点的引用。
       链表和泛型集合之间有个重要的区别就是链表是一个有序的集合每个对象的位置十分重要，LinkList.add方法将对象添加到链表的尾部 。在迭代器调用next方法之后，再利用set进行赋值，会将一个新的值取代调用next或previous方法返回前的上一个元素。
       如果某个迭代器在修改集合时，另一个迭代器对其进行遍历，一定会出现混乱的情况
﻿
2.2数组列表      ArrayList
          List接口用于描述一个有序集合，并且集合中的元素的位置有着十分重要的作用，有两种访问元素的协议，一种是迭代器，另一种是get和set。后者适用于数组的访问。ArrayList封装了一个动态再分配的对象数组。
         Vector 和ArrayList的区别就是：Vector类所有的方法都是同步的，可以由两个以上的线程安全的访问一个Vector对象 ,如果是一个线程访问Vector则需要耗费大量的线程开销，ArrayList方法不是同步的。
     
2.3 散列集       HashSet
         数组和列表可以按照人们的意愿排列元素的次序。只能按照次序查找元素，而另一种数据结构是可以快速的查找所需要的的元素，这就是散列表。
         散列表为每一个对象生成一个整数，称为散列码。散列码是由对象的实例域产生的一个整数，具有不同数据域的对象将会产生不同的散列码。
          在java 中散列表是用数组实现的，每个列表被称为桶，要想查找表中对象的位置就需要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。
          桶数是指用于收集具有相同散列值的桶的数目。如果想要插入到散列表中的元素太多，就会增加冲突的可能性，降低运行性能。标准类库中使用的桶数是2的幂，默认值是16.
         如果散列表太满就需要再散列，如果要对散列表再散列就需要创建一个桶数更多的表，并将所有的新元素插入到这个新表中，然后丢弃原来的表。
        装填因子就是决定何时对散列表进行再散列，装填因子默认为0.75
﻿
2.4树集       TreeSet
          TreeSet与散列集十分类似，它比散列集有所改进。树集是一个有序集合，可以以任意顺序插入到集合中。在对集合进行遍历时，每个值将自动的按照排序后的顺序呈现。
          
2.5 队列与双端队列        ArrayQueue
          队列可以有效的在尾部添加一个元素和在头部删除一个元素，而有两个端的队列即双端队列，双端队列允许人们在头部和尾部同时添加和删除元素，不支持在队列中间添加元素
﻿
2.6 优先级队列  PriorityQueue
优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。
         也就说无论何时调用remove方法，总会获得当前优先级队列中最小的元素，优先级队列并没有对数据进行排序而是使用了一种优雅且高效的数据结构称为堆，堆是一种可以自我调整的二叉树，对树进行添加和删除操作可以让最小的元素移动到根。
﻿
      3、映射       第二部分主要是对集进行了描述，集是一个集合，可以快速的查找现有的元素，但是如果想获取对应的值，并不方便。映射就是通过键的信息来获取对应的值的信息。映射是用来存放键值对的。
﻿
1、基本的映射操作
Java映射中提供了两个通用的实现HashMap和TreeMap这两个类都实现了Map接口。
散列映射对键进行散列，树映射是用键的整体顺序对元素进行排序，并将其组织成索引树。
键必须是惟一的。如果对同一个键调用两次put方法，第二个值就会取代第一个值，实际上put将返回这个键参数的上一个值。
remove方法用于从映射中删除给定键的元素。
size方法用于返回映射中的元素数
﻿
2、更新值的映射
常见的更新方法有：put、merge,putIfAbsent
获取值的方法：getOrDefault(word,0)
﻿
3、映射视图
映射视图主要就是用来遍历集合中的元素。
集合框架本身不认为映射本身是一个集合，不过可以得到映射视图——这是实现了Collection接口或某个接口子对象。
有三种视图：键集合（keySet）、值集合（values）、键值对集合（entrySet）
注意：如果再视图上调用迭代器的remove方法，实际上会从映射中删除这个键和与它有关的键值。不过能能想键集视图中增加元素
﻿
4、链接散列集与映射
链接散列集合映射主要是用来保证元素得插入顺序。
LinkedHashSet和LinkedHashMap用来记住插入元素项的顺序，这样就可以避免在散列表中的项从表面上看是随机的。
 链接散列映射表将用访问顺序，而不是插入顺序，对映射表条目进行迭代。每次调用get或put，受到影响的条目将从当前的位置删除，并放到条目链表的尾部（只有条目在链表中的位置会受影响，而散列表中的桶不会受影响。一个条目总位于与键散列码对应的桶中）。要想构造一个这样的散列映射表，请调用    LinkedHashffap<K, V>(initialCapacity, loadFactor, true)
﻿
5、枚举集与映射
      EnumSet是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet内部是用位序列实现。
      EnumMap是一个键类型为枚举类型的映射。
﻿
6、标识散列映射
类IdentityHashMap有特殊的作用，在这个类中键的散列值不是用HashCode函数计算的，而是用System.identityHashCode方法计算的。
﻿
       4、视图与包装器keySet方法返回一个实现Set接口的类对象，在这个类的方法对原映射进行操作，这种集合称为视图。
1、轻量级视图包装器
            ArrayList.asList(数组对象)   ：该方法返回的不是一个ArrrayList。它是一个视图对象，带有访问底层数组的get和set方法。改变数组大小的所有方法都会抛出一个Unsupported OperationException异常。
           Collection.nCopies(100,"DEFAULT")：创建100个包含字符串的List，每个串都被设置为“DEFAULT”。
            2、子范围
            假设有一个列表staff,如果调用staff.subList(10,20 )，将从中取出第10个到第19个元素，并返回一个List集合。第一个索引包含在内，第二个索引则不包含在内。
可以将任何操作应用于子范围，并能够自动的反应整个列表的情况。
3、不可修改的视图
         Collection还有几个方法，用于产生集合的不可修改视图，这些视图对现有集合增加了一个运行时的检查.如果发现视图对集合进行修改，就抛出一个异常。同时这个集合将保持未修改的状态。
常见的方法有：
Collection.unmodifiableCollecion
Collection.unmodifiableList
Collection.unmodifiableSet
4、同步视图
       如果有多线程访问集合，就必须确保集不会被以外的破坏。例如一个线程视图将元素添加到散列表中，同时另一个线程正在对散列表进行再散列。其结果将会是灾难性的。
        Collection类的静态synchronizedMap方法可以将任何一个映射表转换成具有同步访问方法的Map。
Map<String，String> map = Collection.synchronized(new HashMap<String,String>());
现在就可以由多线程访问map对象了。像get和set方法都必须是同步的，即在另一个线程调用另一个方法之前，刚才的方法调用必须彻底完成.
5、受查视图
"受查"视图用来对泛型类型发生问题时，提供调试支持。
ArrayList<String> strings = new ArrayList<>();
List<String> safe = Collection.checkList(strings,String.class)
视图的add方法将检测插入的对象是否属于给定的类。如果不属于给定的类，将立即抛出一个异常。
﻿
     5、集合中的算法               
1、排序与混排
Collection类中sort方法可以对实现了List接口的集合进行排序。
List<String> staff = new  LinkedList<>();
Collection.sort(staff);
               如果想要使用其他方式对列表进行排序，可以使用List接口的sort方法并传入一个Comparator对象。例如：staff.sort(Comparator.comparingDouble(Employ::getSalary))。
如果想使用降序来进行排列，
 staff.sort(Comparator.reverseOrder())。
                 staff.sort(Comparator.comparingDouble(Employ::getSalary).reversed())。
Collections类有一个算法shuffle，其功能与排序刚好相反。即随机的混排列表中的元素顺序
﻿
2、二分查找
         Collection类的binarySearch方法实现了二分查找法。注意集合必须是排好序的，否则算法将返回错误的答案。如果集合没有采用Comparable接口的compareTo方法进行排序，就还需要提供一个比较器对象。
Collection.binarySearch(c,element);
Collection.binarySearch(c,element,comparator);
如果binarySearch方法的返回值大于0，表示匹配对象的索引，如果返回负值，则表示没有匹配元素
3、简单算法
简单算法主要就是避免一些简单的循环比较集合中的元素
例如：
Collections.replaceAll("C++","JAVA");
Collections.max();
Collections.min()
Collections.copy;
Collections.fill();
Collections.reverse();
4、批操作
常见的操作：
coll1.removeAll（coll2）；   --从coll1中移除coll2的所有元素
coll1.retainAll（coll2）     --从集合1中删除未出现在coll2中的元素
Map<String,Employee> staffMap =  。。。
Set<String> terminatedIDs =  ....
staffMap.keySet().removeAll(terminatedIDs);   --从staffmap中移除set中出现的key
﻿
5、集合和数组的转换
如果是想要实现把一个数组转换为一个集合
String []  values =  ....
HashSet<String> staff = new HashSet<>(Arrays.asList(values));
如果想要实现集合转化为数组
staff.toArray(new String[staff.size()]);     --不会创建一个新的数组
或者
staff.toArray(new String[0])                 --会创建一个新的数组
﻿
   6、遗留的集合主要是对Hashtable，枚举，属性映射，栈，位集等进行说明。
1、HashTable
HashTable和HashMap类的作用一样。实际上他们拥有相同的接口。与Vector方法一样。Hashtable方法也是同步的。如果需要并发访问，则需要使用ConcurrentHashMap
2、枚举       Enumeration
遗留集合使用Enumeration接口对元素列进行遍历。Enumeration接口有两个方法，即hasMoreElements 和nextElement。这两个方法和Iterator接口的hasNext方法和next方法十分类似
3、属性映射        Properties
属性映射是一个类型非常特殊的映射结构，具有以下3个特性：
1、键与值都是字符串
2、表可以保存到一个文件中，也可以从文件中加载
3、使用一个默认的辅助表
Properties（），getProperty()
4、栈  Stack
Stack 类扩展为Vector，vector类并不太让人满意，它可以让栈使用不属于栈的insert和remove方法，即可以在任何地方进行插入和删除操作，而不仅仅是在栈顶