[数据结构与算法]高级部分：集合

集合

一、Java集合框架概述

1.1集合的含义

集合和数组都是对多个数据进行存储操作的结构
此时的存储，指内存层面的存储，不涉及持久化的存储

1.2数组存储的特点与弊端

数组初始化以后，长度就确定了。
数组声明的类型，就决定了进行元素初始化时的类型
数组初始化以后，长度就不可变了，不便于扩展。
数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。
同时无法直接获取存储元素的个数。
数组存储的数据是有序的、可以重复的。---->存储数据的特点单一

1.3集合存储的优点

①数组初始化以后，长度可以改变，便于扩展。
②数组中提供的属性和方法多，便于进行添加、删除、插入等操作，且效率高。
③可以同时直接获取存储元素的个数。
④集合存储的数据是无序的、但不可重复。

1.4集合框架

java集合可分为Collection和Map体系：
1.Collection接口：单列集合，用来存储一个一个的对象,其两个子接口：
①List接口：元素有序、重复的集合---->ArrayList、LinkedList、Vector都是List接口的实现类
②Set接口：元素无序、不可重复的集合---->HashSet(LinkedHashSet)、SortedSet(TreeSet)都是Set接口的实现类
2.Map接口：双列数据，保存具有映射关系“key-value对”的集合

二、Collection接口方法

1.添加 coll.add(Object o);|coll.addall(Collection coll);
2.获取有效元素的个数: int size();
3.清空集合: void clear();
4.是否是空集合:boolean isEmpty();
5.是否包含某个元素:
boolean contains(Object obj);
是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c);
也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较。
6.删除
boolean remove(Object obj) ;
通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection coll);
取当前集合的差集
7.取两个集合的交集
boolean retainAll(Collection c);
把交集的结果存在当前集合中，不影响c
8.集合是否相等: boolean equals(Object obj);
9.转成对象数组:Object[] toArray();
10.获取集合对象的哈希值:hashCode();
11.遍历:

		//第一种遍历
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //第二种遍历
        for(Object obj: coll){
            System.out.println(obj);
        }

三、Collection子接口一：List

1.主要分为：ArrayList、LinkedList、Vector

2.ArrayList和LinkedList的异同

二者都线程不安全，相对线程安全的Vector，执行效率高。
此外，ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

3.ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

四、Collection子接口之二：Set接口

1.Set 接口概述

1.Set接口是Collection的子接口，set接口没有提供额外的方法。
2.Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。
3.Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。
4.|----Collection接口：单列集合，用来存储一个一个的对象

• |----Set接口：存储无序的、不可重复的数据 -->高中讲的“集合”
• • |----HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
• |----LinkedHashSet：遍历其内部数据时，可以按照添加的顺序遍历，LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet。
• |----TreeSet：可以按照添加对象的指定属性，进行排序。

5.Set：存储无序的、不可重复的数据。以HashSet为例说明：

1. 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
2. 不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。

2.Set实现类之一：HashSet

2.1向HashSet中添加元素的过程：

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断数组此位置上是否已经有元素：

• 如果此位置上没有其他元素，则元素a添加成功。 —>情况1
• 如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值：
• • 如果hash值不相同，则元素a添加成功。—>情况2
• • 如果hash值相同，进而需要调用元素a所在类的equals()方法：
• • • equals()返回true,元素a添加失败
• • • equals()返回false,则元素a添加成功。—>情况3
      
      对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。
      jdk 7 :元素a放到数组中，指向原来的元素。
      jdk 8 :原来的元素在数组中，指向元素a
      总结：七上八下

2.2重写 hashCode() 方法的基本原则

• 在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。
• 当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等。
• 对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

2.3重写 equals() 方法的基本原则

• 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候，总是要改写hashCode()，根据一个类的equals方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法，它们仅仅是两个对象。
• 因此，违反了“相等的对象必须具有相等的散列码”。
• 结论：复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

3.Set实现类之二：LinkedHashSet

LinkedHashSet：遍历其内部数据时，可以按照添加的顺序遍历，LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet。

4.Set实现类之三：TreeSet

4.1TreeSet 概述：

首先，如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable 接口。
其次，排序方式分为自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

4.2自然排序

• 向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。
• 因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是同一个类的对象。
• 对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值。
• 当需要把一个对象放入 TreeSet 中，重写该对象对应的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果：如果两个对象通过equals() 方法比较返回 true，则通过 compareTo(Object obj) 方法比较应返回 0。

4.3定制排序

• TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
• 利用int compare(T o1,T o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。
• 要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
• 此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
• 使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

五、Map接口

1.Map接口概述

|----Map:双列数据，存储key-value对的数据 —类似于高中的函数：y = f(x)

• |----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
• • |----LinkedHashMap:保证在遍历map元素时，可以按照添加的顺序实现遍历。
    原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。对于频繁的遍历操作，此类执行效率高于HashMap。
• |----TreeMap:保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序，底层使用红黑树
• |----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
• • |----Properties:常用来处理配置文件。key和value都是String类型

2.Map结构的理解(完全等同于数学中的函数)：

①Map中的key:无序的、不可重复的，使用Set存储所有的key —> key所在的类要重写equals()和hashCode() （以HashMap为例）
②Map中的value:无序的、可重复的，使用Collection存储所有的value —>value所在的类要重写equals()
③ 一个键值对：key-value构成了一个Entry对象。
④Map中的entry:无序的、不可重复的，使用Set存储所有的entry

3.HashMap的底层实现原理（以jdk7为例说明）：

 HashMap map = new HashMap()；  
 map.put(key1,value1); 

在实例化以后，底层创建了长度是16的一维数组Entry[] table。
首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。

• 如果此位置上的数据为空，此时的key1-value1添加成功。 ----情况1
• 如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值：
• • 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。----情况2
• • 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：
    如果equals()返回false:此时key1-value1添加成功。----情况3
    如果equals()返回true:使用value1替换value2。

补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

★jdk8 相较于jdk7在底层实现方面的不同：

1. new HashMap():底层没有创建一个长度为16的数组
2. jdk 8底层的数组是：Node[],而非Entry[]
3. 首次调用put()方法时，底层创建长度为16的数组
4. jdk7底层结构只有：数组+链表。jdk8中底层结构：数组+链表+红黑树。
   4.1 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
   4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

4.Map中的常用方法

4.1 添加、删除、修改操作：

Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key)：移除指定key的key-value对，并返回value
void clear()：清空当前map中的所有数据

4.2元素查询的操作：

Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等

4.3 元视图操作的方法（遍历）：

Set—> .keySet()：返回所有key构成的Set集合
Collection—> .values()：返回所有value构成的Collection集合
Set—> .entrySet()：返回所有key-value对构成的Set集合

总结：常用方法：

• 添加：put(Object key,Object value)
• 删除：remove(Object key)
• 修改：put(Object key,Object value)
• 查询：get(Object key)
• 长度：size()
• 遍历：keySet() / values() / entrySet()

5.Properties类

• 常用来处理配置文件。key和value都是String类型
• Properties 类是 Hashtable 的子类，该对象用于处理属性文件
• 由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型
• 存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);