集合

2019-08-13 | 阅读：次

概念

集合与数组的对比

集合:就是一个存储数据的容器。
集合与数组一样，也是一个容器，与数组的区别:

数组长度固定，集合的长度不固定。

数组可以存储基本类型和引用类型，集合中存储的元素类型只能是引用类型(自动装箱和拆箱)。

集合的框架结构

Collection集合的框架结构

Map集合的框架结构

Collecation集合

Collection 层次结构中的根接口。Collection 表示一组对象，这些对象也称为collection的元素。一些collection允许有重复的元素，而另一些则不允许。一些collection是有序的，而另一些则是无序的。

List派系:可以重复、有序

Set派系:不能重复、无序

代码就不贴出了。循环遍历可以用增强for和迭代器

List集合

特点: 相对有序存储，可以存储相同元素（不排重），可以通过下标访问集合元素
List接口中可以使用独有的迭代器ListIterator，具有反向遍历的功能

ListIterator迭代器

列表迭代器，可以向前向后遍历，修改，添加，删除

ArrayList集合

特点: 相对有序存储，可以存储相同元素（不排重），可以通过下标访问集合元素，通过数组实现的集合。
线程不安全（适用在对元素查询、遍历操作，不适合插入和删除）

删除引用类型的数据时是依据根据地址但是如果删除数据相同，地址不相同，将无法删除
所以通过重写equals方法进行比较引用类型内容和地址，进行删除

LinkedList集合

特点: LinkedList类是List接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括null）。
线程不安全（适用在对元素插入和删除操作，不适合遍历和查找）

存储方式: 双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环）

存储特点: 相对有序存储，可以存储相同元素（不排重），可以通过下标访问集合元素，通过链表实现的集合

ArrayList和LinkedList的总结

ArrayList存储结构是数组,LinkedList存储结构是双向链表。
ArrayList集合适用在对元素查询、遍历操作，不适合插入和删除。
LinkedList集合适用在对元素插入和删除操作，不适合遍历和查找。

Vector(了解)

特点：同步集合，线程安全，但是效率比较低

存储方式：数组 Vector类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。
但是Vector的大小可以根据需要增大或缩小，以适应创建 Vector后进行添加或移除项的操作。

Stack（栈）了解

特点：采用栈的存储方式（先进后出），是Vector的子类

Queue(队列)了解

于模拟队列这种数据结构，队列通常是指“先进先出”（FIFO）的容器。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。
通常，队列不允许随机访问队列中的元素。

ArrayList与LinkedList，Vector三种实现类存储的比较

a.功能基本相同
b.底层存储结构：ArrayList是数组，LinkedList是链表，Vector是数组
c.Vector是一个古老的集合，从JDK1.0开始就有了，Vector存在一些方法名比较长的方法，xxxElement
d.Vector是线程安全的，效率低，ArrayList是线程不安全的，效率高，推荐使用ArrayList【Collections工具类中有相应的方法可以将ArrayList改为线程安全的】
e.ArrayList查找遍历比较快，LinkedList插入删除比较快

set集合

特性:

无序存储，不可以存储相同的元素，不能通过下标访问遍历:

通过增强for

或使用迭代器Iterator

HashSet集合

特性:

此类实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

Hash:

哈希——实际含义散列,就是一种算法，把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。

存储结构：

哈希表:数组+链表,既有数组的优点也有链表的优点。（jdk1.7之前数组+链表，jdk1.8 数组+链表+红黑树）

基于 HashMap 实现的，底层采用 HashMap 来保存元素

存储特点：

相对无序存储，不可以存储相同元素（排重），通过哈希表实现的集合

重写hashCode() (可以实现排重效果)

hashCode()是Object中的方法，每个对象的hashCode值是唯一的，所以可以理解成hashCode值表示这个对象在内存中的位置

HashSet集合排重时，需要判断两个对象是否相同，对象相同的判断可以通过hashCode值判断，所以需要重写hashCode()方法

重写equals()(重点)

equals()方法是Object类中的方法，表示比较两个对象是否相等，若不重写相当于比较对象的地址

所以我们可以尝试重写equals方法，检查是否排重

HashSet的重复依据:hashCode和equals需要同时重写hashCode和equals方法，实现排重。

LinkedHashSet集合

LinkedHashSet类是具有可预知迭代顺序(相对有序)的Set接口的哈希表和链接列表实现。是HashSet的子类。

存储特点:

有序存储，不可以存储相同元素（排重），通过链表实现的集合的有序。

TreeSet集合(重要)

