泛型和集合

Java 使用集合来组织和管理对象，本节我们重点讲解泛型和集合。主要介绍 Collection、List、ArrayList、Map、HashMap、Set 和 HashSet、Collections、算法等内容。

知识点

• 泛型
• Collection
• List
• ArrayList
• Map
• HashMap
• Set 和 HashSet
• Collections
• 算法
• Stream
• List、Set、Map有什么区别和联系

一.集合的体系结构：

List、Set、Map是这个集合体系中最主要的三个接口。 List和Set继承自Collection接口。 Map也属于集合系统，但和Collection接口不同。

Set不允许元素重复。HashSet和TreeSet是两个主要的实现类。Set 只能通过游标来取值，并且值是不能重复的。

List有序且允许元素重复。ArrayList、LinkedList和Vector是三个主要的实现类。 ArrayList 是线程不安全的， Vector 是线程安全的，这两个类底层都是由数组实现的 LinkedList 是线程不安全的，底层是由链表实现的

Map 是键值对集合。其中key列就是一个集合，key不能重复，但是value可以重复。 HashMap、TreeMap和Hashtable是Map的三个主要的实现类。 HashTable 是线程安全的，不能存储 null 值 HashMap 不是线程安全的，可以存储 null 值

泛型

泛型即参数化类型，也就是说数据类型变成了一个可变的参数，在不使用泛型的情况下，参数的数据类型都是写死了的，使用泛型之后，可以根据程序的需要进行改变。
定义泛型的规则：

• 只能是引用类型，不能是简单数据类型。
• 泛型参数可以有多个。
• 可以用使用 extends 语句或者 super 语句 如 表示类型的上界，T 只能是 superClass 或其子类， 表示类型的下界，K 只能是 childClass 或其父类。
• 可以是通配符类型，比如常见的 Class<?>。单独使用 ? 可以表示任意类型。也可以结合 extends 和 super 来进行限制。

泛型

把类型明确的工作推迟到创建对象或调用方法的时候才去明确特殊的类型。
参数化类型：
把类型当作参数来传递
<数据类型>只能是引用类型

Question：为什么需要泛型

早期Java是使用Object来代表任意类型的，但是向下转型有强转的问题，这样程序就不太安全
首先，我们来试想一下：没有泛型，集合会怎么样

• Collection、Map集合对元素的类型是没有任何限制的。本来我的Collection集合装载的是全部的Dog对象，但是外边把Cat对象存储到集合中，是没有任何语法错误的。
• 把对象扔进集合中，集合是不知道元素的类型是什么的，仅仅知道是Object。因此在get()的时候，返回的是Object。外边获取该对象，还需要强制转换

有了泛型以后：

• 代码更加简洁【不用强制转换】
• 程序更加健壮【只要编译时期没有警告，那么运行时期就不会出现ClassCastException异常】
• 可读性和稳定性【在编写集合的时候，就限定了类型】

泛型类
泛型类就是把泛型定义在类上，用户使用该类的时候，才把类型明确下来。

用户想要使用那种类型，就在创建的时候指定类型。使用的时候，该类就会自动转化成用户想要的使用类型。

泛型方法：

刚才我们在类上定义泛型，现在我们也可以在方法上定义泛型。

类型通配符

现在有一个需求：
方法接收一个集合参数，遍历集合并把元素打印出来

**使用泛型的方法**

Collection

集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大内容：对外的接口、接口的实现和对集合运算的算法。

因为集合框架中的很多类功能是相似的，所以我们用接口来规范类。Collection 接口是 Java 集合框架里的一个根接口。它也是 List、Set 和 Queue 接口的父接口。Collection 接口中定义了可用于操作 List、Set 和 Queue 的方法——增删改查

List是一个接口，不能实例化，需要一个具体类来实现实例化。

List 集合中的对象按照一定的顺序排放，里面的内容可以重复。
List 接口实现的类有：ArrayList（实现动态数组），Vector（实现动态数组），LinkedList（实现链表），Stack（实现堆栈）。


List的方法有

ArrayList 和 List的区别

1.List是接口，List特性就是有序,会确保以一定的顺序保存元素.

ArrayList是它的实现类,是一个用数组实现的List.

Map是接口,Map特性就是根据一个对象查找对象.

HashMap是它的实现类,HashMap用hash表实现的Map,就是利用对象的hashcode(hashcode()是Object的方法)进行快速散列查找.(关于散列查找,可以参看<<数据结构>>)

ArrayList编程实例——学生信息管理系统

Map
Map 接口也是一个非常重要的集合接口，用于存储键 / 值对。Map 中的元素都是成对出现的，键值对就像数组的索引与数组的内容的关系一样，将一个键映射到一个值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。我们可以通过键去找到相应的值。

value 可以存储任意类型的对象，我们可以根据 key 键快速查找 value。Map 中的键 / 值对以 Entry 类型的对象实例形式存在。

KeySet()方法

返回keySet()方法，返回key，并且组成一个set集合。

HashMap

HashMap 是基于哈希表的 Map 接口的一个重要实现类。HashMap 中的 Entry 对象是 无序 排列的，Key 值和 value 值都可以为 null，但是一个 HashMap 只能有一个 key 值为 null 的映射（key 值不可重复）。

集合和数组的区别

(1)数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型）
(2)JAVA集合可以存储和操作数目不固定的一组数据。
(3)若程序时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类库，array不适用。

联系：使用相应的toArray()和Arrays.asList()方法可以回想转换。

