java集合框架

集合的特点：

• 存储的数据量可变
• 存储的数据类型可变（通过泛型可以添加不同类型的数据）
• 只能存储引用类型
  上述三点都是对应于数组的特点。

集合的分类：

基本接口collection和map
collection实现了Iterable接口，包含list、set、queue
list：可以包含重复元素，取出和放入的顺序一致
set：不包含重复元素，最多包含一个null，取出和放入的顺序不一致
queue：
其中collection继承了Iterable接口，其iterator()方法返回一个迭代器，而该方法乃至迭代器的具体实现在collection的子类中。

迭代器是接口的原因，每种集合的数据结构不一样，其遍历的实现方式不一样，所以抽象为接口，真正的实现是以内部类方式实现。可参见ArrayList中的iterator()方法。这里作为java多态和继承的很好的体现实例

基本方法：

自行查询api，不过有以下注意的点

• addAll(Collection collection)， 实质是将地址值赋值给另一个列表。
• retainAll(Collection collection)，保留与给定集合中共有的元素，如果集合被改变，则返回true。
• toArray() 方法，返回一个包含该集合中所有元素的数组，是新建的数组，原有集合不会对该数组产生引用，所以对集合的操作不会影响该数组。这也是遍历集合的一种解决方案

关键接口：

• Iterator
  Iterator it = list.iterator();
  遍历方法除了常见的while(it.hasNext())，还可以是for循环

for(Iterator it = list.iterator();it.hasNext();) {
        Student s = (Student) it.next();
        //Do something about s;
}

迭代器遍历集合时候，除非使用迭代器的remove方法，不能同时对集合进行增删操作，因为迭代器是基于iterator()方法被创建的，后续对集合的改变不能被同步上。即当多个线程，或多个任务对Collection进行操作时，若其中某一个任务通过Iterator遍历集合时，同时该集合的内容被其他迭代器或者集合自身的方法修改类，会抛出ConcurrentModificationException异常。
此外迭代器中next方法和remove方法是紧紧关联的，remove是删除上次调用next时返回的元素，所以调用remove前没有调用next是非法的。

为什么要使用迭代器？
不同集合的数据结构不一样，比如set，就不能使用for循环。使用迭代器作为接口，在不同集合中根据集合数据结构实现遍历的功能。此外，Iterator访问方式把对不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。再者，Iterator能够让访问者同时遍历并操作列表元素，如使用其remove方法，如果在fori循环中遍历并删除元素，会导致指针偏移。

• List
  有序的collection（存储和取出顺序一致），用户可以控制插入的位置，根据元素索引访问元素，允许重复的元素。

• ListIterator list特有的迭代器，继承了Iterator迭代器，特有逆向遍历功能和其他新特性，但是使用前必须先经过过正向遍历，所以实际用处不大。
• list集合特有用for(int i = 0;i < list.size(); x++)循环功能

根据之前叙说的迭代器遍历数组时修改数组异常——ConcurrentModificationException，一种思路，两种方案，思路就是将修改和遍历合并到一个线程，方案分别是仅仅用迭代器或者仅仅用集合，实践中推荐ListIterator，但修改位置受限（见api），而使用for循环遍历，会有隐藏的风险：

for(int i = 0;i<arrayList2.size(); i++) {
            Student student = (Student)arrayList2.get(i);
            System.out.println(student.getOfficialName());
            System.out.println(arrayList2.size());
            if(student.getOfficialName().equals("hugo")) {
                arrayList2.remove(1);
            }
        }//此时原来数组中下标为2的元素将不能被访问到

List的数据结构

• ArrayList 底层实现是数组，查询快，增删慢，线程不安全，效率高
• Vector 底层实现是数组，查询快，增删慢，线程安全，效率低
• LinkedList 底层实现是链表，查询慢，增删快，线程不安全，效率高

如果有很多元素的增加删除，需要用LinkedList，因为用Arraylist会有大量元素的移动，且会遇到扩容的问题

不建议使用Vector，理由如下

