Collection集合，Map集合-平芜编程栈

Collection体系结构图

collection是这些类的父接口，这里主要说ArrayList，linkedlist，hashset，treeset，linkedhashset，

对于集合的操作无非就是几种情况，添加，修改，删除，查询。这不过根据这些实现类的底层存储，效率问题，加上各自的特点，在不同的场景下，使用他们其中相对的综合效率较高的那一个。

collection

这是父类中的抽象方法，其他那几个类都有，再加上一些自己特有的，

新建容器：Collection coll=new ArrayList();
增
add(Object obj); 添加数据
addAll(Collection coll2);//将coll2中的所有数据添加到coll1中批量添加
删
remove(Object obj) 移除指定对象
removeAll(Collection coll2);//将coll2中的数据从coll1中移除
clear() 清空
改
没有提供修改方法
查
coll.isEmpty();//是否为空
coll.size();//返回对象个数
coll.contains(Object obj);//判断是否包含指定对象
containsAll(Collection coll2) 是否包含coll2中所有对象
求交集
retainAll(coll2);//求两个集合的交集

Iterator 集合的遍历

先说集合的遍历，在collection几口中有个Iterator<E> iterator();这个东西，他返回的是个Iterator类型的对象，他是一个迭代器，用于遍历集合的，当然那遍历集合不只这一种方式，先说这个，

我们发现这个也是一个接口，而且在第一张图中发现所有的集合都实现了这个接口（中间还有一个Itertable 接口）

1. 在当前集合上添加一个迭代器
Iterator iter = coll1.iterator();
2. 判断下一个位置是否有值
iter.hasNext()
3. 取出下一个位置的值，并将指针移动一位
iter.next()

移除方法：iter.remove(); 移除iter指向的那个数据

//第一种遍历方式 Iterator(迭代器) while(iter.hasNext()){ Object next = iter.next(); System.out.println(next); }

//第二种遍历方式 foreach(增强for循环) 也能遍历数组 // 语法：for(数据类型 对象名:容器){ // } //案例：循环一次就从coll1中取一个对象赋值给obj,直到coll1中所有值取完为止 for(Object obj:coll1){ System.out.println("--"+obj); }

注意：只要实现Iterable这个接口的数据，就可以作为foreach冒号后面的类型
foreach不一定只能操作实现Iterable这个接口的数据

这里还有一个问题，就是在迭代的时候对集合进行修改的问题，（为什么，迭代器的删除就没有问题，而用集合的删除就会出现问题呢）

public static void main(String[] args) { Collection coll=new ArrayList(); coll.add("aaa"); coll.add(12); coll.add(13); coll.add(3.4); coll.add("aaa"); coll.remove(12); System.out.println(coll); Iterator iter = coll.iterator();//new Itr() cursor=0 while(iter.hasNext()){//如何判断下一个是否有值的？ return cursor != size; Object next = iter.next(); System.out.println(next); if(next.equals(13)) //coll.remove(13);// 这个不行会报错的 iter.remove(); } }

这个时候需要我们通过DEBUG去查看ArrayList里面的源码：

发现：ArrayList里面有个内部类，他返回了一个Itr对象，

Iterator是一个接口 iterator()中 -->return new Itr();
new Itr() 会初始化Itr的普通属性
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;//将当前集合的修改次数进行了赋值
2. 在集合操作过程中，size:集合的对象个数 modCount:标记修改次数
3. hasNext()
public boolean hasNext() {
return cursor != size; //判断cursor是否已经达到size(cursor在next方法中会自增)
}
4. next()
public E next() {
checkForComodification();//检查修改次数（集合的修改次数和迭代器修改的次数是否相同） --> 此方法才是我们在// 遍历集合时不能够对集合进行修改的原因
int i = cursor;//将当前游标的值赋值给i
if (i >= size)//判断当前i是否超出集合的对象个数
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//将集合中的数组进行备份
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;//将游标的值进行加1
return (E) elementData[lastRet = i];//返回对象
}
// PS: 检查修改的次数
// 此方法才是我们在遍历集合时不能够对集合进行修改的原因
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

5. iter.remove(); // 这个为什么可以移除呢？会对集合的修改次数进行更新操作
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);//会执行删除操作 modCount值会改变
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;//但是此处会将expectedModCount的值重新赋为新modCount的值
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

