Java-Collection-集合详解
- 集合体系图
- Set集合
-
- 1.set集合的特点
- 2.set集合的唯一性如何保证
- 3.set集合实现类分析
-
- 3.1 HashSet
- 3.2 TreeSet
- List集合
-
- 1.List集合的特点
- 2.List的实现类分析
-
- 2.1 ArrayList
- 2.2 LinkedList
- 总结
-
- Vector和ArrayList
- Arraylist和Linkedlist
集合体系图
Set集合
1.set集合的特点
Set集合特点是无序唯一
2.set集合的唯一性如何保证
对象引用相等性与对象相等性参考：java对象相等判断
Set集合就是对比对象的相等性来保证元素的唯一性，但hashCode相等的时候并不一定保证元素唯一，还有对比equal方法是否相等，只有hashCode和equal同时相等，才认为是相同元素，Set集合只会保存其中一个元素。
Set集合两种存储形态：
A:hashCode相同 而equal不相同的情况 此时认为元素只是在相同的哈希桶内
B:hashCode不同
ArrayList和HashSet都有判断元素是否已经存在的方法：
contains();
ArrayList只是用了equal方法判断
HashSet使用了 hashCode和equals
3.set集合实现类分析
| 类型 | 实现使用map对象 | 数据结构 |
|---|---|---|
| HashSet | HashSet | 散列表(拉链法) |
| LinkedHashSet | LinkedHashSet | 双向链表+散列表(拉链法) |
3.1 HashSet
HashSet底层是以hash表实现，线程不安全，效率高，存取速度快。
3.2 TreeSet
红-黑树的数据结构，默认对元素进行自然排序（String）。如果在比较的时候两个对象返回值为0，那么元素重复。
TreeSet默认排序方式为自然排序，既然有排序方式，肯定可以指定排序规则，下面有两种方式可以指定TreeSet的排序规则
1： 元素自身具有排序规则
元素自身具备比较性，需要元素实现Comparable接口，重写compareTo方法，也就是让元素自身具备比较性，这种方式叫做元素的自然排序也叫做默认排序。
例如Set里面存储String类型的数据，String类本身实现了Comparable
public final class String implements java.io.Serializable, Comparable, CharSequence
所以即使不指定，元素根据本身自带排序规则也可以进行排序。
2：容器具备比较性
当元素不具备比较性，或者比较性不是实际所需要的时候，那么此时可以让容器自身具备。需要定义一个类实现接口Comparator，重写compare方法，并将该接口的子类实例对象作为参数传递给TreeMap集合的构造方法。
比如：TreeSet ts = new TreeSet(new MyComparator()); 来指定自定义比较器。
class MyComparator implements Comparator {
public int compare(Object o1, Object o2) {
Book b1 = (Book) o1;
Book b2 = (Book) o2;
System.out.println(b1+" comparator "+b2);
if (b1.getPrice() > b2.getPrice()) {
return 1;
}
if (b1.getPrice() < b2.getPrice()) {
return -1;
}
return b1.getName().compareTo(b2.getName());
}
注意：当Comparable比较方式和Comparator比较方式同时存在时，以Comparator的比较方式为主；
----| Comparable
compareTo(Object o) 元素自身具备比较性
----| Comparator
compare( Object o1, Object o2 ) 给容器传入比较器
注意：在重写compareTo或者compare方法时，必须要明确比较的主要条件相等时要比较次要条件。（假设姓名和年龄一直的人为相同的人，如果想要对人按照年龄的大小来排序，如果年龄相同的人，需要如何处理？不能直接return 0，因为可能姓名不同（年龄相同姓名不同的人是不同的人）。此时就需要进行次要条件判断（需要判断姓名），只有姓名和年龄同时相等的才可以返回0.）通过return 0来判断唯一性。
List集合
1.List集合的特点
List集合底层是以数组为数据结构，元素保持有序、可重复。
2.List的实现类分析
2.1 ArrayList
ArrayList关注索引，因此也提供了一系列索引的操作方法，数组使用索引可以很快的进行查询，但是如果进行插入和删除元素，会花销元素的移位操作，因此List查询快，删除和插入比较慢。
ArrayList底层为数组，数组就要指定长度，初始化时，如果不指定长度，ArrayList默认给一个10的长度
随着元素的插入，容量不足够容纳时，ArrayList会根据元素的长度计算，来判断扩容多少，具体分为两种情况：
- 插入元素的总容量小于默认容量
只添加一个元素，例如：原来数组的capacity为10，size已经为10，不能再添加了。需要扩容，新的capacity=old capacity+old capacity>>1=10+10/2=15.即新的容量为15。 - 插入元素的总容量大于默认容量
当同时添加多个元素时，原来数组的capacity为10，size为10，当同时添加6个元素时。它需要的min capacity为16，而按照capacity=old capacity+old capacity>>1=10+10/2=15。new capacity小于min capacity，则取min capacity。
参考源码：
2.2 LinkedList
LinkedList底层是以双向链表为数据结构的集合，按插入顺序排序存储元素，集合无序，并且不提供sort方法对元素进行排序。LinkedList的数据结构如下图：
next：对下个元素的引用
prev：对上个元素的引用
first： 指向第一个元素
last：指向最后一个元素
链表的数据结构特点是：增删元素复杂度仅为O(1)，而查询元素相对较慢。
增加元素
public boolean add(E e) {
linkLast(e);//将元素作为最后一个元素插入
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
移除元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);//改变元素指向，并将元素置null，移除元素
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
获取元素
获取元素类似二分法，根据索引获取，判断索引是否小于size/2 如果小于 从first开始遍历，反之从last遍历
public E get(int index) {
checkElementIndex(index);
return node(index).item;//node方法索引元素
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
总结
Vector和ArrayList
1，vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。
2，如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%，而arraylist增长率为目前数组长度的50%。如果在集合中使用数据量比较大的数据，用vector有一定的优势。
3，如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，如果频繁的访问数据，这个时候使用vector和arraylist都可以。而如果移动一个指定位置会导致后面的元素都发生移动，这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据时其它元素不移动。
ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以索引数据快，插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快。
Arraylist和Linkedlist
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。