集合的整理
放一张集合关系图
1、开始
java集合 就像个容器 把多个对象丢进去（所以会有人称这个为java的容器） 存在于java.util包下 总的来说由Collection 进行延伸的 也就是根接口
2、Collection接口
继承Iterable接口
注意：Iterable（java.lang） 和 terator（java.util）区别
Iterable是接口 terator是迭代器 实现Iterable接口 才可以调用Iterator方法 对象才可以使用foreach
Iterable 接口在java.lang包下 这个接口下有Iterator<T> iterator();方法
Iterator 是迭代器 迭代器有两个核心的方法 boolean hasNext()和E next() 可以用这个遍历ArrayList Set LinkedList
List<String> str=new ArrayList<>();
str.add("aaa");
str.add("bbbb");
Iterator<String> it=str.iterator();
while(it.hasNext()){
System.err.println("需要先next 然后再remove 否则会报错 java.lang.IllegalStateException==="+it.next());
it.remove();Iterator 迭代器 可以一边遍历一边进行删除操作
Iterable 可以调用Iterator()方法 实现功能返回迭代器Iterator 另外还有增强for循环的方法（forEach(Consumer<? super T> action)）
为啥Collection不直接实现Iterator而是先实现Iterable
Iterator接口的核心方法依赖于迭代器当前迭代位置，如果Collection直接实现Iterator接口 会导致集合对象中包含当前迭代位置的数据 当集合被不同方法使用时 迭代位置就不能预置
每一次调用Iterable的Iterator()方法，都会返回一个从头开始的Iterator对象，各个Iterator对象之间不会相互干扰，这样保证了可以同时对一个数据结构进行多个遍历。这是因为每个循环都是用了独立的迭代器Iterator对象。(为啥collection继承Iterable而不是Iterator)
继承Collection接口 的有三个：List Set Queue 里面有
3、List 集合
有序的容器 保持每个元素的插入顺序 可以允许重复的对象 可以插入多个null元素 常用的实现类有ArrayList LinkedList Vector
关键是查看源代码
1）ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable动态数组 可以快速查询 数组型的集合 有索引查询比较快 但是删除后需要重新排序 所以速度比较慢（看下面源码 ）
查询很快的原因（通过下标进行读取）
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}移除很慢的原因 （删除之后需要排序）
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//这里用了这个方法 也就是删除某个位置元素 后面的往前复制
//public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
elementData[--size] = null; // clear to let GC do its work
}ArrayList插入之前需要判断容量 进行扩容处理 如果没有超过容量（初始容量为10） 增加数据 ArrayList速度还是很快的 超过容量 涉及到 大量数据的复制过程 所以速度会很慢
ArrayList 是非同步的 如果多个线程 在同一个位置对它进行操作 会容易出错 线程不安全
2）LinkedList
基于链表实现的 实现了Deque接口 可以被当做堆栈 队列或者双向队列使用 可以快速插入和删除 也是线程不安全的
重要的是节点的操作
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;
}
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;
}
}
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;
}3）Vector
当集合中有多线程对集合元素进行操作时 用这个 但是现在一般使用CopyOnWriteArrayList
有synchronized 修饰 可以同步线程安全 允许元素为null
4、Set集合
无序 不可重复 只能允许最多为一个null
5、Map集合
键值对形式存储 key可以为null 最多一个
Set集合和Map集合放一起 基本上都会对这两个进行对比
1）HashSet和HashMap
a、HashSet 实现Set接口 继承AbstractSet 抽象类
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializableb、HashMap实现Map接口 继承AbstractMap抽象类
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, SerializableHashSet 存储对象之前重写hashCode()和equals()方法 目的是去重
为啥重写equals()还要重写hashCode() 重写了equals()保证属性值相等，如果不重写hashCode() 就可能导致 对象不一样 两个对象的内存值 还是不能去重
c、HashSet源码里面创建了一个HashMap类型的map对象 可以说是一个特殊的HashMap 添加对象用的是add()方法 没有add(int c ,E e)这个方法 因为HashSet没有下标 从源码看 底层实现是map.pu()方法，元素存放在map集合的Key里面 这也就是为啥不能重复 只允许一个null HashMap 使用的是 public V put(K key, V value)
public HashSet() {
map = new HashMap<>();
}public boolean add(E e) {
return map.put(e, PRESENT)==null;
}2）HashTable和HashMap
a、HashTable 继承Directionary抽象类 实现Map接口 HashMap实现Map接口 继承AbstractMap抽象类 HashTable 有Contains()方法 HashMap 去掉了 改成了containsvalue()和containsKey()
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializableb、HashTable不允许为null指 看源码里面有判断 HashMap可以接受null值 但是只允许一个
//HashTable
public synchronized V put(K key, V value) {
// Make sure the value is not null 确保value不为null 否则抛异常
//在contains(Object value)方法里面也有这个判断
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}c、HashTable 线程安全 方法基本上都是synchronized进行修饰 HashMap线程不安全，使用的时候需要调用Collection类里面的synchronizedMap()静态方法
//这是Collection类里面关于Map加锁的静态方法
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}d、迭代器 HashMap的迭代器是fail-fast迭代器 而HashTable 的Enumerator 迭代器则不是
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)//modCount 修改次数 对hashMap修改一次 增加一次
//迭代器初始化过程中会将modCount 赋值给迭代器的expectedModCount
throw new ConcurrentModificationException();//亮着不相等 别的线程修改了会抛异常
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
e、初始容量和填充因子（见下面代码） 增加方式:HashTable old*2+1 HashTable 是2的指数
/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
this(11, 0.75f);//HashTable初始容量为11 填充因子0.75
}
//HashMap 初始容量16 填充因子0.75
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
f、HashTable 直接使用对象的hashcode HashMap 重新计算hashcode（这个涉及到数据结构的内容 后期再完善修改）
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();//不能存null值
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();//先获取放进去的元素的key的hashcode
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//迭代寻找key 找到就替换
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);//这里就是添加 如果容量不够就进行扩容 具体代码后面分析
return null;
}//HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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);//红黑树节点 采用TreeNode<K,V>进行实现 JDK 1.8 的优化目的主要是：减少 Hash冲突 & 提高哈希表的存、取效率
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();//扩容 后面和hashTable的addEntry()方法进行分析
afterNodeInsertion(evict);
return null;
}
/**
* HashTable 数据存储
*/
private transient Entry<?,?>[] table;扩容问题
3）TreeSet和TreeMap
6、Queue 队列集
上一篇： JS获取屏幕宽高属性总结