字数太多了分开发。
1、Collection学习-day2
Vector部分源码
无参构造
调用verctor无参构造
Vector vector = new Vector();
首先进入无参构造,this(10)就相当于Vector(10),还是方法重载,所以我们可以看到无参构造默认的初始化大小initialCapacity为10
进入有参构造,继续调用另一个重载方法,这时候有个capacityIncrement的变量,暂时先不管,后面会说。
进入另一个构造函数,super是调用父类无参构造,因为Vector继承了一个AbstracList的父类,子类继承父类一定要先调用父类的无参构造,super不写也会默认加上。
然后判断initialCapacity是否合法(>=0),如果合法那么就给elementData赋值10个大小、Object类型的数组,把capacityIncrement赋值。因为我们是无参构造,所以initialCapacity、capacityIncrement都是默认值,一个是10,一个是0
Add方法
在add处打个断点
进入后发现,和ArrayList很像啊,无非是ArrayList用size,Vector用elementCount记录下标。
再进入,进行一个判断,下标是否达到数组的长度,如果达到了就要扩容,如果没达到就赋值,然后下标加1
我们加满10个后,进入grow()看一下,和ArrayList的逻辑一模一样
有点区别的地方就是newCapacity。第一个区别是它不需要判断newCapacity是不是空了,因为给了默认值10,所以不会是空的;第二个区别就是扩容机制,这里就用到了capacityIncrement,默认是0,如果大于0,我们每次扩容都增加capacityIncrement;否则,我们就扩容两倍,也就是加上oldCapacity。
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity <= 0) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
有参构造
我们有参构造可以指定capacityIncrement的大小,就像这样,指定初始值大小和扩容大小。
LinkedList部分源码
LinkedList底层是双向链表。有个内部类Node,代表结点。
自身有size记录大小,first、last头尾指针,我们存放的数据即能通过first的next指针遍历,也能通过last的pre指针遍历
如图所示,LinkedList的结构
构造器
就提供了两个构造器,常用无参构造,另一个是Collection类型,?是通配符,代表一切类型
<? extends E>泛型类型的上限,代表只能是E或者E的子类
<? super E>泛型类型的下限,代表只能是E或者E的父类
add方法
add方法会调用linkLast方法,其实就是在尾部添加元素,和addLast调用的方法一样。
进入linkLast方法,用l先暂时记录last的值,建立一个新结点,前驱是l,即last,后驱当然是null啦。
然后把这个新结点赋值给last,作为最后一个元素。这时候last变了,这就是为什么用l的原因。
第一次赋值后
当l==null,说明是空链表,那就让first也是新结点。
我们再添加一个,新结点是连接之前的last的,所以last里已经形成倒序的单向链表了。
这是会进入另一个分支,l.next=newNode,l代表刚才那个元素的后继要连接到新结点,这样就形成了双向链表了。
自己多跑几次源码就会理解了,要讲出来还是挺费人的,,,可以尝试自己动手跑跑romove、set、get方法。
2、Map系列
Collection是单列元素,Map存的是Key-Value的双列元素。
简易Map体系
常用方法
HashMap map = new HashMap();
// put,存放无序,按key的hash存储的
// key不能重复,重复了有替换机制
map.put("no1", "aaa");
map.put("no2", "bbb");
map.put("no3", "ccc");
map.put("no1", "aaa2");
System.out.println("put: " + map);
// remove
map.remove("no1");
map.remove("no2", "bbb");
System.out.println("remove: " + map);
// get
Object o = map.get("no3");
System.out.println("根据key来get: " + o);
// size
int size = map.size();
System.out.println("key-value数量: " + size);
// isEmpty
boolean empty = map.isEmpty();
System.out.println("isEmpty: " + empty);
// clear
map.clear();
System.out.println("clear: " + map);
// containsKey containsValue
boolean b = map.containsKey("no1");
boolean b1 = map.containsValue("aaa");
System.out.println("contaisKey: " + b);
System.out.println("containsValue: " + b1);
控制台输出:
put: {no2=bbb, no1=aaa2, no3=ccc}
remove: {no3=ccc}
根据key来get: ccc
key-value数量: 1
isEmpty: false
clear: {}
contaisKey: false
containsValue: false
遍历
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("no1", "aaa");
map.put("no2", "bbb");
map.put("no3", "ccc");
// 1 取key
Set set = map.keySet();
// 增强for
for (Object o : set) {
System.out.println(o + "-" + map.get(o));
}
// 迭代器
Iterator it = set.iterator();
while (it.hasNext()) {
Object next = it.next();
System.out.println(next + "-" + map.get(next));
}
// 2 取value
Collection values = map.values();
System.out.println("~~~~~~~~~~~~~~~~~~~");
for (Object value : values) {
System.out.println(value);
}
// 3 通过Map.EntrySet
Set entrySet = map.entrySet();
for (Object entry :entrySet) {
Map.Entry m = (Map.Entry) entry;
// 提供了getkey和getvalue方法
System.out.println(m.getKey() + "--" + m.getValue());
}
}
HashMap里的entrySet()方法,返回的是Set集合,而这个Set集合里放得是Map接口下的接口——Entry接口。
Entry的作用是为了方便遍历Map集合,因为其提供了getValue和getKey方法。
HashMap的底层是散列表Table,Table里存放的是Node,而Node又实现了Entry接口,本质上我们的每个键值对是存放在Table里的Node中,然后HashMap中又提供了一个entrySet的Set集合,作用是方便我们遍历HashMap的键值。
HashMap源码
HashMap应该是Map的重点。
初始化对象,将loadFactor默认因子设为0.75
调用put方法,
先看看hash方法,并非简单地传回key的哈希值,而是将key的哈希值操作了一番。(点到为止,没做深入研究)
再进入putVal,这应该就是put方法中最核心的代码了,代码量也比较大,如下。
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;
}
应对这种源码,就应该逐步拆解着看,多跑几次,把能跑出来的理解了,然后再看那些没跑过的,再去理解什么意思。所以第一次进来,首先会执行下面这条语句,因为此时table表确实为null,可以看一下此时hashMap的结构。
然后就进入了HashMap的另一个核心方法resize,这里面就是HashMap的扩容机制。
resize代码如下,和putVal不相上下,也慢慢拆解。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = 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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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;
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;
}
}
}
}
}
return newTab;
}
首先,操作了一下新老数组和新老临界值(threshold, newThr, oldThr)
因为是第一次,这些值都为0,所以进入else分支,在这里,第一次记录table扩容为16的默认值,记录边界值为加载因子*默认初始值。
然后把记录的值真正赋值给threshold(临界值,16*0.75=12),并且给table创建新的Node类型的数组,大小为16。
然后后面的暂时不看,我们回到putVal,重点是,执行了resize后,table被初始化了。
然后下一个if,这里是算出要插入table表的位置,这个位置的值如果是null(第一次肯定都是null啊),就直接插个新结点,也就是调用newNode,这就不进去看了。
然后剩下的代码都不执行,直接跳到这里,这里就说明了threshold的作用了,Map不是把数组容量耗尽了扩容,而是找一个边界值,这个边界值是用一个因子*数组大小计算出来的(感兴趣可以看看这个HashMap默认加载因子为什么选择0.75?(阿里) - aspirant - 博客园 (cnblogs.com)),如果键值对的个数超过了这个临界值,就resize扩容。
OK,走完了这个流程,理解了第一次添加的逻辑,其实并不是很难,因为把复杂的大量代码拆解成一个个部分了,那我们添加key重复的元素会怎么样呢?会进入到这个else语句
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;
}
}
还是拆开看,先看看第一组if:
①:这里是判断是否重复的核心,首先先看看hash值是否相等,如果相等还要满足key地址相等或者key的equals方法相等。由此我们可以知道Map底层是如何判断相等的了,与Value无关,只与Key有关,并且我们可以通过重写equals方法来决定如何判断相等。如果Key相等,后面会覆盖Value。
②:这里是树化,jdk8的map改成了数组加链表加红黑树的结构了,当table的大小>=64并且单个链表的长度>=8时会把链表转成红黑树。暂时先了解到这里。
③:这是在这个链表上循环遍历,如果找到相同的就退出,如果没找到相同的就添加到这个链表的尾部,如果链表长度大于等于8了,就执行treeifyBin树化,一会再看这个代码。
ok,执行完了又会判断一下e是否为空,添加重复的元素e=p,e的值就是添加的这个Node的值,不为null,中间e.value = value是value覆盖语句。
执行完了,再看看树化treeifyBin的代码,可以看到,首先要判断table是否为null,或者table的大小是不是小于64(MIN_TREEIFY_CAPACITY的值),如果table不足64会先扩容,不会树化。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
第二次扩容我们会更新table大小,边界值,边界值直接乘2。
总结
大概就理解这些吧,看源码太耗功力了,源码这东西,看起来费劲,写起来更费劲,不如自己多追踪追踪体会体会。本来还想写写LinkedHashMap、HashSet、LinkedHashSet的,不写了不写了。
HashSet底层就是HashMap,底层传入的Value是一个默认值,而LinkedHashSet底层是LinkedHashMap,而LinkedHashMap的底层还是HashMap,其实还是HashMap的那些核心源码,只是维护了一个双向链表来实现取元素有序。
总结一下常用容器:
<1>Collection:单列
允许重复:List
- 增删方便:LinkedList 双向链表
- 改查方便:ArrayList 可变数组
- Vector线程安全,但是一般不用
不允许重复:Set
- HashSet 底层HashMap
- TreeSet 能排序
- LinkedHashSet 插入与取出顺序一致
<2>Map:双列
- 键无序:HashMap 底层是哈希表,jdk7:数组+链表;jdk8:数组+链表+红黑树
- 键排序:TreeMap
- 键取出和插入顺序一致:LinkedHashMap
- 读取文件用的:Properties
- HashTable:功能与HashMap类似,线程安全,但是不推荐用,效率太低,并发一般都用ConcurrentHashMap
当然容器的知识远不止这些,暂时先学到这里。