• Vector 对每个方法都加上了锁，损耗性能
• 遍历列表时，为保证同步往往通过将不同的方法整合起来，再加锁。Vector同步单个操作的特点并不能保证多线程操作列表时线程安全，此时其锁就成为了负担
• vector容量达到上限时其容量增量是100%，ArrayList是50%，它更耗内存

LinkedList有添加元素的特有方法，add/get~last/first，removeFirst/Last，Vector也有特有addElement(E obj)、elementAt(int index)、elements()功能，被iterator替代

代码示例： 从列表中抽出重复项

ArrayList oldList = new TestClass("ss").mArrayList;
        oldList.add("aaaa");
        oldList.add("bbbb");
        oldList.add("aaaa");
        oldList.add("gggg");
        oldList.add("cccc");
        oldList.add("cccc");
//solution 1
        ArrayList<String> newList = new ArrayList<>();
        newList.add((String) oldList.get(0));
        for (int i = 0; i < oldList.size(); i++) {
            boolean shouldAdd = true;
            for (int j = 0; j < newList.size(); j++) {
                if(oldList.get(i).equals(newList.get(j))) {
                    shouldAdd = false;
                }
            }
            if(shouldAdd) {
                newList.add((String) oldList.get(i));
            }
        }
// solution 2
Iterator iterator = oldList.iterator();
        while(iterator.hasNext()) {
            String str = (String) iterator.next();
            if(!newList.contains(str)) {
                newList.add(str);
            }
        }
// solution 3
 for (int i = 0; i < oldList.size() - 1; i++) {
            for (int j = i+1; j < oldList.size(); j++) {
                if(oldList.get(i).equals(oldList.get(j))){
                    oldList.remove(j);
                    y--;
                }
            }
        }

去除重复元素的方式
//如何利用Comparator工具去除重复元素？？

用LinkedList创建栈结构的集合

private class MyStack extends LinkedList<String> {
        
        private LinkedList<String> mList;
        
        public MyStack() {
            mList = new LinkedList<>();
        }
        
        public String get() {
            return mList.removeFirst();
        }
        
        public void addFirst(String string) {
            mList.addFirst(string);
        }
        
        public boolean isEmpty() {
            return mList.isEmpty();
        }
    }

• Set
  不包含重复元素，最多包含一个null，取出和放入的顺序不一致
  常见实现类
  HashSet，由一个hash table支持（实际上为hashMap实例），不保证迭代的顺序，特别是不保证每次迭代的顺序都相同。
  hashSet添加元素流程

public boolean add(E var1) {
        return this.map.put(var1, PRESENT) == null;
//PRESENT是全国人民final的同一代表
    }

当你把对象加入HashSet时，HashSet会先计算对象的hashcode值（其实是通过hashCode经过位运算获得的hash值）来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现，直接添加元素。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。不同会添加，这属于处理哈希冲突的范畴；相同，就不能添加。

自定义的hashCode方法必须与equals兼容，如果equals方法返回true，两个对象的hashCode值必须相同。
先看下面这个例子

我们知道不同的对象地址值不同，哪怕其成员完全一致，所以它们的hashCode当然不一样，这是上述所有对象都能被添加的原因。但是如果开发需求类型和成员一致的对象应被视为相同，即equals方法需要被重写，这时候hashCode方法也应该适配。

LinkedhashSet
链表和hash表组成，用于保证数据的有序性和唯一性，底层实现是LinkedHashMap

TreeSet
与散列集类似，但有所改进，能够对元素进行排序，
两种排序方式：
自然排序，子类必须实现Comparable接口，即重写compareTo方法
public class Stuff implements Comparable
自定义的实现了Comparator接口的类,关键在于重写其compare方法
TreeSet<Stuff> treeSet = new TreeSet<Stuff>(new StuffComparator<Stuff>());
具体采用哪种方式取决于构造器
有的类官方设定为Comparable接口实现类，可以进行自然排序，如Integer和String
由此可知，不同于HashMap唯一性主要取决于hashCode和equals方法，TreeMap&TreeSet的排序结果主要取决于子元素的对比方式
TreeSet的实现依赖的是TreeMap，TreeMap是基于红黑树实现的(一种自平衡的二叉树)。

TreeSet的add方法，实现依靠TreeMap的put方法，过程基本是找到根节点，然后二选一排序方式，循环比较最后找到合适插入位置。
获取元素，依靠二叉树里前序遍历方式遍历，
这边截取put方法中的一段

Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);

依赖TreeSet的添加元素机制能够将玩出的骚操作
将子元素的compareTo方法固定返回一个int值，比如-1，就能让元素一直添加到父元素的left，实现一个单项链表结构。

由此可见，TreeSet的本质是一个TreeMap，
有序性依赖：二叉树结构
唯一性依赖：子元素实现的对比方式

实践中偏向哪种方式——个人倾向重写Comparator接口，因为比较逻辑和bean对象分离，且能使用new Comparator的匿名内部类方式让快捷变换比较逻辑。

Queue
实现在尾部添加，在头部删除一个元素；对于双端队列，可以有效

地同时添加或者删除元素，不支持在队列中间增删元素

Map集合

以键值对出现的数据结构，Map集合键是唯一的，其数据结构与键有关，跟值无关。
特有的方法有

containsKey();
containsValue(); 
get(Object key); return the value
Collection<V> values() 
keySet() 
put(K key, V value) 除了添加还可以替换同键的值;
entrySet() ; Returns a Set view of the mappings contained in this map.

运用举例

Map<String, String> map = new HashMap();
        map.put("Jay", "Kun");
        map.put("Jolin", "???");
        map.put("kotlin", "java");
//获取所有键
        Set<String> set = map.keySet();
        for (String str :
                set) {
            System.out.println(str+"");
        }
//获取所有值
Collection<String> collection = map.values();
        for (String str :
                collection) {
            System.out.println(str);
        }
//this set is java.util.HashMap$KeySet
//this collection is java.util.HashMap$Values

//遍历集合
//solution 1
Set<String> set = map.keySet();
        for (String str :
                set) {
            System.out.println(map.get(str));
        }

//solution 2
Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry :
                entries) {
            System.out.println(entry);
        }

关键实现类
HashMap
hash存储优势在于：对于没有实现RandomAccess接口与的集合，当忘记了数据的位置时，想快速查找一个数据很低效。如果不在意元素的顺序，散列表就可以实现快速查找功能。
hashMap底层实现是hash表，实质是元素为链表的数组，我们习惯把数组元素称为桶（比较形象）
hashMap以键值对的方式存储数据，关键是key要保持唯一，而value虽然功能上是我们真正想要的数据，但在该数据结构的存取中根本没有考虑value的存在，可以当做key的一个附属品来使用。

hashMap添加元素的过程
当你把对象加入hashMap时，hashMap会先计算对象的hashcode值（其实是通过hashCode经过位运算获得的hash值）来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现，直接添加元素。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。不同会添加，这属于处理哈希冲突的范畴；相同，就不能添加。

通过为不同对象生成一个整数，成为hash code（该值能快速生成），不同对象拥有不同的散列码。
java中，散列表用链表数组实现，每个链表被称为桶，要想查找对象的位置，首先计算其散列码，然后与桶的总数取余，结果就是元素所在桶的索引。
实际开发中的一个问题：
hash 冲突：有时候，桶会出现被占满的情况，即不同的对象产生了相同的hash值。解决这个问题通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表，相同hash值得不同对象存储在同一个槽位的链表中。

hashSet和HashMap在使用的时候，需要保证添加进去的元素是不可变的，api只能保证元素添加进去的时候是不可变的，但无法控制元素后面是否会变

hashMap的get(Object key)方法参数不是泛型，因为只需要用到equals和hashcode方法。返回值类型是泛型类型

实际开发中的另一个问题：

