集合本身就是容器，用于存储元素（实际上存储的是引用）。不同的集合实体类的底层数据结构是不一样的，如ArrayList的底层数据结构是数组，LinkedList的底层数据结构是双向链表，HashMap的底层数据结构是哈希表。常见的集合接口是Collection和Map。两者明显的区别在于，前者存储的值是单一的，可以遍历，后者存储的值是键值对的方式，不可遍历。如下图：
这里需要再次强调的是，不同的集合底层依赖的数据结构是不一样的，也就是说元素的组织方式不一样，要根据具体的情况，选择适当的集合。（PS：加强数据结构的学习和复习）
Collection
Map
Collection接口继承了Iterable接口，该接口保证了Collection任意的实现类都拥有一种能力–可迭代（遍历），最明显的体现就是 foreach 循环可以实现Collection的任意实现类的遍历。
List<String> arr = new ArrayList<>(); arr.add("1"); arr.add("2"); arr.add("3"); for(String s:arr){ System.out.println(s); }结果
1
2
3
事实上，foreach循环适用于数组以及任何实现了Iterable接口的类，以ArrayList为例，上面的foreach循环等价于
Iterator<String> iterator = arr.iterator(); while (iterator.hasNext()){ String s = iterator.next(); System.out.println(s); }其中hasNext()和next()都是接口Iterator的重要方法，下面讲述Iterable和Iterator接口。
Iterable的字面意思是可迭代的，可遍历的，表示一种能力，任何集合如果想能被遍历，那么就必须实现这个接口。
public interface Iterable<T> { // main method Iterator<T> iterator(); default void forEach(Consumer<? super T> action) { Objects.requireNonNull(action); for (T t : this) { action.accept(t); } } default Spliterator<T> spliterator() { return Spliterators.spliteratorUnknownSize(iterator(), 0); } }而里面核心的方法 Iterator<T> iterator();必须被实现。该方法会返回一个Iterator，即迭代器，所以如果要让自定义的集合能被遍历，除了重写Iterable接口以外，还需要重写Iterator接口。
public interface Iterator<E> { boolean hasNext(); E next(); default void remove() { throw new UnsupportedOperationException("remove"); } default void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (hasNext()) action.accept(next()); } }Iterator迭代器接口可以按照下面的图理解
hasNext方法用于查看该集合是否还有剩余元素，如果有就返回true，没有就返回false。
next方法指向下一个元素，并返回上一个元素。这个方法唯一的问题就是可能并没有下一个元素，当并没有下一个元素时，该方法将抛出 NoSuchElementException.所以为了保证每一次next都没有问题，那么应该预先用hasNext（）方法判断是否有剩余元素。
remove用于删除上一个元素，这个方法依赖于next方法，调用一次next方法后，才能使用remove方法，否则就会抛出IllegalStateException。因为最开始并不存在上一个元素，所以必须调用next方法，其次当调用一次remove方法后，上一个元素已经被删掉了，不存在上一个元素，所以必须调用next方法。
还需注意的是，获取迭代器之后，如果修改集合的结构（比如添加元素，删除元素等,当然除了迭代器的remove方法除外），然后再使用迭代器遍历，则会出现java.util.ConcurrentModificationException
List<String> arr = new ArrayList<>(); arr.add("1"); arr.add("2"); arr.add("3"); Iterator<String> iterator = arr.iterator(); // arr.remove(2); wrong code // arr.add("4"); wrong code while (iterator.hasNext()){ System.out.println(iterator.next()); }这也是为什么不能在foreach循环中轻易修改集合结构的原因。
自己定义可遍历的集合的话，比如自定义ArrayList，必须实现Iterable接口和需要一个Iterator的实现类。这里需要知道的是上面提到三个异常``NoSuchElementException,IllegalStateException,ConcurrentModificationException`都是非受检异常，你自己处理不处理其实无所谓，为了规范还是自己处理一下。
下面的代码仿照ArrayList来写的，主要方法如下所示
MyArrayList
package com.lordbao.iterator.MyArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.function.Consumer; /** * @Author Lord_Bao * @Date 2020/9/3 8:40 * @Version 1.0 */ public class MyArrayList<T> implements Iterable<T> { //表示数组的元素个数 也代表下一个默认待插入的位置的下标 private int size; //默认容量为10 private static final int DEFAULT_CAPACITY = 10; //空数组，无参构造函数调用，或是初始化容量为0时，将是下面这个数组 private static final Object[] EMPTY_ELEMENTDATA = {}; //MyArrayList 的 底层数据结构 数组 private Object[] elementData; public MyArrayList() { elementData = EMPTY_ELEMENTDATA; } public MyArrayList(int initialCapacity) { if (initialCapacity == 0) elementData = EMPTY_ELEMENTDATA; else if (initialCapacity > 0) elementData = new Object[initialCapacity]; else throw new IllegalArgumentException("InitialCapacity " + initialCapacity + " can't be below 0"); } public boolean add(T t) { return add(size, t); } public boolean add(int index, T t) { addIndexCheck(index); ensureCapacity(); //刚好在size处插入元素 也满足 for (int j = size - 1; j >= index; j--) { elementData[j + 1] = elementData[j]; } elementData[index] = t; size++; return true; } public T getLast() { return get(size - 1); } public T get(int index) { getOrRemoveIndexCheck(index); return (T) elementData[index]; } public T remove(int index) { getOrRemoveIndexCheck(index); T result = (T) elementData[index]; for (int i = index + 1; i <= size - 1; i++) { elementData[i - 1] = elementData[i]; } elementData[size - 1] = null; size--; return result; } public T removeLast() { return remove(size - 1); } public boolean isEmpty(){ return size==0; } public int size(){ return size; } private void getOrRemoveIndexCheck(int index) { if (index < 0 || index >= size) throw new IllegalArgumentException("Index " + index + " out of bounds"); } private void addIndexCheck(int index) { if (index < 0 || index > size) throw new IllegalArgumentException("Index " + index + " out of bounds"); } private void ensureCapacity() { //如果是空数组,就扩容 if (elementData == EMPTY_ELEMENTDATA) { elementData = new Object[DEFAULT_CAPACITY]; } else { //检查容量是否充足 ensureCapacity(size); } } private void ensureCapacity(int size) { //如果数组存储的元素达到数组容量则进行扩容 if (size >= elementData.length) expandCapacity(); } private void expandCapacity() { //扩容2倍 int newCapacity = elementData.length << 2; elementData = Arrays.copyOf(elementData, newCapacity); } @Override public Iterator<T> iterator() { return new Itr(); } private class Itr implements Iterator<T> { int pointer; int lastRet=-1;//上一个被返回的元素坐标，如果没有就是-1 @Override public boolean hasNext() { return pointer < size; } @Override public T next() { if (pointer>=size) throw new NoSuchElementException(); //记录最近一次返回的元素坐标 lastRet = pointer; return (T) elementData[pointer++]; } @Override public void remove() { if (lastRet <0) throw new IllegalStateException(); MyArrayList.this.remove(lastRet); pointer = lastRet; //这样的目的是下一次next以后，pointer仍然指向正确 lastRet = -1;//一次删除之后，必须next，这样才能修改lastRet来继续删除下一个元素 } @Override public void forEachRemaining(Consumer<? super T> action) { //暂时不写 } } }测试代码
package com.lordbao.iterator.MyArrayList; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * @Author Lord_Bao * @Date 2020/9/3 8:41 * @Version 1.0 */ public class Main { public static void main(String[] args) { MyArrayList<String> arr = new MyArrayList<>(1); arr.add("h"); arr.add("i"); Iterator<String> iterator = arr.iterator(); while (iterator.hasNext()) { String next = iterator.next(); System.out.println(next); } //增强for循环 等价于上面的while for (String s : arr) { System.out.println(s); } } }结果
h
i
h
i
测试上面部分方法
package com.lordbao.collection; /** * @Author Lord_Bao * @Date 2020/9/1 10:50 * @Version 1.0 */ import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.Objects; /** * 用于测试Collection接口常见的方法 * * boolean add(E e) * boolean remove(Object o) * boolean contains(Object o) * void clear() * int size() * boolean isEmpty() * Object[] toArray() * iterator<E> iterator() */ public class Main1 { public static void main(String[] args) { Collection<Man> arr = new ArrayList<>(); //add arr.add(new Man("jack")); arr.add(new Man("rose")); arr.add(new Man("loki")); arr.add(new Man("jenny")); //remove 底层会调用equals arr.remove(new Man("loki")); //iterator Iterator<Man> iterator = arr.iterator(); while (iterator.hasNext()){ Man man = iterator.next(); System.out.println(man); } //contains 底层会调用equals System.out.println(arr.contains(new Man("jack"))); //toArray Object[] objects = arr.toArray(); System.out.println(objects[0]); //clear size isEmpty arr.clear(); System.out.println(arr.size()); System.out.println(arr.isEmpty()); } } class Man{ private String name; public Man() { } public Man(String name) { this.name = name; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Man man = (Man) o; return Objects.equals(name, man.name); } @Override public String toString() { return "Man{" + "name='" + name + '\'' + '}'; } }这里需要主要的是contains和remove底层会调用equals方法,怎么判断元素是否相等需要自己去拿捏。
测试结果
Man{name=‘jack’} Man{name=‘rose’} Man{name=‘jenny’} true Man{name=‘jack’} 0 true
List继承自Collection，它的元素的最大特点是有序可重复，即存储的顺序和遍历的顺序是相同的，重复指的是相同的元素可以重复存储。
List最常见的实现类是ArrayList和LinkedList以及Vector。ArrayList和Vector的底层都是数组，前者不是线程安全的，后者是线程安全的，但是Vector效率比较低下，并且已经有新的方式保证线程安全，所以ArrayList应用更加广泛。
测试代码
package com.lordbao.list; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * @Author Lord_Bao * @Date 2020/9/1 16:18 * @Version 1.0 */ public class Main { public static void main(String[] args) { List<String> list = new ArrayList<>(); // add(int index , E e) list.add(0,"world"); list.add(0,"the"); list.add(0,"hello"); //打印 list.forEach(System.out::println); System.out.println("---------------------------------"); //set(int index,E e) list.set(0,"hi"); list.forEach(System.out::println); System.out.println("---------------------------------"); //E get(int index) System.out.println(list.get(0)); // E remove(int index) System.out.println(list.remove(0)); // indexOf lastIndexOf System.out.println(list.indexOf("the")); System.out.println(list.lastIndexOf("the")); } }结果
hello the
world
hi the
world
hi hi 0 0
ArrayList的底层是数组，数组的特点就是随机访问快，增删效率较低（涉及移动大量元素），而且数组分配的空间是连续的，当数组大到一定程度的时候，就要考虑存储问题。
ArrayList的底层是数组，但元素增加的时候，就要考虑扩容问题，而扩容就会涉及移动元素，所以怎么扩容也是一个很重要的问题。
LinkedList底层是双向链表，双向链表的特单是增删新的节点效率高，但是访问元素的效率就要低一点。在空间存储上，双向链表的节点不是连续的。
Vector底层也是数组，它是线程安全的，但是效率比较低，事实上，可以通过Collections工具类，让ArrayList变得线程安全.List<String> list = Collections.synchronizedList(new LinkedList<>());。
Set没有特别的方法，这里不讲。
HashSet底层采用的是HashMap。参见HashMap
TreeSet底层采用的是TreeMap。参见TreeMap
Map以键值对的形式存储数据，它的键部分就是Set，无序不可重复。
常见的方法测试如下
package com.lordbao.map; import java.util.*; /** * @Author Lord_Bao * @Date 2020/9/2 8:09 * @Version 1.0 */ /** * 测试常见的方法 */ public class Main { public static void main(String[] args) { Map<Integer,String> map =new HashMap<>(); //存 map.put(1,"hello"); map.put(2,"jsjsis"); map.put(3,"the"); map.put(4,"world"); //取 System.out.println(map.get(1)); //删 System.out.println(map.remove(2)); //检查是否包含 key 和 value System.out.println(map.containsKey(1)); System.out.println(map.containsValue("hello")); //获得Key部分 并遍历 Set<Integer> integerSet = map.keySet(); for (Integer integer : integerSet) { System.out.println(integer); } //获得values部分 并遍历 Collection<String> values = map.values(); for (String s:values){ System.out.println(s); } // k 和 v封装成一个集合 Set<Map.Entry<Integer, String>> set = map.entrySet(); for (Map.Entry<Integer,String> node:set){ System.out.println("key="+node.getKey()+",value="+node.getValue()); } //清空 查看map元素个数 查看map是否为空 map.clear(); System.out.println(map.size()); System.out.println(map.isEmpty()); } }HashMap的底层数据结构是哈希表，哈希表是数组和链表的产物。下面重点说HashMap的两个方法
get（Object key） ，put（K key，V value）为什么HashMap的Key是不可重复的呢？
因为每次调用put方法的时候，底层会调用Key的hashcode方法，然后计算出hash值，最后再通过哈希算法获得数组的下标，如果下标的元素是null，那么证明没有值存储，那么Key 和Value封装成头结点放在这个下标处。如果下标的元素不是null，那么就会遍历该下标下的链表，调用equals方法，如果都为false，则将Key 和Value封装成结点放在链表末尾，否则证明有重复Key存在，不执行put操作。
get方法的原理是类似的，计算出数组下标，如果下标处的元素为null，说明没有值，返回null，否则沿着链表一次调用Key的equals方法进行判断，如果都为false，则返回null。
综上所述，HashMap的不可重复的原因是底层调用了equals方法，保证Key不存在重复，而下标的计算实际是过滤了很多不满足条件的节点。
为什么说HashMap的Key是无序的呢？
其实存储Key的过程是比较复杂的，要经过运算，这个存储的过程是无序的，而取值是有一定顺序的，比如从每个数组元素的的链表进行遍历。存储无序，取值有序，就会照成存储值的时候是一种顺序，取值的时候是另一种顺序。
终上所述，如果要让HashMap发挥作用，那么Key部分就必须要合理重写equals和hashcode方法。
Properties继承自HashTable，Hashtable的底层是哈希表，类似于ArrayList和Vector的关系，HashTable是线程安全的，而HashMap不是线程安全的，不过可以通过下面的方法，使得HashMap是线程安全的。
Map<String,String> map= new HashMap<>(); map = Collections.synchronizedMap(map);Proerties的Key和Value都是存储String，该类常用来读取以键值对存储的配置文件。
TreeMap的底层是二叉树，这部分数据结构不熟悉，有时间去学习和复习。TreeMap的Key部分是TreeSet，这个集合也是无序不可重复，不可重复的原因不清楚，猜测是进行了equals判断，无序是因为存储数据的时候依赖的是二叉树，取出数据的时候是大小有序的。
使用TreeMap，就需要保证Key部分实现了Comparable接口，或者是new TreeMap集合的时候，传入一个实现了Comparator接口的实现类。
下面以TreeSet为例，按照Worker工资由高到低，同工资按照姓氏升序进行排序。
package com.lordbao.map; import java.util.*; /** * @Author Lord_Bao * @Date 2020/9/2 14:06 * @Version 1.0 */ public class TestTreeSet { public static void main(String[] args) { //方法1 Set<Worker> set = new TreeSet<>(); set.add(new Worker("Adams",1000)); set.add(new Worker("Athens",1000)); set.add(new Worker("Bob",1200)); for (Worker worker : set){ System.out.println(worker); } System.out.println(""); //方法2(可以使用Lambda表达式) Set<Worker> set1 = new TreeSet<>(new Comparator<Worker>() { @Override public int compare(Worker o1, Worker o2) { if (o1 == o2) return 0; if (o1 == null) return -1; if (o2==null) return 1; if (o1.getSalary() == o2.getSalary()) return o1.getName().compareTo(o2.getName()); return o2.getSalary() -o1.getSalary(); } }); set1.add(new Worker("Adams",1000)); set1.add(new Worker("Athens",1000)); set1.add(new Worker("Bob",1200)); for (Worker worker : set1){ System.out.println(worker); } } } class Worker implements Comparable<Worker>{ private String name=""; private int salary=0; @Override public String toString() { return "Worker{" + "name='" + name + '\'' + ", salary=" + salary + '}'; } public Worker() { } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getSalary() { return salary; } public void setSalary(int salary) { this.salary = salary; } public Worker(String name, int salary) { this.name = name; this.salary = salary; } //按照工资降序排列，工资相同，名字升序排列 @Override public int compareTo(Worker o) { if (o==null) return 1; if (salary == o.salary) return name.compareTo(o.name); return o.salary-salary; } }结果
Worker{name=‘Bob’, salary=1200} Worker{name=‘Adams’, salary=1000} Worker{name=‘Athens’, salary=1000}
Worker{name=‘Bob’, salary=1200} Worker{name=‘Adams’, salary=1000} Worker{name=‘Athens’, salary=1000}
集合这一部分，大概分为Collection和Map，根据实际情况去选用合适的集合。这部分的数据结构有些不熟悉，有些熟悉的也模棱两可的，所以数据结构还需要加强。
