前言

最近在看csnotes复习基础知识，正好写博客记录一下

概览

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

Collection

Collection继承关系

TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

Queue

LinkedList：可以用它来实现双向队列。
PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

List

ArrayList：基于动态数组实现，支持随机访问，线程不安全。数组默认大小为10，每次扩容使用grow()方法扩容一半，也就是原数组大小的1.5倍。每次扩容时使用Array.copyOf()把原数组复制到新数组中。
Vector：和 ArrayList 类似，虽然访问速度较慢，但它是线程安全的。
LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

Collection各种集合的使用方式都差不多，以下用ArrayList作为例子
使用collection类的sort()方法进行排序
sort方法参数包含一个List和Comparator对象，Comparator中compare方法要指定排序规则，返回值若大于0则前者权重比后者大，将数组的前一个对象和后一个对象做交换，小于0则相反，等于0则按存入顺序排序。

@Test
   public void TestList(){
       List<User>list=new ArrayList<>();
       list.add(new User(1,"user1"));
       list.add(new User(2,"user2"));
       list.add(new User(3,"user3"));
       //list排序
       //list.sort(Comparator.comparing(User::getUid));
       Collections.sort(list, new Comparator<User>() {
           @Override
           public int compare(User o1, User o2) {
               return o1.getUid()-o2.getUid();
           }
       });
   }

使用foreach和迭代器进行遍历

@Test
    public void TestList(){
        List<User>list=new ArrayList<>();
        list.add(new User(1,"user1"));
        list.add(new User(3,"user3"));
        list.add(new User(2,"user2"));
        //list的遍历
        //foreach
        for(User user:list){
            System.out.println(user.getUid()+","+user.getUsername());
        }
        //iterator
        Iterator<User> iterator = list.iterator();
        while(iterator.hasNext()){
            User next = iterator.next();
            System.out.println(next.getUid()+","+next.getUsername());
        }
    }

Map

Collection继承关系

TreeMap：基于红黑树实现。
HashMap：基于哈希表实现，线程不安全。内部包含了一个 Entry 类型的数组 table。Entry 存储着键值对。 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry。在jdk1.8中，一个桶存储的链表长度大于等于 8 时会将链表转换为红黑树。
HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

以HashMap作为例子进行Map集合的排序和遍历
将Map转为List进行排序

@Test
   public void TestHashMap(){
       Map<Integer,User>map=new HashMap<>();
       map.put(1,new User(1,"user1"));
       map.put(2,new User(3,"user2"));
       map.put(3,new User(2,"user3"));
       //转list排序:根据key值升序
       ArrayList<Map.Entry<Integer, User>> entries = new ArrayList<>(map.entrySet());
       entries.sort(Comparator.comparing(Map.Entry::getKey));
   }

使用foreach或迭代器进行遍历

@Test
   public void TestHashMap(){
       Map<Integer,User>map=new HashMap<>();
       map.put(1,new User(1,"user1"));
       map.put(2,new User(3,"user2"));
       map.put(3,new User(2,"user3"));
       //转list排序:根据key值升序
       ArrayList<Map.Entry<Integer, User>> entries = new ArrayList<>(map.entrySet());
       entries.sort(Comparator.comparing(Map.Entry::getKey));
       //foreach遍历
       for(Map.Entry<Integer,User> user:map.entrySet()){
   		System.out.println(user.getKey()+","+user.getValue().getUsername());
       }
       //迭代器遍历
       Iterator<Map.Entry<Integer, User>> iterator = map.entrySet().iterator();
       while(iterator.hasNext()){
           Map.Entry<Integer, User> userEntry = iterator.next();
           System.out.println(userEntry.getKey()+","+userEntry.getValue().getUsername());
       }
   }

解决集合线程安全问题

最直接的方法是使用线程安全的集合，如Vector、HashTable、ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentSkipListMap、ConcurrentSkipListSet、ConcurrentLinkedQueue、ConcurrentLinkedDeque等。
使用Collections.synchronizedMap()、Collections.synchronizedList()、Collections.synchronizedCollection()手动给线程不安全的集合加锁。