Collection体系结构图collection是这些类的父接口这里主要说ArrayListlinkedlisthashsettreesetlinkedhashset对于集合的操作无非就是几种情况添加修改删除查询。这不过根据这些实现类的底层存储效率问题加上各自的特点在不同的场景下使用他们其中相对的综合效率较高的那一个。collection这是父类中的抽象方法其他那几个类都有再加上一些自己特有的新建容器Collection collnew 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几口中有个IteratorE 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 collnew 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() cursor0 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 returnint lastRet -1; // index of last element returned; -1 if no suchint 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;//将当前游标的值赋值给iif (i size)//判断当前i是否超出集合的对象个数throw new NoSuchElementException();Object[] elementData ArrayList.this.elementData;//将集合中的数组进行备份if (i elementData.length)throw new ConcurrentModificationException();cursor i 1;//将游标的值进行加1return (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对象时将数组的初始容量设置为0b. 在进行第一次添加时会将数组的容量设置为10并且将数据添加到第一个位置上c. 在进行后面的添加时查看当前数组是否有空间如果有空间就按照顺序去添加如果没有空间则自动进行扩容(扩容规则是原容量的1.5倍) 10-15-22public 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 NodeE l last;//将目前的最后一个节点进行备份 //将新数据封装成一个Node节点对象(而且将prev设置为之前的最后一个节点、将next设置为null) final NodeE 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) { NodeK,V[] tab; NodeK,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 ((TreeNodeK,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; } }LinkedHashSetLinkedHashSet是HashSet的子类它在HashSet的基础上在结点中增加两个属性before和after维护了结点的前后添加顺序。java.util.LinkedHashSet它是链表和哈希表组合的一个数据存储结构。LinkedHashSet插入性能略低于 HashSet但在迭代访问 Set 里的全部元素时有很好的性能。TreeSetTreeSet中维护了一个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 TreeMapE,Object()); } public V put(K key, V value) {//TreeMap的添加方法 EntryK,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; EntryK,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); } EntryK,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; }map1. 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);//根据keyvalue值进行移除 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.75tablenull临界值0b.在第一次添加数据时会将数组容量设置为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.7512以后每次每次的扩容容量为之前的2倍边界值也为原来的两倍final NodeK,V[] resize() { NodeK,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}) NodeK,V[] newTab (NodeK,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-TreeMapTreeMap 红黑树TreeMap中的所有key值就相当于TreeSet集合(a.不能重复 b.具有大小排序机制 c.数据必须是相同类型 d.必须具备排序机制)LinkedHashMapHashSet-HashMap LinkedHashSet-LinkedHashMap特点 map集合中的key变为有序的了在HashMap的基础上添加了一个链表结构Node他是一个内部类在hashmaplinkedlist它相当于一个链表结构