java基础系列(一)List 和 Set
1. List 特点
2. Set特点
Set具有与Collection完全一样的接口，因此没有任何额外的功能，不像前面有两个不同的List。实际上Set就是Collection,只 是行为不同。(这是继承与多态思想的典型应用：表现不同的行为。)Set不保存重复的元素(至于如何判断元素相同则较为负责)
Set 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。
ArrayXxx:底层数据结构是数组，查询快，增删慢LinkedXxx:底层数据结构是链表，查询慢，增删快HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序
3. ArrayList 和 HashSet分析
此处挑选常用集合做分析
ArrayList
默认大小
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
内部是一个对象数组
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
扩容 1.5倍
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);
}
数组拷贝
Arrays.copyOf(elementData, newCapacity);
底层调用
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
HashSet
内部原理, 存放一个map, 将添加的值作为key, object对象做value
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}