今天学习一下集合包里面的内容,常见的有Collection和Map两个接口的实现类
Collection中常见的又分为两种:
1.List ,支持放入重复的对象,实现类有arraylist,linkedlist,vector,stack
2.Set ,不支持放入重复对象,hashset,treeset
ArrayList:
创建arraylist:提供了三种构造方式。
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity];//大于0时就直接创建object数组 } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA;//为0时构造一个空的 } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
当插入的数据大于它的容量时就会扩容,过程如下:
public static void main(String[] args) { List list = new ArrayList(2); list.add(1); list.add(2); list.add(3); }
上面定义了长度为2,但存放了三个,调用过程是这样的,在第三次时决断minCapacity-elementData.length>0就调用grow法。源码如下:
//添加 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); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 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); }
删除元素:
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; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; 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 }
遍历时:
public Iterator<E> iterator() { return new Itr(); } int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException();//这个异常说明在操作元素时,有其他线程对list进行了改变 } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
总结:
ArrayList基于数组方式实现,无容量限制,在插入元素时可能会扩容,在删除元素时,容量大小并不会改变,但可以通过trimToSize()来修改。在查找元素时要遍历数组,对于非null的元素,采取equals的方式查找,最后一点arrayList是非线程安全的。
LinkedList也是非线程安全的,它基于双向链表机制实现,插入元素时要新建一个Entry对象(1.8好像是Node,没骨找到Entry对象)。
Vector是基于Synchronized实现的线程安全的ArrayList,但在插入元素时容量扩充的机制和ArrayList稍有不同,并可通过capacityIncrement来控制容量的扩充。
Stack继承Vector,实现后进先出(LIFO)的弹出及压入操作,提供了push,pop,peek三个主要方法。
HashSet:
hashset是set接口的实现,set 和list区别就是set不允许有元素重复(不重复是底层用hashmap),
总结:
HashSet基于HashMap,无容量限制,HashSet是非线程安全的。