Java集合大致可分为Set、List、 Queue和Map四种体系,其中Set代表无序、不可重复的集合; List代表有序、重复的集合;而Map则代表具有映射关系的集合,Java 5又增加了Queue体系集合,代表一种队列集合实现。集合类主要负责保存、盛装其他数据,因此集合类也被称为容器类。所有的集合类都位于
java.util包下,后来为了处理多线程环境下的并发安全问题,Java 5还在java utilconcurrent包下提供了一些多线程支持的集合类。
Collection是一个接口,Map没有继承Collection。
Set和Map很相似,Set底层是Map实现的。Map和List的实现比较重要
HashSet是Set接口的典型实现,HashSet不能 保证元素的排列顺序,它是非线程安全的,并且集合内元素的值可以是null。HashSet底层 是由HashMap实现的,它将元素存到了HashMap的key上,而对应的value则是一个空对象。
底层数据怎么存的?
有序和无序怎么保证的?
扩容机制?
//transient,该属性不需要序列化,因为只把数据存在了map的k上,即v为空,浪费空间 private transient HashMap<E,Object> map; //底层存数据 //map中的v存固定的PRESENT,而不是null,起到判断比较的作用,null无法比较,常量可以 private static final Object PRESENT = new Object(); //构造器,初始化map public HashSet() { map = new HashMap<>(); } //添加数据的方法 public boolean add(E e) { return map.put(e, PRESENT)==null; } //移除 public boolean remove(Object o) { return map.remove(o)==PRESENT; } //迭代方法 public Iterator<E> iterator() { return map.keySet().iterator(); } //重写序列化方法,只序列化key for (E e : map.keySet()) s.writeObject(e);
TreeSet可以确保集合元素处于排序状态(按照数据的值排序,可以自定义排序规则),TreeSet支持 自然排序和定制排序两种排序方式,它的底层是由TreeMap实现的。TreeSet也是非线程安全的,但是它内部元素的值不能为null(要排序,null没法比较)。
private transient NavigableMap<E,Object> m; //底层实现 public TreeSet() { this(new TreeMap<E,Object>()); } //添加和移除,iterator,序列化和上面的HashSet一样
ArrayList是基于数组实现的List,所以ArrayList封装 了一个动态的、允许再分配的Object数组。
ArrayList对象使用initialCapacity参数来设置该数组的长度,当 向ArrayList中添加元素超出了该数组的长度时,它的initialCapacity会 自动增加,即ArrayList会自动扩 容。若需要对ArrayList缩容,则需要主动调用trimToSize()。会主动扩容但不会主动缩容
源码解读:
定义和初始化:
/** * Default initial capacity.首次初始化数组,默认长度为10 */ private static final int DEFAULT_CAPACITY = 10; //两个空的数组,区分创建集合的时候是默认长度还是指定长度,两者方式再扩容机制上不一样 private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //数组中存储的具体元素 transient Object[] elementData; //实际存放的数组长度 private int size; /** * Constructs an empty list with an initial capacity of ten.创建一一个默认的容量为10的数组 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //初始化数组 public ArrayList(int initialCapacity) { //如果指定容量大于0,创建一个指定容量的数组 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//等于0,创建一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else {//小于0报错 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
扩容机制(当数组追加到一定范围,即添加数据时)
默认长度为10,每次在上一次的容量基础上,扩展1.5倍。每次扩容其实是将原数组的数据拷贝到创建的新数组里面
public boolean add(E e) { //先扩容 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;//追加数据 return true; } //怎么扩容的呢?算好一个容量,算好之后穿过来 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //怎么计算的容量? private static int calculateCapacity(Object[] elementData, int minCapacity) { //数组是默认构造器创建时 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //在默认容量和最小容量取最大值 return Math.max(DEFAULT_CAPACITY, minCapacity); } //当你使用的是有参构造器,直接返回你指定的容量 return minCapacity; } //以上总体来说就是要不要考虑默认容量 //算好容量之后,开始扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code先判断一下要扩容的容量是否大于数组的长度 if (minCapacity - elementData.length > 0) grow(minCapacity); } //grow扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;//获取数组旧的容量 //新的容量=老的容量+老的容量的一半(1.5倍) int newCapacity = oldCapacity + (oldCapacity >> 1); //超过int容量的最小值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //超过int容量的最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win:每次扩容其实是将原数组的数据拷贝到创建的新数组里面 elementData = Arrays.copyOf(elementData, newCapacity); } //数组容量溢出处理 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
List迭代
//两个迭代器 //因为继承关系具有的迭代器 public Iterator<E> iterator() { return new Itr(); } //list自己加的迭代器 public ListIterator<E> listIterator() { return new ListItr(0); } private class Itr implements Iterator<E> { int cursor; //当前游标 int lastRet = -1; //上一次迭代的位置(当前位置的前面??不一定) int expectedModCount = modCount;//期望得修改次数,在迭代的过程中,判断次数相等,不相等说明在迭代的过程中,你修改了(即判断在迭代的过程中,能不能修改数据) //在迭代的过程中,删除数据时要先判断一下修改次数 }
自己的itertor实现排序,增加ListIterator是为了增加迭代的顺序,实现可以从前往后,从后向前,从中间迭代
//是itertor的子类,在其基础上扩展了一些东西 private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { //指定位置开始迭代 super(); cursor = index; } public E previous() {//向前迭代, checkForComodification();//先检查修改次数,继承的 int i = cursor - 1; } //要覆盖某个值也要检查修改次数 ArrayList.this.set(lastRet, e);//把刚刚访问的元素覆盖掉 //添加 public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e);//将元素 } }
缩容:
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
总结:
1、数组实现,默认长度为10,每次扩容1.5倍。每次扩容其实是将原数组的数据拷贝到创建的新数组里面。
2、在迭代的过程中检查修改次数,如果数据被改,就不能迭代下去。
3、支持ListIterator,可以更灵活的进行迭代。
LinkedList是基于双向链表实现的List,它内部的元素可以为nul、可以重复,LinkedList是非线程 安全的。
源码解读:
定义和结构:
transient int size = 0;//连表里有多少个节点 transient Node<E> first; transient Node<E> last; //Node节点有前驱和后继,所以是双向链表 private static class Node<E> { E item; Node<E> next; Node<E> prev; }
添加数据:
public boolean add(E e) { linkLast(e); //到链表末尾 return true; } //指定位置的添加 public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
获取数据:
public E get(int index) { checkElementIndex(index); return node(index).item; }
设置值
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }
删除:
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
node方法根据节点获取索引
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; } }
Queue用于模拟队列,它是一种先进先出 (FIFO) 的容器。
常用方法offer,poll
Deque代表双端队列,它允许你从两端来操作队列中的元素,并支持入栈及出栈操作。Deque在Queue的基础上,增加了如下两类方法:
选择一端进行操作
ArrayDeque底层通过数组实现,为了满足可以同时在数组两端插入或删除元素的需求,该数组还必须是循环的,即循环数组,也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是 非线程安全的,另外该容器不允许放入null元素。
双端队列基于数组实现,
源码解读:
transient Object[] elements;//由数组实现,数据放数组里 transient int head;//头部索引 transient int tail;//尾部索引 //默认最小容量 private static final int MIN_INITIAL_CAPACITY = 8; //构造器,默认初始化长度为16 public ArrayDeque() { elements = new Object[16]; } //指定数组大小时,并不是按照你指定多少就是多少,他要计算一下 private void allocateElements(int numElements) { elements = new Object[calculateSize(numElements)]; } //计算容量(你指定的时候他要扩展为比你指定大的最近的,2的n次方) private static int calculateSize(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. if (numElements >= initialCapacity) {//大于等于最小长度 initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } return initialCapacity; }
ArrayDeuqe的容量一定是2的n次方
入队:
public boolean offer(E e) { return offerLast(e); } public boolean offerLast(E e) { addLast(e); return true; } //往头部增加数据 public void addFirst(E e) { if (e == null) throw new NullPointerException(); //先算头指针下标 elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity();//扩容 }
扩容:
private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length;//数组的长度 //头指针右侧的元素数量 int r = n - p; // number of elements to the right of p //新的容量是原来的2倍 int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); //数组拷贝,先拷贝头指针右侧的数据,再拷贝头指针左侧的数据 Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = a; head = 0; tail = n; }
出队:
public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; // Element is null if deque empty if (result == null) return null; //删除头指针 elements[h] = null; // Must null out slot //头指针移位 head = (h + 1) & (elements.length - 1); return result; } public E pollLast() { //尾节点 int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") E result = (E) elements[t]; if (result == null) return null; elements[t] = null; tail = t;//尾指针左移 return result; }
双端队列当作栈来用
public void push(E e) { addFirst(e);//上面讲过了 } public E pop() { return removeFirst();//一个方向来进和出就是栈 }
除了实现List接口之外,LinkedList还实现 了Deque接口,可以被当成双端队列来使用,因此既可以被当成“栈"来使用,也可以当成队列使用。
源码解读:
public boolean add(E e) { linkLast(e); return true; } //入队:添加到前面去, private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } //出队 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //解除节点的双向关系 private E unlinkFirst(Node<E> f) { 。。。 }
栈的方法:
public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }