今天先看看有关集合的源码.
既然是看集合那就从集合的最根接口Collection接口看起;
本人使用的 IntelliJ IDEA,所以也免去的导入源码的过程,直接进入Collection接口开搞.
Collection接口的一些注释和实现结构
简单的读一下注释.大意如下:
这是一个集合层次的根节点,一个集合包含了一组对象,称为元素.一些集合允许复制,一些不允许,一些是有序的,一些是无须的,JDK不提供任何直接的对于此接口的实:提供了一些特殊的子接口像Set和List.
看Collection的实现,熟悉的有List,Set,Queue基本的,咱们一个一个来看.都不放过.
先看第一个:
SynchronizedCollection 看名字同步的集合,
进入SynchronizedCollection类内部,发现他是一个内部类,是在Collections类下的内部类
看一下java对这个类的描述
/**
* Returns a synchronized (thread-safe) collection backed by the specified
* collection. In order to guarantee serial access, it is critical that
* <strong>all</strong> access to the backing collection is accomplished
* through the returned collection.<p>
*
* It is imperative that the user manually synchronize on the returned
* collection when iterating over it:
* <pre>
* Collection c = Collections.synchronizedCollection(myCollection);
* ...
* synchronized (c) {
* Iterator i = c.iterator(); // Must be in the synchronized block
* while (i.hasNext())
* foo(i.next());
* }
* </pre>
* Failure to follow this advice may result in non-deterministic behavior.
*
* <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
* and <tt>equals</tt> operations through to the backing collection, but
* relies on <tt>Object</tt>'s equals and hashCode methods. This is
* necessary to preserve the contracts of these operations in the case
* that the backing collection is a set or a list.<p>
*
* The returned collection will be serializable if the specified collection
* is serializable.
返回一个由指定集合支持的同步的(线程安全)集合.为了保证连续的数据,重要的是，所有对后台集合的访问是通过返回的集合完成的
当遍历这个集合的时候,用户在返回的集合上手动同步是必要的.
基本上SynchronizedCollection这个类的作用是创建一个线程安全的集合.
我们可以看到一个参数为Collection返回值为Collection的静态方法synchronizedCollection
所以我们在程序中直接调用Collections类的synchronizedCollection方法来获取一个线程安全的集合
Collection collection= Collections.synchronizedCollection(new ArrayList<String>());
在Collections类中还可以看到其他类似的方法:
public static <T> Set<T> synchronizedSet(Set<T> s) {
return new SynchronizedSet<>(s);
}
获取一个线程安全的Set集合.
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
return new SynchronizedSortedSet<>(s);
}
获取一个线程安全的SortSet.
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
获取一个线程安全的List集合
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
获取一个线程安全的map等等.
哪为什么这些获取的就是线程安全的集合呢,我们来看一下他的方法:
我们可以看到,他在所有方法里都加了synchronized关键字,而对应的锁,如果我们在创建集合的时候没有传入锁对象,那么就是它本身,如果传入了锁对象就是这个对象.
下面重点研究一下List,Set,和Queue
一. List接口
接口中定义了一些操作集合的常用方法
下面看一下他的继承关系
可以看到有许多类或者接口实现了List接口
我们主要看一下几个:ArrayList,Vector,LinkedList
(1)ArrayList
进入ArrayList类中首先可以看到定义的一些常量和变量
DEFAULT_CAPACITY ArrayList默认容量为10;
EMPTY_ELEMENTDATA 在调用无参构造的时候默认给的空数组
elementData 真正保存数据的数组
size 就和中真正元素的个数
构造方法有三个
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
传入一个int数定义一个数组
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
无参构造默认生成一个空的数组
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
传入一个集合,将传入集合的值copy到数组中,
下面主要看看ArrayList的主要方法;
1 add方法:add有两个重载;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
直接传入一个元素,首先调用ensureCapacityInternal(size+1)这个方法,我们看一下这个方法;
//
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
判断是否为一个空的数组,如果为空的数组那么将minCapacity赋值为默认容量和元素个数加1中的最大的数,然后执行ensureExplicitCapacity(minCapacity);在ensureExplicitCapacity中首先判断minCapacity和当前集合长度进行比较(正常情况下都是minCapacity大),然后执行grow(minCapacity);这个方法就是list扩容的精髓了;请看:
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
可以看到,新容量是旧容量的1.5倍,
而且在add方法中并没有看到对插入元素的检验,所以ArrayList是一个有序可重复的集合,内部实现了可扩容的数组结构,再添加时,调用add(E e)方法默认是在末尾插入,这样效率并没有对什么影响,二如果调用add(int index, E element)这个方法在结合头部插入元素时,由于ArrayList内部使用数组,则已有元素全部需要向后移动一位,这样就大大影响了效率;
2 remove 方法:remove方法也有两个重载
(1)
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;
}
(2)
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;
}
可以看到,一个是按照索引去删除元素,一个是按照元素去删除,
按照索引去删除最后会返回被删除的那个元素,
按照元素删除只会返回true或者false;
按照元素删除最后调用了fastRemove
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
}
其实最后都是通过索引去删除元素;
好ArrayList这部分就先写这么多,之后会继续进行集合接口的源码阅读记录.
