一:整体继承的关系
List、Set实现Collection接口。Map并没有实现任何接口,但内部聚合了一个Collection对象
二:数组与集合的不同
三:Collection接口简介
Collection
|-----List 有序(存储顺序和取出顺序一致),可重复
|----ArrayList ,线程不安全,底层使用数组实现,查询快,增删慢。效率高。
每次容量不足时,自增长度的一半,如下源码可知
int newCapacity = oldCapacity + (oldCapacity >> 1);
|----LinkedList , 线程不安全,底层使用链表实现,查询慢,增删快。效率高
|----Vector , 线程安全,底层使用数组实现,查询快,增删慢。效率低
每次容量不足时,默认自增长度的一倍(如果不指定增量的话),如下源码可知
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
|-----Set 元素唯一
一个不包含重复元素的 collection。更确切地讲,set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2,并且最多包含一个 null 元素
|--HashSet 底层是由HashMap实现的,通过对象的hashCode方法与equals方法来保证插入元素的唯一性,无序(存储顺序和取出顺序不一致)。
|--LinkedHashSet 底层数据结构由哈希表和链表组成。哈希表保证元素的唯一性,链表保证元素有序。(存储和取出是一致)
|--TreeSet 基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator 进行排序,具体取决于使用的构造方法。 元素唯一。
四:特性
1、List:
2、Set
3、Map
五:深入特性
1:list\map序列化
transient Object[] elementData; //ArrayList
transient Node<E> first; transient Node<E> last; //LinkedList
transient Node<K,V>[] table; //HashMap
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject(); //对默认可以序列化的字段进行序列化
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) { //对存储的数据进行序列化,单个元素一个一个的序列化
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
2:LinkedList获取元素的方式(*)
public E get(int index) {
checkElementIndex(index); //检查获取位置是否合理
return node(index).item; //获取数据,node(index)方法如下
}
Node<E> node(int 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;
}
}
3:TreeMap排序
package others;
import java.util.*;
/**
* 测试TreeMap的自定义排序方式
* 默认是:对key的由大到小排序
*/
public class TreeMapSortForValue {
public static void main(String[] args) {
////测试根据value从小到大排序(默认为从大到小) <可以进行重复值排序了!!!!>
Map<String,Integer> map = new TreeMap<>();
map.put("a", 4);
map.put("d", 3);
map.put("c", 1);
map.put("b", 7);
map.put("h", 3);
sortForValue(map);
////测试自定义排序,这种方式只能对key操作,不可以对value
Map<String,Integer> map1= new TreeMap<>(new customSortForMinToMax());
map1.put("a", 4);
map1.put("d", 3);
map1.put("c", 1);
map1.put("b", 7);
map1.put("h", 3);
System.out.println(map1);
}
static void sortForValue(Map<String, Integer> map){
List<Map.Entry<String,Integer>> list = new ArrayList<>(map.entrySet());
//自定义排序,默认为从大到小就不必创建下面的语句
list.sort((o1, o2) -> o1.getValue().compareTo(o2.getValue())); //lambda表达式形式,效果等同于下面
// list.sort(new Comparator<Map.Entry<String, Integer>>() { //非lambda表达式形式
// @Override
// public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
// return o1.getValue().compareTo(o2.getValue());
// }
// });
for (Map.Entry m : list){
System.out.println(m.getKey()+" "+m.getValue());
}
}
}
//自定义排序方法的具体实现类
class customSortForMinToMax implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
}
// 有比较器
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
// 如果key值相等,覆盖,返回旧值
return t.setValue(value);
} while (t != null);
}
// 此函数为插入元素后,有可能破坏红黑树性质
// 故需要旋转节点来修复红黑树
fixAfterInsertion(e);
size++;
modCount++;
4:扩容机制
//初始容量
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
//初始负载因子
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
。。。。。
//扩容方法
final Node<K,V>[] resize() {
//创建一个新的数组存储未扩容前数组
Node<K,V>[] oldTab = table;
//记录未扩容前数组参数:容量和负载因子
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //threshold为临界值,即:负载因子*容量
//创建扩容后新数组的参数并初始化
int newCap, newThr = 0;
if (oldCap > 0) {
//如果未扩容前容量就已经大于等于最大容量,则不再扩容,并设置临界值为最大整数值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//赋值扩容后的数组容量和临界存储容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//旧数组容量小于0,如果临界值大于0,则复制新容量为临界值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//旧数组容量和临界值都小于0,则重新初始化为默认容量
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果临界容量为0,则重新计算临界值并赋值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//正式修改 扩容后的临界值
threshold = newThr;
//根据计算的新容量创建一个新的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//正式修改 扩容后的数组对象
table = newTab;
//将旧数组(oldTab)里面的值复制到新数组(table)
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//扩容完成,返回新数组,此处返回table和newTab是一样的,因为数组是引用传递,使用的是同意地址下的数组
return newTab;
}
/**
* Default initial capacity.
*/
//初始容量
private static final int DEFAULT_CAPACITY = 10;
。。。。。。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
//保存未扩容前容量
int oldCapacity = elementData.length;
//新容量为 旧容量的的1.5倍
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);
}
//返回值为<T> T[]的Arrays.copyOf方法
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
//返回值为<T,U> T[]的copyOf方法
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//根据新容量创建新数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//调用系统函数进行克隆
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
5:HashMap中key中null值存储位置(JDK8)
/**put方法*/
public V put(K key, V value) {
//使用了putVal方法,其中使用了hash(key)方法获取到key的hash
return putVal(hash(key), key, value, false, true);
}
/**hash(key)方法*/
static final int hash(Object key) {
int h;
//此处可以看到,当key为null时,直接将其hash值设置为0
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**putVal(,,)方法*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化底层数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//!!!此处计算key应该在数组的位置
// 我们已经知道当key为null时,hash值为0,则“i = (n - 1) & hash]”这一步后"i = 0"
//因为所有的值与0相与都为0,则如果数组的该位置没有节点,则创建一个新的节点并赋值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果有节点,分是否是同一个key两种情况,同一个key则替换其value,不同key则向后拉链
else {
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//增加该map的修改次数
++modCount;
//增加元素数,并注意扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}