关于java:集合一从这里开始ListSet

Collection汇合体系

Collection 是一个汇合接口，

它提供了对汇合对象进行基本操作的通用接口办法，

所有汇合都是它的子类，比方 List、Set 等。
 
Collections 是一个包装类，

蕴含了很多静态方法，不能被实例化，就像一个工具类，

比方提供的排序办法： Collections. sort(list)。
 
Collections.sort排序外部原理 

Collections.sort排序通过泛化实现对所有类型的排序。

对于根本数据类型依照字符表，数字大小排序；

对于自定义类型，通过Comparable接口，重写compareTo()自定义比拟大小的形式。
 
Collections.sort外部调用的是Arrays.sort()

对于Arrays类有两种sort办法，sort(Object)应用归并排序，sort(int)应用疾速排序。

jdk1.6中应用MergeSort

jdk1.7中应用TimSort=MergeSort + insertionSort

TimSort介绍

由Tim Peters于2002年应用在Python编程语言中。

该算法用于查找曾经排序的数据的子序列，并应用该常识更无效地对其余部分进行排序。

这是通过将已辨认的子序列（称为运行）与现有运行合并直到满足某些条件来实现的。

从版本2.3开始，Timsort始终是Python的规范排序算法。

现在，Timsort 已是是 Python、 Java、 Android平台和 GNU Octave 的默认排序算法。

List

List是有序可反复的

有三个实现类： ArrayList、LinkedList和Vector。

线性形式存储，索引形式拜访，存取程序统一。

1、ArrayList(数组)

继承自AbstractList

底层采纳可变数组存储元素，反对索引，因而适宜查问和遍历。

非线程平安，线程不同步，单线程拜访汇合

<div>毛病：每个元素之间不能有距离，列表的结尾会预留肯定的容量空间，当数组大小不满足(增删操作)时，就要将曾经有数组的数据复制、挪动到新的存储空间，代价较高，因而，不适宜增删</div>

有初始容量大小，ArrayList扩容增长原来的0.5倍

2、LinkedList(链表)

继承自AbstractSquentialList

为了克服ArrayList不适宜增删，LinkedList底层采纳双向链表构造存储数据的，

每个元素通过援用相连，使得增删高效。(Jdk1.6循环链表；1.7双向链表)

还提供了List接口中没有定义的办法，专门用于操作表头和表尾元素，

能够当作堆栈、队列和双向队列应用。

因为底层是用双向链表实现的，没有初始化大小，也没有扩容的机制。

LinkedList空间节约，在每一个元素都要耗费比ArrayList更多的空间，用来寄存节点

双向链表：蕴含两个指针，一个prev指向前一个节点，一个next指向后一个节点

双向循环链表：最初一个节点的next指向head，head的prev指向最初一个节点，形成一个环。

3、Vector(数组)

Vector与ArrayList一样，也是通过数组实现的，

不同的是它反对线程的同步，即某一时刻只有一个线程可能写 Vector，

防止多线程同时写而引起的不一致性，但实现同步须要很高的破费，

因而，拜访它比拜访ArrayList慢。

增容时，增至原来的1倍

Set

该体系汇合用于存储无序(存入和取出的程序不肯定雷同)元素，值不能反复。

对象的相等性实质是对象hashCode值（java是根据对象的内存地址计算出的此序号）判断的，

如果想要让两个不同的对象视为相等的，就必须笼罩Object的hashCode办法和equals方法。 

1、HashSet

HashSet实现原理：

HashSet是基于HashMap实现的，底层应用HashMap保留所有元素，

HashSet源码非常少，相干的操作基本上都是间接调用底层HashMap的办法来实现。

哈希表寄存的是哈希值。

HashSet存储元素的程序并不是依照存入时的程序（和List显然不同）而是依照哈希值来存的所以取数据也是依照哈希值获得。

HashSet如何查看反复

元素的哈希值是通过元素的 hashcode办法来获取的,

HashSet首先判断两个元素的哈希值，如果哈希值一样，

接着会比拟 equals办法如果 equls后果为true ，HashSet就视为同一个元素。

如果equals 为false就不是同一个元素。 

哈希值雷同equals为false的元素是怎么存储呢

就是在同样的哈希值下顺延（能够认为哈希值相同的元素放在一个哈希桶中）。

也就是哈希一样的存一列。HashSet通过hashCode值来确定元素在内存中的地位。

一个hashCode地位上能够寄存多个元素。

2、LinkedHashSet(HashSet+LinkedHashMap)

对于 LinkedHashSet 而言，它继承自HashSet、又基于 LinkedHashMap 来实现的。

LinkedHashSet 底层应用 LinkedHashMap 来保留所有元素，它继承与 HashSet，其所有的办法操作上又与HashSet雷同。

因而LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的结构器，底层结构一个 LinkedHashMap来实现，在相干操作上与父类HashSet的操作雷同，间接调用父类HashSet的办法即可。

可实现有序插入

3、TreeSet(二叉树)

继承自SortedSet，适宜排序

存入元素时会与其余元素比拟，用Comparable接口中的CompareTo()办法，存入对象的类实现接口，调用办法。

也能够用Comparator接口中的compara()办法比拟字符串长度。

TreeSet()是应用二叉树的原理对新add()的对象依照指定的程序排序（升序、降序），每减少一个对象都会进行排序，将对象插入的二叉树指定的地位。

Integer和String对象都能够进行默认的TreeSet排序，而自定义类的对象是不能够的，本人定义的类必须实现Comparable接口，并且覆写相应的compareTo()函数，才能够失常应用。

在覆写compare()函数时，要返回相应的值能力使TreeSet依照肯定的规定来排序

比拟此对象与指定对象的程序。如果该对象小于、等于或大于指定对象，则别离返回负整数、零或正整数。

<div align='center' style=color:#808000> 如果文章对你有帮忙</div>
<div align='center' style=color:#808000> 记得点赞 + 分享</div>
<div align='center' style=color:#808000> 【微信搜寻JavaUps】</div>