源码分析第二期---List集合与Set集合
List接口
List接口的常用实现子类：Vector，ArrayList，LinkedList
注意事项
• List集合中元素有序（添加顺序和取出顺序一致），并且可以重复
• List集合中的每一个元素都有对应的顺序索引，即==支持索引取出==
• 可以放任意类型的数据（包括null），并且可以存放多个null值
• 线程不安全（因为线程不安全，所以执行效率比较高 ）
• Vector是线程安全的，在多线程的情况下，不建议使用Arraylist
List接口常用方法及其遍历方式
• 使用迭代器 ```java import java.util.*;
public class Map1 { public static void main(String[] args) { List list = new ArrayList<>(); list.add("jack"); list.add("bom"); list.add("鱼香肉丝"); list.add("北京烤鸭");
//迭代器遍历
Iterator<Object> iterator = list.iterator();
while (iterator.hasNext()){
Object next = iterator.next();
System.out.println(next);
}
}}
- 使用增强for
```java
for(Object e:list){
System.out.println("list"+e);
}• 使用普通for
List扩容机制
• Arraylist维护一个Object类型的数组elementData[]；
• 当创建ArrayList对象的时候，如果使用无参构造器，则初始化elementData容量为0，第一次添加，则扩容elementData为1.5倍。
• 如果指定容量大小，则扩容的时候直接按指定容量的1.5倍扩容。
源码分析
public static void main(String[] args) {
List<Object> list = new ArrayList<>();
for (int i = 0; i <=10 ; i++) {
list.add(i);
}
for (int i = 0; i <=20 ; i++) {
list.add(i);
}
System.out.println(list);
}源码解读：创建一个空的elementData 数组；
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}添加元素
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}Vector底层结构和源码剖析
• Vector底层也是一个对象数组
• Vector是线程安全的
Vector的扩容机制
• 如果是无参构造，默认空间大小是10，满后，就按二倍扩容
• 如果指定大小，每次直接按二倍扩容
LinkedList底层结构
• 底层实现了双向链表和双端队列特点；
• 可以添加任意元素（元素可以重复），包括null；
• 线程不安全的，没有实现按同步；
• LinkedList底层维护了一个双向链表，所以LinkedList的元素的==添加和删除==效率比Arraylist要高。
LinkedList源码分析
主要看一下这里添加一个元素的代码
//创建一个节点
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
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++;
}ArrayList与LinkedList比较
| 项目 | 底层结构 | 增删 | 改查的效率 |
| ArrayList | 动态数组 | 效率低 数组需要扩容 | 效率高 |
| LinkedList | 双向链表 | 较高，通过改变链表的指向 | 效率低 |
实际开发过程中使用ArrayList用的多，因为在开发过程中，我们进行改和查的情况最多。
set接口
set接口的常用方法
• set接口的实现子类主要有：HashSet，TreeSet
• Set接口添加与取出的顺序是不一致的（无序），没有索引值
• 不允许有重复元素，最多有一个null值
• set接口同样是collection接口的子接口，同样具有迭代器和增强for遍历的功能。
HashSet
• HashSet底层创建的其实就是Hashmap；
•
public HashSet() { map = new HashMap<>(); }• 可以存放null值，但是只能存放一个null值
• 不保证存放的数据和取出的顺序一致
• 不能有重复的元素
用数组和链表模拟一个简单的集合
模拟代码：
import java.util.*;
public class Map1 {
public static void main(String[] args) {
Node[] table = new Node[16];//创建一个Node数组
//创建节点
Node join = new Node("join",null);
//把该节点放在索引为2的位置
table[2] = join;
//再创建一个新得节点存放在数组2得join的后面
Node jack = new Node("jack",null);
join.next = jack;
}
//创建一个节点
static class Node{
Object item;//存放数据
Node next;//指向下一个节点
public Node(Object item, Node next) {
this.item = item;
this.next = next;
}
}
}
我们采用模拟的方法来创建一个Node类型的数组，来存放变量，当存入第一个值得时候：
当我们再数组2的join节点后面继续添加元素，当一个链表的节点数大于8，且数组的大小大于64的时候，此时链表就会变成红黑树。
HashSet的扩容机制
分析下面代码在源码中的执行过程
HashSet<Object> list = new HashSet<>();
list.add("java");
list.add("php");
list.add("java");大家可以看这篇文章中HashMap的扩容机制，HashSet与其类似 源码分析
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();//扩容，当size大于12的时候才会执行扩容代码
afterNodeInsertion(evict);
return null;
}如果传入的元素相同，那么第二次传入的时候就不执行这里
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//这里就是判断是否
}这段代码中我强调一点就是equal方法的使用，该方法是程序员自己重写的，比较的具体是什么，由程序员来定义。不能简单的理解为内容相同。因为每个类都有自己的equal方法，我下面举个例子：
import java.util.*;
public class Map1 {
public static void main(String[] args) {
HashSet<Object> list = new HashSet<>();
list.add(new Dog("小花"));
list.add(new Dog("小花"));
System.out.println(list);
list.add(new String("渣渣鑫"));
list.add(new String("渣渣鑫"));
System.out.println(list);
}
//创建一个内部类Dog
static class Dog{
private String name;
public Dog(String name){
this.name = name;
}
@Override
public String toString() {
return "Dog{" +
"name='" + name + '\'' +
'}';
}
}
}
大家会发现Dog类创建的对象是重复出现的，而String创建的对象则只有一个显示，这就说明二者对象下的equals的实现方式不同。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;所以添加一个元素的时候，如果该元素计算出来的哈希值和当前索引位置对应的链表的第一个元素值相同，并且准备加入的key的值和索引中的值相同（说明他们就是同一个对象）或者他们的equals相同。如果满足其中的一个就不能将该元素添加进去
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);如果上面判断为假，就是说，他们计算出来的哈希值相同并且满足内容相同这两个条件，就不能加入该元素。走到这里说明上面的两个条件都不满足，然后就判断p是不是一颗红黑树，如果是一颗红黑树，就调用putTreeVal()方法；
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;
}走到这里说明上面的三种情况都不满足，就看看他与链表中的元素是否相同。这里采用的是循环比较机制。
LinkedHashSet源码解读
• LinkedHashSet是HashSet的实现类，他的底层是LinkedHashMap，底层维护的是一个数组和一个双向链表。
• LinkedHashSet根据元素的hashCode值来决定元素的存储位置（确定数组的索引），同时使用链表维护元素的次序，就是使得元素插入和取出的顺序保持一致。
• 不可以添加重复元素，简单理解为什么插入和取出的元素是有序的。就是存入的元素会与新插入的元素取得联系，他们收尾相连来取得联系.
• LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全 部元素时有很好的性能。
add的底层实现还是Hashmap相同
与HashMap的putVal是相同的