TreeSet集合是可以给元素进行重新排序的一个Set接口的实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的

存储特点：

无序存储，排重，通过红黑树实现的集合，可以给元素进行重新排序

SortedSet接口

TreeSet除了实现了Set接口外，还实现了SortedSet接口
它的方法查API吧

TreeSet集合的元素排序

元素所属的类需要实现java.lang.Comparable接口，并重写compareTo方法。
compareTo方法除了可以进行排序外，还有排重的功能，但是必须在compareTo方法中对类中所有的属性值都进行判断，否则不比较那个属性，排重就会忽略哪个属性

演示代码:

@Override
public int compareTo(Student o) {
    int n1=this.name.compareTo(o.name);
    int n2=this.age-o.age;
    return n1==0?n2:n1;
}

或者定制排序，元素需要通过java.util.Comparator接口（比较器）中的compare方法进行比较大小，并排序。

compare方法除了可以进行排序外，还有排重的功能，但是必须在compare方法中对类中所有的属性值都进行判断，否则不比较那个属性，排重就会忽略哪个属性

TreeSet集合中的无参数构造方法默认使用自然排序的方式对元素进行排序，使用TreeSet集合的定制排序时，创建集合对象不可以直接使用无参数构造方法，需要使用传入一个Comparator比较器的构造方法创建集合对象。

演示代码:

TreeSet<String> treeSet=new TreeSet<String>(new Comparator<String>() {
@Override
public int compare(Student o1, Student o2) {
    int n1=o1.getAge()-o2.getAge();
    int n2=o1.getName().compareTo(o2.getName());
    return n1==0?n2:n1;
}
}

Map集合

Map接口是将键映射到值的对象。一个映射不能包含重复的键，每个键最多只能映射到一个值，值可以重复。

特点：
（1）存储的数据是键值对（2）键不能重复
（3）一个键对应一个值，值可以重复
（4）无序的

循环遍历Map集合
（1）通过KeySet()方法得出key值，map.get(key)得出value值
（2）调用Map集合的entrySet方法，相当于将Map集合转成一个Set集合，再通过Set集合的遍历方式遍历即可。需要添加泛型Set<Entry<String,String>>，使用它调用getkey()和getValue()。

演示代码:

//将map转成一个Set集合
Set<Map.Entry<String, Integer>> set = map.entrySet();
//遍历set
Iterator<Map.Entry<String, Integer>> it=set.iterator();
while(it.hasNext()) {
  System.out.println(it.next());
}

HashMap集合

基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序。

存储特点:
相对无序存储，元素以键值对形式存在，键不可以重复，值可以重复，但会覆盖之前的数据，元素整体排重，可以快速的通过键查找到所对应的值，通过哈希表实现的集合,线程不安全

排重
HashMap集合的排重，只需要重写键所属的类的hashCode和equals方法即可。

存储方式:
哈希表（数组+链表/红黑树）
默认初始容量16和默认加载因子0.75的空HashMap,如果小于等于6时，自动转化为链表。
JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时,并且输入长度大于等于64时，将链表转化为红黑树，以减少搜索时间
JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）

LinkedHashMap

LinkedHashMap集合是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。
此实现与HashSet的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。
用法与HashSet类似。

存储特点：
有序存储，元素排重，通过链表实现的集合。

LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。
另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。
同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

Hashtable集合

此类实现一个哈希表，该哈希表将键映射到相应的值。任何非null对象都可以用作键或值。
Hashtable有一个子类Properties，Properties集合使用的比较频繁。

存储特点：
相对无序存储，元素排重，通过哈希表实现的集合。
数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

特性:
线程安全的，但是效率非常低下。
不允许存储null键和值。

HashMap与Hashtable的区别

Hashtable线程安全的，而HashMap线程不安全的
Hashtable中不允许存在null的键和null值，但是HashMap中允许null的键和null值

TreeMap集合

特点：
存储键值对、键不能重复、一个键对应一个值、值可以重复
无序，数据会进行排序。
自平衡二叉红黑树
排重依据：Comparable接口的compareTo()方法的返回值。如果返回0就认为是重复的元素。

定制排序(可以参考set集合的文章)

要实现Comparable接口
定制比较器 Comparator

ConcurrentHashMap集合

特性：
jdk1.7采用分段的数组+链表，jdk1.8采用数组+链表/红黑二叉树
实现线程安全的访问，性能和吞吐量远远高于HashTable
HashTable里使用的是synchronized关键字，这其实是对对象加锁，锁住的都是对象整体，当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。
ConcurrentHashMap算是对上述问题的优化.

Conllections工具类