总的来说就是，在迭代的过程中只要进行.next(),remove(),都会进行检查，判断迭代器的修改次数和集合对他的修改次数是否相同，不同会抛出并发修改异常。

集合的修改次数是不是不明白，在ArrayList当中只要对集合进行修改他也会记录就该次数（在下面的源码中你会经常发现modcount++的身影），只不过记录的属性在抽象类中声明了，

这是ArrayList里面的所有属性是不是没有发现modCount他在AbstractList类中

ArrayList（只说区别）添加修改删除的方法，最后在统一说

区别：底层存储数据的方式是不同的（数组）

底层分析：
a. 在创建ArrayList对象时，将数组的初始容量设置为0
b. 在进行第一次添加时，会将数组的容量设置为10，并且将数据添加到第一个位置上
c. 在进行后面的添加时，查看当前数组是否有空间，如果有空间就按照顺序去添加
如果没有空间，则自动进行扩容(扩容规则是原容量的1.5倍) 10->15->22

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } // 第一次添加数据此方法返回值是10，否则直接返回minCapacity private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0)//判断数组容量是否能够满足添加当前数据 grow(minCapacity);//扩容的代码 } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);//原容量的1.5倍 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);//扩容代码 }

LinkedList 双向链表

至于什么是双向的链表（不会的话建议不要看这个了，先去学学数据结构的链表）

底层分析：
他的底层的数据添加，就是数据结构中的双向链表的添加，没啥可说的，都学java的，你的数据结构我猜你肯定学了。没学就去补，这里不多讲（单链表，双向链表，循环链表，PS：很基础的东西）

源码追踪：
在创建LinkedList对象时，只是加载了first和last普通的属性(赋值为null)
添加操作：

public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last;//将目前的最后一个节点进行备份 //将新数据封装成一个Node节点对象(而且将prev设置为之前的最后一个节点、将next设置为null) final Node<E> newNode = new Node<>(l, e, null); last = newNode;//直接将新节点对象赋给last if (l == null)//判断之前的最后一个节点是否是null(判断是否是第一次添加) first = newNode;//将新节点也赋值给了first else l.next = newNode;//将之前的最后一个节点对象的next设置为当前节点对象 size++; modCount++; }

list：

底层效率(增删) 效率(改查)
ArrayList 数组较低较高 ★
LinkedList 双向链表较高较低
a. 特点
允许重复
有顺序(添加顺序) 意味着存在下标的概念

b. List接口中有哪些常用的方法
增
add(Object obj);
addAll(Collection coll);
add(int index,Object obj);在集合的指定索引位置插入数据
addAll(int index,Collection coll);在集合的指定索引位置批量插入数据
删
remove(Object obj)
remove(int index) 移除指定索引位置的对象如果删除的数据是int型，需要手动装箱
removeAll(Collection coll);
clear()
改
set(int index, Object obj) 修改指定索引位置的对象
查
isEmpty()
size()
contains(Object obj)
containsAll(Collection coll)
get(int index) 返回指定索引位置的对象
indexOf(Object obj) 返回集合中第一次出现指定对象的索引值
lastIndexOf(Object obj) 返回集合中最后次出现指定对象的索引值
交集
retainAll(Collecton coll) 去交集

HashSet

特点：

无序(添加顺序) 有自己的一套排序机制(hash值)
不可重复

HashSet底层维护了一个HashMap,HashMap中维护了一个table(这是一个Node类型的数组)
(table中每一个空间都是一个单向链表结构) 容量和扩容问题在HashMap时在仔细研究

所以说他的添加操作跟hashmap的添加操作一样

（PS：这个node就相当于一个指针。这个table在我就是一个链表数组，然后具体添加多数组的那个位置，有相应的规定）

他既然维护了一个hashmap那么他的好多方法都是间接调用了hashmap中的方法