HashSet<Stuff> stuffs = new HashSet<>();
        Stuff stuff1 = new Stuff(23,"Leonardo");
        Stuff stuff2 = new Stuff(23,"Leonardo");
        Stuff stuff3 = new Stuff(24,"Hugo");
        stuffs.add(stuff1);
        stuffs.add(stuff2);
        stuffs.add(stuff3);
        for (Stuff employee:stuffs) {
            System.out.println(employee.toString());
        }
/**
     * console:
     * Stuff{ID=23, mName='Leonardo'}
     Stuff{ID=24, mName='Hugo'}
     Stuff{ID=23, mName='Leonardo'}
     */

我们知道不同的对象地址值不同，哪怕其成员完全一致，所以它们的hashCode理论上是不一样的，这是上述所有对象都能被添加的原因。但是如果开发需求类型和成员一致的对象应被视为相同，即equals方法需要被重写，这时候hashCode方法也应该适配，否则会出现equals返回true的两个对象hashCode不同。所以我们要同时自定义hashCode和equals方法——

自定义的hashCode方法必须与equals兼容，如果equals方法返回true，两个对象的hashCode值必须相同。
既然如此，hashCode的生成就不在依赖于第一无二的对象，而是考虑到了成员变量，其变化范围就会缩小，缩小就增加了hash冲突的可能性，导致性能下降，所以又要尽量random化hashCode，看下面的一种方案。
** 核心需求：适配equals同时尽量不会出现hash冲突 **

@Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (!(o instanceof Stuff))
            return false;

        Stuff stuff = (Stuff) o;

        if (ID != stuff.ID)
            return false;
        return mName.equals(stuff.mName);
    }

    @Override
    public int hashCode() {
        int result = ID;
        result = 31 * result + mName.hashCode();
        return result;
    }

如果散列码分布均匀，桶的数目也足够大，需要比较的次数就少，hashMap的效率就很高；所以想保证性能，就要指定初始桶的数目，太少会增加散列冲突的可能性，一般建议设置为元素个数的75%~150%，如果散列表太满，就需要再散列。

58e67eae921e4b431782c07444af824e_r.jpg

HashMap和HashTable的区别，前者线程不安全，后者方法用synchronized修饰；前者能够出现一个唯一的null键，且可以有多个键对应null值，但后者中键值不能有null;初始容量大小和每次扩充容量大小的不同.
jdk 1.8实现方式稍有不同
相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间

LinkedHashMap
由一个双向链表和hash表组成，具备HashMap键唯一的特点，同时保证存取顺序一致

TreeMap
依赖一个红黑树实现数据唯一和排序

HashMap和Hashtable的区别

• 线程不安全，效率高vs线程安全，效率低；HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）
• 允许使用最多一个null键和多个null值vs不允许使用null作为键值
• 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
• JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制
  总之，不要使用Hashtable

其他补充

1.遍历集合
使用Lambda表达式遍历集合

public static void main(String[] args) {
        List<String> names = new ArrayList<String>();
        names.add("aa");
        names.add("bb");
        names.add("cc");
        names.forEach(name -> System.out.println(name));
    }

lambda表达式的目标类型是Consumer，并将集合的元素类型作为生成Consumer对象的泛型参数，然后自动将集合元素作为方法参数传递给Consumer对象的accept方法。foreach方法中会调用一个for-each循环。上面这一句代码可以看做是下面代码的极简形式：

Consumer<String> printConsumer= new Consumer<String>() {
            public void accept(String name) {
                System.out.println(name);
            }
        };
        names.forEach(printConsumer);

其等效于手写一个foreach循环，并没有在线程安全性上做改进。
更多内容，可以参考网页https://www.baeldung.com/foreach-java

2、Collections
对集合进行操作的工具类，有对集合进行二分查找和排序的方法。

public static <T> void sort(List<T> list)默认按照自然顺序排序
public static <T> int binarySearch(List<?> list,T key)二分查找
public static <T> T max(Collection<?> coll)最大值
public static void reverse(List<?> list)翻转
public static void shuffle(List<?> list)洗牌，随机置换