Java集合
Collection
继承关系
所有:统称集合
然后大类分为:
- List,列表:ArrayList,LinkedList,Vector(很少用了)...
- Set,集:HashSet,LinkedHashSet,TreeSet...
- Queue,队列:PriorityQueue,ArrayBlockingQueue...
List是有序的,ArrayList,Linked都有序,只是内部实现不一样。
ArrayList基于数组实现,LinkedList基于链表实现。
常用的集合类关系图
先了解一下什么是数组?
数组是一段连续的内存空间,需要指定长度,一旦分配,不可以动态改变大小。
List
ArrayList
ArrayList就是基于数组结构的,但是我们平时使用的时候,ArrayList是动态添加的,自动扩展长度的。
它内部是如何做的呢?
- 创建
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
数据对象赋值为
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- 添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
这个ensureCapacityInternal往下走的代码主要是这个
elementData = Arrays.copyOf(elementData, newCapacity);
也就是copy数组,copy数组是会新创建数组的。
- 删除元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
所以ArrayList的增删效率是相对比较低的,但是查询速度快,因为基于数组实现的。
LinkedList
LinkedList是基于双链表数据结构实现的
什么是双链表呢?
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
链表结构特点时,增删快,查询慢。
我们添加数据或者删除数据时,只要对节点里的next/pre进行指向修改即可。
所以LinkedList的特点就有了,增删快,查询慢。
List总结
List-有序,内容可以重复
数组实现的特点:查询快,增删慢
双链表实现的特点:查询慢,增删快
Set
什么是set?
它和List一样,都是继承自Collection接口
常用的有HashSet,TreeSet,LinkedSet
- HashSet
哈希表实现,无须,内容唯一。
如何确保唯一呢?通过hashCode和equals
- TreeSet
基于红黑树结构实现,唯一,有序
如何保证有序-->自然排序/比较器
如何保证唯一性?
根据比较值,返回值来决定
- LinkedHashSet
前面我们说了HashSet无序,唯一
那怎么确保唯一,又有序呢?
就有这个LinkedHashSet了
通过链表保证数据有序
通过Hash表确保数据唯一
Map
Map是单独的接口,Map则为映射,也就是Key->Value的关系
常用的Map类关系图
TreeMap
- 基于红黑树实现的Map集合
- 有序
- 线程不安全
HashMap
- 基于Hash表实现
- 线程不安全
- 无序
LinkedHashMap
- 基于链表和哈希表实现
- 有序
- 线程不安全
HashTable
- 基于哈希表实现
- 线程安全
- 无序
总结
- 是否有序,这里指的是添加的顺序
Linked ,Array,Tree有序
Hash无序
- 是否线程安全
HashTable, Vector线程安全
ArrayList,LinkedList,HashSet,TreeSet,LinkedHashSet,ArraySet线程不安全
- 效率
效率是相对来说的
查询:索引的比没索引要遍历的效率高 线程安全:线程不安全的比线程安全的效率高 增删:无索引的比有索引的增删快
- 是否可以存Null值
其实这个意义不在,只是说面试要问。
可以存null值:HashMap,HashSet,LinkHashSet,HashSet,ArrayList,LinkedList
不可以存null值:HashTable,TreeSet
- 是否去重
Hash和Tree会去重,也就是确保唯一
链表和数组实现的不会去重
如果说要有序,又去重可以结合起来实现。
除此以外,还要掌握遍历,自定义Bean的比较的两种实现方式。
有这些知识,基本上够用了。
如果想知道原理,就要学习数据结构。
以上提到的,比如说哈希表,双链表结构,红黑树,数组也是一咱数据结构,这个就不用说了,自古以来大家都知道数组的。