hashset的扩容机制，去重机制，数据的添加方式

添加方法
1. 先计算出当前对象的hash值
2. 判断当前数组是否为空，或者长度是否为0，如果成立，则进行初始容量的设置
3. 根据当前对象的hash值和数组的长度计算出一个索引值，判断当前索引值位置是否有值
如果没有 --> 直接将当前对象封装成Node节点，添加到当前索引位置
如果有
a. hash值一样
继续判断内容是否一致(equals)
内容一致
直接覆盖value值
内容不一致
如果不是树节点，则直接将当前对象链接到单向链表中
循环判断，当前链表中是否有对象和当前对象一致
如果有一致的则覆盖value值，如果没有一致的则成功链接到当前链表中
b. hash值不一样
就判断当前节点是否是树节点
如果不是树节点，则直接将当前对象链接到单向链表中
循环判断，当前链表中是否有对象和当前对象一致
如果有一致的则覆盖value值，如果没有一致的则成功链接到当前链表中
HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能。HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。因此

//源码追踪 //创建对象时，构造器只创建了一个HashMap对象 public HashSet() { map = new HashMap<>(); } // 添加方法--会调用map中的put方法，值是作为map中的key值出现，value值是一个常量对象 public boolean add(E e) { return map.put(e, PRESENT)==null; } //map中的添加方法 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // 计算当前数据的hash值，并且经过了一些位运算(可以直接将运算后的值看作是数据的hash值) static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 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)//判断table是否为空，或者长度是否为0 n = (tab = resize()).length;//将table进行了一个初始容量的设置 //(n - 1) & hash 根据数据的hash值计算出一个索引值,并判断当前索引位置是否有值 if ((p = tab[i = (n - 1) & hash]) == null)//(a. hash一样，索引值肯定一样 b.hash值不一样，索引值也有可能一样) //如果没有值，直接进入if，指定添加操作(将当前数据封装成一个Node节点添加到当前数组的空位置) tab[i] = newNode(hash, key, value, null); //如果该索引位置有值，则进入到else else if (p.hash == 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; } //如果能够执行到此处，说明数组中当前元素的下一个元素是有值，判断下一个元素和新元素是否一致 //如果一致，则直接break if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //如果不一致，则继续循环，继续往下一个判断 p = e; } }

LinkedHashSet

LinkedHashSet是HashSet的子类，它在HashSet的基础上，在结点中增加两个属性before和after维护了结点的前后添加顺序。java.util.LinkedHashSet，它是链表和哈希表组合的一个数据存储结构。LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

TreeSet

TreeSet中维护了一个TreeMap

特点：

TreeSet无序：
有一个大小排序机制
Comparable --> int compareTo(Object obj)
Comparator --> int compare(Object o1,Object o2)
TreeSet不可重复：
Comparable --> int compareTo(Object obj)
Comparator --> int compare(Object o1,Object o2)
如果返回的是0，则进行value值的覆盖
TreeSet中如果定制排序和自然排序同时存在，以谁为准！定制排序为准

//TreeSet中维护了一个TreeMap,创建TreeMap对象时，如果有定制排序 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } public TreeSet() {//没有定制排序的，那么他的类必须实现Comparable接口 this(new TreeMap<E,Object>()); } public V put(K key, V value) {//TreeMap的添加方法 Entry<K,V> t = root;//将根节点备份 if (t == null) {//判断是否是第一次添加 compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null);//直接将对象封装成Entry对象，赋给根节点 size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator;//将定制排序的对象进行备份 if (cpr != null) {//是否有定制排序 //从根节点就行对比，直到有一个分叉是null为止，找到当前对象添加的位置 do { parent = t; cmp = cpr.compare(key, t.key);//对比的代码 if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); }else { //说明没有定制排序 ---> 默认就采用自然排序 if (key == null)//抛空指针异常 throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key;//将当前对象强转为Comparable //依然是从根节点进行对比大小，直到找到自己所在的位置为止 do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else//说明在当前树节点中找到和当前对象相同的数据了，则对value值进行覆盖 return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent);//将当前对象封装成一个Entry对象 if (cmp < 0) parent.left = e;//将当前Entry对象放在parent的左侧 else parent.right = e;//将当前Entry对象放在parent的右侧 fixAfterInsertion(e); size++; modCount++; return null; }

