[数据结构与算法]集合框架Collection和Map总结Collections工具类

集合框架

集合:是广义上的集合,简单理解就是容器.注意:集合只能存放对象类型的数据.

集合框架指的是java.util包中定义的各种容器类、相关的工具类、接口的统称。不同的容器存储不同结构的数据。使用时要进行导包操作。

Iterable接口

Iterable英文含义是可迭代的，即可遍历的。

Iterable接口是Collection接口的父接口。

Iterable接口中规定了实现类必须要提供迭代器对象，在Java中使用迭代器去遍历集合中的元素。

Collection接口

Collection是其他单值集合接口的父接口，它规定了单值容器应该具有哪些功能。

List接口

规定了有序集合应该具有什么功能。有序不是内容有序，而是存放顺序有序。既然有序，意味着有下标的概念。

List接口除了包含父接口中全部的抽象方法之外，还声明了很多和下标(index)有关的方法。

ArrayList继承于AbstractList(抽象类)

AbstractList(抽象类)实现了List接口

List接口extends Collection接口

Collection接口定义了容器应该有哪些功能(查看元素,添加元素,删除元素,清空元素,获取迭代器).Collection接口继承了Iteratable接口,所以可以用forEach循环

List在Collection基础上,增加了和index相关的方法,添加到某个位置,获取某个位置的元素

ArrayList他实现了List接口意味着他也实现了Collection接口,那么这些接口中的方法

在实际开发过程中,List仅仅作为容器存在,用它来存数据,另外可以通过下标取数据.

如果要在遍历的过程中删除元素,使用迭代器遍历,同时使用迭代器删除元素.

Set集合.代表数学中的集合

特点:1.去重;2.无序(没有下标的概念)

Set本身没有什么独特的方法,所有的方法都与Collection接口中的方法相同.

Set的实现类.—HashSet

hashSet的初始容量是16,负载因子是0.75(当当前因子达到初始容量的75%),开始双倍扩容到32–>64…

如果需要获取里面的元素:1.使用List,不使用Set;2.或者把Set转换为List.

List<String> list = new ArrayList<>(set);

Set不能用For循环进行遍历.因为没有下标获取元素的方法;可以使用增强for循环,找到对象,输出;也可以使用迭代器.

set和list是可以互相转换的---->利用各自的构造方法.

Set的去重机制,先判断hashCode是否相等,如果相同,再判断equals方法.两者都相等会被去重.否则其中只要一个不相等,两个对象都是不相等的.

LinkedHashSet

他有和HashSet的相同功能.LinkedHashSet会维持元素加入的顺序.双向链表.LinkedHashSet继承于HashSet,父类中的所有方法,子类都继承.只不过子类重写了父类的方法.为什么要重写?因为父类方法无法维持添加的顺序,所以子类重新实现了继承来的方法.也可以去重.因为String和Integer这两种类已经重写了HashCode和equals方法,所以不需要重写,但是如果自己写的类,需要重写这两种方法.比如自己写的类Person类,创建对象的时候,去重,就必须重写HashCode和equals方法.

如果你想让添加顺序保持不变,可以用LinkedHashSet方法.

TreeSet实现类

TreeSet内容有序的集合,即它会对放入其中的数据按内容进行排序,它底层数据结构是二叉树.

TreeSet可以对数据进行排序，但排序规则由你来定！

TreeSet支持2种排序：自然排序、比较器排序。

自然排序：被放入TreeSet的数据，必须实现Comparable接口。Comparable接口中只有一个方法 int compareTo(T t) ，即被放入TreeSet中的对象要实现compareTo方法，TreeSet每放入一个元素，就会拿这个元素和已有元素比较（用compareTo方法比较），最终确定新添加的数据的位置，使TreeSet集合所有元素有序。

比较器排序：这种排序方式更加灵活，不要求容器中的元素实现Comparable接口。而是通过一个实现了Comparator接口的类来对TreeSet中的元素进行比较，TreeSet根据比较的结果进行排序。Comparator实现类必须要实现int compare(T t1, T t2)方法。TreeSet中每放入一个元素，就会借助比较器比较新加入的元素和已有元素的大小关系，最终确定新添加的数据的位置，使TreeSet集合所有元素有序。