数组转为集合：

Array.asList()

集合转为数组

集合.toArray()；

List、Set、Map有什么区别和联系

• list 和set 有共同的父类 它们的用法也是一样的 唯一的不太就是set中不能有相同的元素 list中可以
• list和set的用途非常广泛 list可以完全代替数组来使用
• map 是独立的合集 它使用键值对的方式来储存数据 键不能有重复的 值可以用
• map不像上边两种集合那个用的广泛 不过在servlet 和jsp中 map可是绝对的重中之重 页面之间传值全靠map

• 注意：Map没有继承Collection接口，Map提供key到value的映射。

List

• LinkedList类
  • LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
  • 注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

ArrayList和Vector的底层实现都是ElementData数组的实现，ArrayList和Vector的基本属性是ElementData数组，为数据结构，ArrayList和Vector的方法都是对ElementData的操作。

• ArrayList类
  • ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
  • size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
  • 每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并 没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
  • 和LinkedList一样，ArrayList也是非同步的（unsynchronized）。
  • 特点是：寻址容易，插入和删除困难；

• Vector类
  • Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和ArrayList创建的 Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例 如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该 异常。

ArrayList和Vector的区别

Vector和ArrayList都继承List的接口，List是Vector和ArrayList需要实现的方法。比如说在这张图内，LinkedList继承了List和Queue属于多继承，说明LinkedList这个类，同时需要实现List和Queue的方法。

首先我们给出标准答案：
1、Vector是线程安全的，ArrayList不是线程安全的。
2、ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。

Vector的源码

实现了List接口，底层和ArrayList一样，都是数组来实现的。分别看一下这两个类的add方法，首先来看ArrayList的add源码

再看Vector的add源码


方法实现都一样，就是加了一个synchronized的关键字，再来看看其它方法，先看ArrayList的remove方法

再看Vector的remove方法

方法实现上也一样，就是多了一个synchronized关键字，再看看ArrayList的get方法

Vector的get方法

再看看Vector的其它方法

无一例外，只要是关键性的操作，方法前面都加了synchronized关键字，来保证线程的安全性。当执行synchronized修饰的方法前，系统会对该方法加一把锁，方法执行完成后释放锁，加锁和释放锁的这个过程，在系统中是有开销的，因此，在单线程的环境中，Vector效率要差很多。（多线程环境不允许用ArrayList，需要做处理）。

至于底层数组的扩容区别，这里就不带着大家读源码了，有兴趣的朋友大家自己读吧，底层代码几乎是一样的，不同的只是计算后的新数组长度不一致。

和ArrayList和Vector一样，同样的类似关系的类还有HashMap和HashTable，StringBuilder和StringBuffer，后者是前者线程安全版本的实现。希望以后大家在面试过程中，能说出个因为所以，而不是一味的去背面试题，唯有理解，无需再背。

• **Stack 类
• Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得 Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set

• HashSet类
  • 它不允许出现重复元素；
  • 不保证集合中元素的顺序
  • 允许包含值为null的元素，但最多只能有一个null元素。
  • HashSet的实现是不同步的。

• TreeSet类
  • TreeSet类实现 Set 接口，该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素，根据使用的构造方法不同，可能会按照元素的自然顺序 进行排序，或按照在创建 set 时所提供的比较器进行排序。
    • TreeSet描述的是Set的一种变体——可以实现排序等功能的集合，它在将对象元素添加到集合中时会自动按照某种比较规则将其插入到有序的对象序列中.
  • HashSet是基于Hash算法实现的,其性能通常优于TreeSet,我们通常都应该使用HashSet,在我们需要排序的功能时,我门才使用TreeSet;

Map接口

• Hashtable类
  • Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。
    添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。
  • Hashtable 通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。
  • 作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。
  • Hashtable是同步的。

• HashMap类
  • HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。
    其迭代子操作时间开销和HashMap 的容量成比例,因此，不要将HashMap的初始化容量设得过高，或者load factor过低。
• WeakHashMap类
  • WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

• hashmap遍历的两种方式

• HashMap的遍历有两种常用的方法，那就是使用keyset及entryset来进行遍历

  • 方法一：
    

• 效率高,以后尽量要使用此种方式！

• 方法二：
• 

效率低,以后尽量少使用！

• HashMap的数据结构

  • HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next.
    数据

  • 
    

    • (补充：为什么要在HashMap里面实现一个静态内部类）
    • 因为HashMap需要对某个数据结构进行各种的方法操作，但是HashMap中的Entry不是基本类型，所以我们需要新建一个类（数据结构）来处理数据。因为，这个类（数据结构）是随着HashMap的创建而创建，所以要创建一个静态内部类。（静态属性随着类的创建而创建）

  • 
    

  • value的值是元素的key的哈希值对数组长度取模得到。如下面第二幅图中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

• **HashMap的存取实现

Set和HashSet

Set 接口也是 Collection 接口的子接口，它有一个很重要也是很常用的实现类——HashSet，Set 是元素无序并且不包含重复元素的 collection（List 可以重复），被称为集。
HashSet 由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。
接下来我们通过代码的形式来详细看一看吧

Collections
java.util.Collections 是一个工具类，他包含了大量对集合进行操作的静态方法。

常用方法

我们可以把集合理解为高级数组，collections的方法就是用来对集合和数组进行操作的。
所以我们把Collections叫做工具类。

**算法**

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，则执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量 —- 维基百科

1，排序算法