map

1. Map集合双列集合 key-value(键值对)
2. Map集合的实现类 HashMap、TreeMap、LinkedHashMap、Hashtable、Properties(读取配置文件:IO流)
Map中的所有key值就相当于一个Set集合(满足Set集合的特点)
Map中所有value值就相当于一个Collection/List
(Map中的所有value值，是可以重复的，它的顺序由key值决定)

HashMap中的常见方法

增

put(Object key,Object value);//会检测key是是否已存在，如果不存在直接添加，如果存在则进行覆盖 putAll(Map map) //将Map集合中所有内容添加到新map集合中 批量添加

删

remove(Object key)// 根据key值进行移除 remove(Object key, Object value);//根据key+value值进行移除 clear();

改

replace(Object key, Object newValue);//根据key值进行替换value值 replace(Object key, Object oldValue,Object newValue);//根据key值+value值进行替换value值

查

map.isEmpty() //判断是否为空 map.size() //获得键值对个数 map.containsKey(2)); // 是否包含key值 map.containsValue("css"); //是否包含value值 map.get(Object key); //根据key值获得value值

HashMap的遍历方式

keySet() //返回map中所有的key值 Set set = map.keySet();//返回map中所有的key值 for (Object obj : set) { System.out.println("key---"+obj); System.out.println(map.get(obj)); } values() 获得map中所有的value值 Collection values = map.values(); for (Object object : values) { System.out.println("%%%"+object); } entrySet();//返回map中所有的键值对(Map.Entry) Set entrySet = map.entrySet();//返回map中所有的键值对(Map.Entry) for (Object object : entrySet) { Map.Entry entry=(Map.Entry)object;//向下转型 强转 System.out.println(entry.getKey());//单独获得key值 System.out.println(entry.getValue());//单独获得value }

Hashmap的扩容

a.初始化工作
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
将负载因子设置为0.75
table=null
临界值=0
b.在第一次添加数据时，会将数组容量设置为16，并且计算出临界值为12:((int)16*0.75)

c.在超过hash表的临界值时，会先进行添加数据的操作，在进行扩容(扩容规则是原容量的2倍，新的临界值也是原来的2倍)
if (++size > threshold)
resize();
d.扩容完成后，会将旧数组中的数据，转移到新数组中(会重新根据hash值和新数组长度进行计算新的索引位置)

e.在添加数据时，如果一个桶中的链表长度大于8，并且数组长度达到64，则将当前链表结构变为红黑树结构
如果当前桶内已经是树结构了，则按照树结构的方式去添加数据（什么时候树化，什么时候反树？）
HashMap是线程不安全的，并允许使用 null 值和 null 键。

扩容的源码：

（第一次扩容量为16，边界值为16*0.75=12，以后每次每次的扩容，容量为之前的2倍，边界值也为原来的两倍）

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的，以后的每次扩容都会进入到if中 if (oldCap >= MAXIMUM_CAPACITY) {//如果就容量大于最大值，则采用int范围的最大值作为临界值 threshold = Integer.MAX_VALUE; return oldTab; } //对旧容量进行2倍操作，并赋值给新容量 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //将临界值也更新为原来的2倍 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];//采用新容量创建hash表 table = newTab;//将新创建的hash表赋值给table (table就有容量了) if (oldTab != null) { //主要是将旧数组中的数据，循环添加到新数组中,会重新分配空间 for (int j = 0; j < oldCap; ++j) { } }

Set和Map关系
Set集合的底层都是Map集合 HashSet->HashMap TreeSet->TreeMap

TreeMap 红黑树
TreeMap中的所有key值，就相当于TreeSet集合(a.不能重复 b.具有大小排序机制 c.数据必须是相同类型 d.必须具备排序机制)