创建一个空的TreeSet对象是按照自然排序的.TreeSet之所以可以对String进行排序,因为String这个类和Integer实现类实现了Comparable接口.Comparable接口里面只有一个方法public int CompareTo(Object o);TreeSet底层逻辑是二叉树,把元素存成一个树形结构(在存的时候就会去重),去重的依据不是equals而是CompareTo比较的结果是0就去重.要求:元素要实现Comparable接口,实现接口中的ComparaTo方法,如果这个方法返回值是0,就认为重复了,如果不为0,会把元素添加二叉树指定的位置(进行中序遍历).

比较器排序:在创建TreeSet的时候就指定一个比较器对象(实现了Comparator接口的对象,通常使用匿名类),实现Comparator接口中的Compare方法

相比与自然顺序排序比较器更优:1.我们可以给同一波数据指定不同的排序方式,只需要给出不同的比较器对象即可;2.保证类的干净,如果有些类不是自己写的或者是系统类,如果要对这样的对象进行比较,可以用比较器Comparator;

Map集合

HashMap：是最普通的Map实现类，键值对的顺序是无序的。

LinkedHashMap：键值对的顺序和存入时的顺序一致。

TreeMap：key的内容有序的键值对集合。

Hashtable不是Map的实现类，但是和Map一样，它也是键值对容器，用法和HashMap一样，主要的区

别是：

1. Hashtable在多线程访问时，是安全的。HashMap是不安全的

2. Hashtable继承于Dictionary，HashMap继承于AbstractMap

3. Hashtable键和值都不能为null，HashMap的键和值都可以为null，但只能有一个key为null

//获取map中所有的value用Collection去接收
Collection values = map.values();
//但是Collection可以转换成list
List ls = new ArrayList(values);
//获取map中的所有的键值对 Map.Entry

//map的遍历---找到map的每个键和每个值
//1.通过key遍历,找的value

//2.通过键值对进行循环Map.entry

//3.分别获取所有的key和所有的value

//value可以是任意类型的,
//key是否为任意类型--->大多数情况下key都是String类型的,如果是其他情况其他的数据类型map要求key是唯一的,自定义类型不一定会保证唯一性,原理和set中添加自定义类型是一样的,必须在自定义类型中添加hashCode和equals方法.如果想要自定义方法作为key,需要重写hashCode和equals方法.

总结:Map是存放键值对的容器.

添加元素 put

修改元素put replace

删除元素 remove

获取元素 get

获取所有的key keySet()

获取所有的value Collection values()

获取所有的键值对 entrySet()

LinkedHashMap实现类

//创建一个空的map,初始容量是16,加载因子是0.75,有一个可以预测的顺序(迭代顺序即添加顺序)
Map<> map = new LinkedHashMap();


Map<> map2 = new LinkedHashMap(16, 0.75f, false);
//如果参数为true是访问顺序,如果是false跟访问顺序没有关系,依旧是添加的顺序.看map2.get(*)访问顺序是没有意义的,看的是它的添加顺序.true是你get元素的顺序,false是你put元素的顺序

TreeMap实现类.

//TreeMap是key有序的键值对容器--->不是添加顺序,而是比较key的大小.
//创建一个空的map,使用自然顺序排序.
//自然顺序排序:key所属的类要实现	Comparable接口 --->实现接口中的comparaTo方法.
Map<> map = new TreeMap();
//TreeMap有什么用?--->做通讯录的时候,key是String分组的名称A ,B C, D ...
Map<String,List<Person>> map = new TreeMap();

哈希表

散列表

数组(查询快)和链表(增删快)的结合体—>哈希表

Collections工具类

和Arrays类似,是一个工具类.

Collections是集合框架(List,Set,Map)的工具类,提供了很多操作集合框架的方法.

//
List<String> list = new ArrayList<>();
List<String> list2 = Arrays.asList("aaa", "bbb", "ccc", "ddd", "fff");
Collections.addAll(list,"aaa", "bbb", "ccc", "ddd", "fff");
Collections.binarySearch(list,"aaa");//二分查找需要内容有序
Collections.copy(list2, list);//拷贝
Collections.disjoint(list, list2);//两个数组之间是否有交集
Collections.fill(list2,"haha");//填充
Collections.frequency(list,"aaa");//某有个元素出现了多少次
Collections.max(list);//找最大值
Collections.replaceAll(list, "aaa", "bbb");//替换,把list中的aaa都替换成bbb
Collections.rotate(list, 1);//后移出来的在放到前面
Collections.shuffle(list);//打乱顺序
Collections.swap(list, 0 , 2);//交换元素