java基础:集合类
集合类继承图
其中常见的有:
HashMap、TreeMap、ConcurrentHashMap、ArrayList、LinkedList
ArrayList
特点:底层数据结构是数组。线程不安全。初始大小为10,最大容量为最大为Integer.MAX_VALUE,即((2^31)-1)2147483647。
add(e)实现:
首先去检查一下数组的容量是否足够
扩容到原来的1.5倍
第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
足够:直接添加
不足够:扩容
add(e,i)实现:
检查角标
空间检查,如果有需要进行扩容
插入元素
扩容方法:
扩容大小为1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
总结:
ArrayList是基于动态数组实现的,在增删时候,需要数组的拷贝复制,所以增删时效率较低但是在读取修改时效率高。
ArrayList的默认初始化容量是10,每次扩容时候增加原先容量的一半,也就是变为原来的1.5倍
删除元素时不会减少容量,若希望减少容量则调用trimToSize()
它不是线程安全的。它能存放null值。
LinkedList
特点:底层数据结构是双向链表。线程不安全。
add方法:
往链表的最后添加数据
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
remove方法:
如果添加的o为空则删除最后一个节点,不为空则遍历全部节点找到相同的然后解链。
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
解链方法:
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
总结:
底层数据结构是双向链表。线程不安全。增删速度较快但查改较慢。
Vector(了解)
底层数据结构是数组。线程安全,每次扩容增加原先的2倍
HashMap
特点:
1、底层结构为散列表(哈希表)+红黑树实现(数组+链表-->散列表)。初始容量为16最大容量为2的31次方。桶满并且散列表容量大于64时会从链表变成红黑二叉树 , 默认当一个元素被添加到至少有8个元素的桶中时桶中链表变红黑树 ,当一个元素被删除后桶中只剩6个元素时红黑树变链表
2、装填因子默认为0.75,也就是如果表中超过了75%的位置已经填入了元素,那么这个表就会用双倍的桶数自动进行再散列,并扩容两倍。
3、初始容量和装载因子对HashMap影响挺大的
hash值计算方法:
将hash值和他的高16位进行异或运算。(异或运算:相同为0,不同为1)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
put方法:
1、当散列表为空时,调用resize初始化散列表
2、查看桶是否为空,为空则直接放入
3、若不为空查找链表有没有key相同的元素,如果有则将value值覆盖。
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
LinkedList
特点:
1、底层是散列表和双向链表。继承于HashMap所以如初始容量、装载因子等参数函数和HashMap相同。
2、允许为null,不同步
3、插入的顺序是有序的(底层链表致使有序)
4、装载因子和初始容量对LinkedHashMap影响是很大的~
5、LinkedHashMap遍历的是内部维护的双向链表,所以说初始容量对LinkedHashMap遍历是不受影响的
TreeMap
特点:
1、TreeMap底层是红黑树,它方法的时间复杂度都不会太高:log(n),map集合有序。
2、非同步
3、TreeMap实现了NavigableMap接口,而NavigableMap接口继承着SortedMap接口,致使我们的TreeMap是有序的!
4、使用Comparator或者Comparable来比较key是否相等与排序的问题~
ConcurrentHashMap
1、底层结构是散列表(数组+链表)+红黑树,这一点和HashMap是一样的。
2、Hashtable是将所有的方法进行同步,效率低下。而ConcurrentHashMap作为一个高并发的容器,它是通过部分锁定+CAS算法来进行实现线程安全的。CAS算法也可以认为是乐观锁的一种~
3、在高并发环境下,统计数据(计算size…等等)其实是无意义的,因为在下一时刻size值就变化了。
4、get方法是非阻塞,无锁的。重写Node类,通过volatile修饰next来实现每次获取都是最新设置的值
5、ConcurrentHashMap的key和Value都不能为null