集合类

[TOC]

java 提供三种集合：

List：一种有序列表的集
Set：一种保证没有重复元素的集合
Map：一种通过键值（key-value）查找的映射表集合

Java访问集合总是通过统一的方式——迭代器（Iterator）来实现， 它最明显的好处在于无需知道集合内部元素是按什么方式存储的。
典型的用法如下：
 

   Iterator it = collection.iterator(); //获得一个迭代子
                while(it.hasNext()) {

        Objectobj it= it.next(); //得到下一个元素
        } 
复制代码

一.List

List有两种： 一种是基本的ArrayList其优点在于随机访问元素，另一种是更强大的LinkedList它并不是为快速随机访问设计的。
实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

LinkedList类:

LinkedList实现了List接口，允许null元素。对顺序访问进行了优化，向List中间插入与删除的开销并不大，随机访问则相对较慢。还具有下列方法：addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()这些方法(没有在任何接口或基类中定义过)，这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意：LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：List list = Collections.synchronizedList(newLinkedList(…));

ArrayList类：

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

import java.util.*;
 
public class Test{
 public static void main(String[] args) {
     List<String> list=new ArrayList<String>();
     list.add("Hello");
     list.add("World");
     list.add("HAHAHAHA");
     //第一种遍历方法使用 For-Each 遍历 List
     for (String str : list) {            //也可以改写 for(int i=0;i<list.size();i++) 这种形式
        System.out.println(str);
     }
 
     //第二种遍历，把链表变为数组相关的内容进行遍历
     String[] strArray=new String[list.size()];
     list.toArray(strArray);
     for(int i=0;i<strArray.length;i++) //这里也可以改写为  for(String str:strArray) 这种形式
     {
        System.out.println(strArray[i]);
     }
     
    //第三种遍历 使用迭代器进行相关遍历
     
     Iterator<String> ite=list.iterator();
     while(ite.hasNext())//判断下一个元素之后有值
     {
         System.out.println(ite.next());
     }
 }
}
复制代码

Vector类：

Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和 ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

Stack类

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和 pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

List转化成数组

Integer[] array = list.toArray(new Integer[list.size()]);
Integer[] array = list.toArray(Integer[]::new);

数组转化成List

可以使用Arrays.asList(T…)方法把数组转换成List。

List对象的比较

List内部并不是通过==判断两个元素是否相等，而是使用equals()方法判断两个元素是否相等。

在List中查找元素时，List的实现类通过元素的equals()方法比较两个元素是否相等，因此，放入的元素必须正确覆写equals()方法，Java标准库提供的String、Integer等已经覆写了equals()方法；

编写equals()方法可借助Objects.equals()判断。

如果不在List中查找元素，就不必覆写equals()方法

public class ListCompare {
    @Test
    public void test() {
        List<Person> list = Arrays.asList(
                new Person("Xiao", "Ming", 18),
                new Person("Xiao", "Hong", 25),
                new Person("Bob", "Smith", 20)
        );
        boolean exist = list.contains(new Person("Bob", "Smith", 20));
        System.out.println(exist ? "测试成功!" : "测试失败!");
    }


    class Person {
        String firstName;
        String lastName;
        int age;

        public Person(String firstName, String lastName, int age) {
            this.firstName = firstName;
            this.lastName = lastName;
            this.age = age;
        }

        public boolean equals(Object o) {
            if (o instanceof Person) {
                Person p = (Person) o;
                return this.age == p.age && Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName);
            }
            return false;
        }
    }
}

复制代码

二、Map接口

请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

        方法put(Object key, Object value)添加一个”值”(想要得东西)和与”值”相关的”键”(key)(使用它来查找)。方法get(Object key)返回与给定”键”相关联的”值”。可以用containsKey()和containsValue()测试Map中是否包含某个”键”或”值”。

HashTable类

Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。Hashtable是同步的，线程安全。
添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作使用Java的hashCode来实现，时间开销为常数。

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，           如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。

  如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。

public class MapCompare {
    @Test
    public void test() {
        Map<Person, String> map = new HashMap<>();
        map.put(new Person("xiao", "Ming", 18), "nice");
        map.put(new Person("xiao", "hong", 20), "hong");

        System.out.println("get:"+map.get(new Person("xiao", "hong", 20)));
    }


    class Person {
        String firstName;
        String lastName;
        int age;

        public Person(String firstName, String lastName, int age) {
            this.firstName = firstName;
            this.lastName = lastName;
            this.age = age;
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Person) {
                Person p = (Person) o;
                return this.age == p.age && Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(firstName, lastName, age);
        }
    }
}
复制代码

HashMap类

        HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

import java.util.*;
 
public class Test{
     public static void main(String[] args) {
      Map<String, String> map = new HashMap<String, String>();
      map.put("1", "value1");
      map.put("2", "value2");
      map.put("3", "value3");
      
      //第一种：普遍使用，二次取值
      System.out.println("通过Map.keySet遍历key和value：");
      for (String key : map.keySet()) {
       System.out.println("key= "+ key + " and value= " + map.get(key));
      }
      
      //第二种
      System.out.println("通过Map.entrySet使用iterator遍历key和value：");
      Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
      while (it.hasNext()) {
       Map.Entry<String, String> entry = it.next();
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
      }
      
      //第三种：推荐，尤其是容量大时
      System.out.println("通过Map.entrySet遍历key和value");
      for (Map.Entry<String, String> entry : map.entrySet()) {
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
      }
    
      //第四种
      System.out.println("通过Map.values()遍历所有的value，但不能遍历key");
      for (String v : map.values()) {
       System.out.println("value= " + v);
      }
     }
}

复制代码

如果作为key的对象是enum类型，那么，还可以使用Java集合库提供的一种EnumMap，它在内部以一个非常紧凑的数组存储value，并且根据enum类型的key直接定位到内部数组的索引，并不需要计算hashCode()，不但效率最高，而且没有额外的空间浪费。

我们以DayOfWeek这个枚举类型为例，为它做一个“翻译”功能：

public class Main {
    public static void main(String[] args) {
        Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
        map.put(DayOfWeek.MONDAY, "星期一");
        map.put(DayOfWeek.TUESDAY, "星期二");
        map.put(DayOfWeek.WEDNESDAY, "星期三");
        map.put(DayOfWeek.THURSDAY, "星期四");
        map.put(DayOfWeek.FRIDAY, "星期五");
        map.put(DayOfWeek.SATURDAY, "星期六");
        map.put(DayOfWeek.SUNDAY, "星期日");
        System.out.println(map);
        System.out.println(map.get(DayOfWeek.MONDAY));
    }
}
复制代码

TreeMap类

        基于红黑树数据结果的实现。查看”键”或”键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。

SortedMap在遍历时严格按照Key的顺序遍历，最常用的实现类是TreeMap；
作为SortedMap的Key必须实现Comparable接口，或者传入Comparator；
要严格按照compare()规范实现比较逻辑，否则，TreeMap将不能正常工作。

public class TreeMapTest {
    @Test
    public void test() {
//        Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
//            public int compare(Student p1, Student p2) {
////                if (p1.score == p2.score) {
////                    return 0;
////                }
////                return p1.score > p2.score ? -1 : 1;
//                return -Integer.compare(p1.score, p2.score);
//            }
//        });
        Map<Student, Integer> map = new TreeMap<>();

        map.put(new Student("Tom", 77), 1);
        map.put(new Student("Bob", 66), 2);
        map.put(new Student("Lily", 99), 3);
        for (Student key : map.keySet()) {
            System.out.println(key);
        }
        System.out.println(map.get(new Student("Bob", 66))); // null?
    }

    static class Student implements Comparable {
        public String name;
        public int score;

        Student(String name, int score) {
            this.name = name;
            this.score = score;
        }

        public String toString() {
            return String.format("{%s: score=%d}", name, score);
        }

        @Override
        public int compareTo(Object o) {
            Student student = (Student) o;
            return -Integer.compare(this.score, student.score);
        }
    }
}

复制代码

WeakHashMap类

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

三、Set接口

        Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2) = false，因此Set最多有一个null元素。

        很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。

        请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

public class Main {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("pear");
        set.add("orange");
        for (String s : set) {
            System.out.println(s);
        }
    }
}

banana
orange
apple
pear
复制代码

HashSet类：

HashSet是基于HashMap实现的，HashSet底层采用HashMap来保存所有元素。为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。hashCode和equal()是HashMap用的，因为无需排序所以只需要关注定位和唯一性即可。hashCode用来计算hash值，hash值是用来确定hash表索引，hash表中的一个索引存放的是一张链表，所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry。

        put时，如果hash表中没定定位到，就在链表前加一个Entry，如果定位到了，则更换Entry中的value(值)并返回旧value(值)。

        覆写key的hashCode()和equal()时一定要注意，不要把它们和可变属性关联上，否则属性变了之后hashCode会变，equal也会为false，这样在Map中就找不到它了而且这样的对象因为找不到它所以得不到释放，这样就变成了一个无效引用(相当于内存泄漏)。

LinkedHashSet类

HashSet类的子类，具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

TreeSet类

TreeSet是依靠TreeMap来实现的，TreeSet集合类是一个有序集合，它的元素按照升序排序，默认是自然顺序排列，也就是说，TreeSet中的对象元素需要实现Comparable接口。TreeSet与HashSet类一样没有get()方法来获取列表中的元素，所以也只能通过迭代器方法来获取。

由于TreeMap需要排序，所以需要一个Comparable为键值进行大小比较，当然也是用Comparator定位的，Comparator可以在创建TreeMap时指定，这时排序时使用Comparator.compare，如果创建时没有指定Comparator那么就会使用key.compareTo()方法，这就要求key必须实现Comparable接口。

TreeMap是使用Tree数据结构实现的，所以使用compare接口就可以完成定位了。

/**
 * 在聊天软件中，发送方发送消息时，遇到网络超时后就会自动重发，因此，接收方可能会收到重复的消息，在显示给用户看的时候，需要首先去重。请练习使用Set去除重复的消息：
* */
public class TreeSetText {
    @Test
    public void test() {
        List<Message> received = Arrays.asList(
                new Message(1, "Hello!"),
                new Message(2, "发工资了吗？"),
                new Message(2, "发工资了吗？"),
                new Message(3, "去哪吃饭？"),
                new Message(3, "去哪吃饭？"),
                new Message(4, "Bye")
        );
        List<Message> displayMessages = process(received);
        for (Message message : displayMessages) {
            System.out.println(message.text);
        }
    }

    static List<Message> process(List<Message> received) {
        Set messageSet = new TreeSet<>(new Comparator<Message>() {
            @Override
            public int compare(Message o1, Message o2) {
                return Integer.compare(o1.sequence, o2.sequence);
            }
        });

        messageSet.addAll(received);
        return new ArrayList<>(messageSet);
    }

    static class Message {
        public final int sequence;
        public final String text;

        public Message(int sequence, String text) {
            this.sequence = sequence;
            this.text = text;
        }
    }
}

复制代码

Queue接口

 Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。要避免把null添加到队列。

方法	说明	备注
add	增加一个元素	队列已满，抛出IIIegaISlabEepeplian
remove	移除并返回队列头部元素	队列为空，抛出oSuchElementException
element	返回队列头部的元素	队列为空，抛出NoSuchElementException
offer	添加一个元素并返回true	如果队列已满，则返回false
poll	移除并返问队列头部元素	如果队列为空，则返回null
peek	返回队列头部的元素	如果队列为空，则返回null
put	添加一个元素	如果队列满，则阻塞
take	移除并返回队列头部元素	如果队列为空，则阻塞

remove、element、offer、poll、peek其实是属于Queue接口。

注意：Queue队列是不能直接实例化的。原先在java编程中，Queue的实现都是用LinkedList。如：Queue qe = new LinkedList();

LinkedList即实现了List接口，又实现了Queue接口，但是，在使用的时候，如果我们把它当作List，就获取List的引用，如果我们把它当作Queue，就获取Queue的引用，始终按照面向抽象编程的原则编写代码，可以大大提高代码的质量。

// 这是一个List:
List<String> list = new LinkedList<>();
// 这是一个Queue:
Queue<String> queue = new LinkedList<>();
复制代码

注意：此实现不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程结构上修改了该列表，则它必须保证外部同步。(结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改)。这一般通过对自然封装该列表的对象进行同步操作来完成。

Deque
如果把条件放松一下，允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名Deque。

Java集合提供了接口Deque来实现一个双端队列，它的功能是：

• 将元素添加到队尾或队首：addLast()/offerLast()/addFirst()/offerFirst()；
• 从队首／队尾获取元素并删除：removeFirst()/pollFirst()/removeLast()/pollLast()；
• 从队首／队尾获取元素但不删除：getFirst()/peekFirst()/getLast()/peekLast()；
• 总是调用xxxFirst()/xxxLast()以便与Queue的方法区分开；
• 避免把null添加到队列。

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.offerLast("A"); // A
        deque.offerLast("B"); // A <- B
        deque.offerFirst("C"); // C <- A <- B
        System.out.println(deque.pollFirst()); // C, 剩下A <- B
        System.out.println(deque.pollLast()); // B, 剩下A
        System.out.println(deque.pollFirst()); // A
        System.out.println(deque.pollFirst()); // null
    }
}
复制代码

Stack

在Java中，我们用Deque可以实现Stack的功能：

• 把元素压栈：push(E)/addFirst(E)；
• 把栈顶的元素“弹出”：pop()/removeFirst()；
• 取栈顶元素但不弹出：peek()/peekFirst()。

当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。

ArrayBlockingQueue类

一个由数组支持的有界队列。基于数组的阻塞循环队列，先进先出原则对元素进行排序。

LinkedBlockingQueue类

一个由链接节点支持的可选有界队列。基于链表的队列，先进先出排序元素。

PriorityBlockingQueue类

一个由优先级堆支持的无界优先级队列。PriorityBlockingQueue是对PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞队列上put时是不会受阻的。但是由于资源被耗尽，所以试图执行添加操作可能会导致OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元素要具有比较能力。

DelayQueue

一个由优先级堆支持的、基于时间的调度队列。（基于PriorityQueue来实现的）是一个存放Delayed元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的Delayed元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的getDelay(TimeUnit.NANOSECONDS)方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用null元素。

SynchronousQueue

一个利用BlockingQueue接口的简单聚集（rendezvous）机制。SynchronousQueue 类是最简单的。它没有内部容量。它就像线程之间的手递手机制。在队列中加入一个元素的生产者会等待另一个线程的消费者。当这个消费者出现时，这个元素就直接在消费者和生产者之间传递，永远不会加入到阻塞队列中。

总结

Java中的List/Set和Map的区别？

List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector> 。

Set 接口实例存储的是无序的，不重复的数据。List 接口实例存储的是有序的，可以重复的元素。Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>。

Map同样对每个元素保存一份，但这是基于”键”(key)的，Map也有内置的排序，因而不关心元素添加的顺序。如果添加元素的顺序对程序设计很重要，应该使用LinkedHashSet或者LinkedHashMap。

如何选用集合类？

1.要求线程安全，使用Vector、Hashtable

2.不要求线程安全，使用ArrayList, LinkedList, HashMap

3.要求key和value键值，则使用HashMap, Hashtable

4.数据量很大，又要线程安全，则使用Vector

如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。

要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。

尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

数据结构与算法的解度处理 (数组，链表，栈树，树，图)

数据量千级以内可以使用 Sparse 数组 (Key为整数)，ArrayMap (Key 为对象) 虽然性能不如 HashMap ，但节约内存。
ArrayMap采用的是数组+数组的形式，一个数组存储key的hash值，一个数组存储value，所以如果数据较大时，效率相对较低；
HashMap采用的是数组+链表/红黑树的形式，数组存放key的hash值，链表存放值，如果值数量超过8，会转成红黑树.

为什么推荐用SparseArray代替HashMap?

SparseArray三大特点
双数组、删除O(1)、二分查找
为什么省内存？
HashMap 为了避免过多的哈希冲突，引入了负载因子，打个比方，负载因子使用默认值 0.75，这意味着容量达到了 75%，就会开始扩容，也就是必然有 25% 的空间是不存储数据而被浪费的。而 SparseArray 可以把数组利用到最后一个空间。
复杂度为什么这么低？
SparseArray 做了两个优化：
1.引入 DELETE 标记
既然底层使用了数组，数组的缺点是什么？—— 删除数据时需要搬移元素。SparseArray 对数组的删除不做数据搬移，引入 DELETE 标记，以此达到在删除时做到 O(1) 的时间复杂度。
在调用 size()和put()需要扩容时，才去清理 DELETE 标识。
2.优化追加元素
SparseArray 提供了一个 append() 方法，来优化追加的情况。该方法会判断追加的 key 值，是否大于数组中最大的值，如果是则直接追加在数组末尾，否则执行 put() 方法插入 mKey 数组。

因为sparseArray避免了对key的自动装箱（int转成integer），它的内部是采用2个数组来实现的；一个存储key 一个存储value；相对来说，性能更快，内部采用压缩方式节省内存空间；sparseArray代替HashMap的时候最好存储的数量在千量级以下。key必须是int类型，才可以替代hashmap

SparseArray 遍历
方法1. 可以得到key值：

     SparseArray<UserBean> mUserArray = new SparseArray<>();
         //SparseArrayr容器的遍历方法1
        for (int i = 0; i < mUserArray.size(); i++) {
            int key = mUserArray.keyAt(i);
            UserBean user = mUserArray.get(key);
            Log.e("key = " + key, user.toString());
        }
复制代码

方法2. 不需要key值：

     SparseArray<UserBean> mUserArray = new SparseArray<>();
         //SparseArrayr容器的遍历方法2
        for (int i = 0; i < mUserArray.size(); i++) {
            UserBean user = mUserArray.valueAt(i);
            Log.e("没有key值", user.toString());
        }
复制代码

SparseArray中有一些和HashMap中相似的实用方法，比如：

put(int key, E value)
get(int key)
get(int key, E valueIfKeyNotFound)
delete(int key)
removeAt(int index)
keyAt(int index)
valueAt(int index)
等等。
复制代码

android又给封装了SparseIntArray,SparseBooleanArray,SparseLongArray等等，使用方法和SparseArray都大同小异，只要你会使用Map，那么你就会使用SparseArray。

ArrayMap

ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。

添加数据:
public V put(K key, V value)
获取数据:
public V get(Object key)
删除数据:
public V remove(Object key)
特有方法
它和SparseArray一样同样也有两个更方便的获取数据方法：

public K keyAt(int index)
public V valueAt(int index)

总结:
SparseArray和ArrayMap都差不多，使用哪个呢？
假设数据量都在千级以内的情况下：

1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用

2、如果key类型为其它的类型，则使用ArrayMap

CopyOnWriteArrayList:

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。
CopyOnWrite并发容器用于读多写少的并发场景。比如白名单，黑名单等场景。
CopyOnWrite两个缺点：
内存占用问题。因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。
数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。【当执行add或remove操作没完成时，get获取的仍然是旧数组的元素】

并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue使用场景总结

在并发队列上 JDK 提供了两套实现： 一个是以 ConcurrentLinkedQueue 为代表的高性能队列，一个是以 BlockingQueue 接口为代表的阻塞队列。无论哪种都继承自 Queue，并且都是线程安全的，都可以进行并发编程。
适用阻塞队列的好处：多线程操作共同的队列时不需要额外的同步，另外就是队列会自动平衡负载，即那边（生产与消费两边）处理快了就会被阻塞掉，从而减少两边的处理速度差距
当许多线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。
LinkedBlockingQueue 多用于任务队列，并提供了 BlockingQueue 的等待性方法，BlockingQueue 基本都是基于锁实现
ConcurrentLinkedQueue  多用于消息队列，则是基于 CAS 的无锁技术，不需要在每个操作时使用锁，所以扩展性表现要更加优异。

单生产者，单消费者  用 LinkedBlockingqueue
多生产者，单消费者   用 LinkedBlockingqueue
单生产者 ，多消费者   用 ConcurrentLinkedQueue
多生产者 ，多消费者   用 ConcurrentLinkedQueue
leeeyou.gitbooks.io/java-36/con…

ConcurrentLinkedQueue使用：

blog.csdn.net/liyantianmi…
有三个函数需要注意的：
peek()获取元素 不移除头结点
poll() 获取元素并且在队列中移除，如果队列为空返回null
size:
返回此队列中的元素数量。如果此队列包含的元素数大于 Integer.MAX_VALUE，则返回 Integer.MAX_VALUE。需要小心的是，与大多数 collection 不同，此方法不是 一个固定时间操作。由于这些队列的异步特性，确定当前的元素数需要进行一次花费 O(n) 时间的遍历。
注意1：ConcurrentLinkedQueue的.size() 是要遍历一遍集合的，很慢的，所以尽量要避免用size，如果判断队列是否为空最好用isEmpty()而不是用size来判断.
问题1：使用了这个ConcurrentLinkedQueue 类之后是否意味着我们不需要自己进行任何同步或加锁操作了呢？
如果直接使用它提供的函数，比如：queue.add(obj); 或者 queue.poll(obj);，这样我们自己不需要做任何同步。但如果是非原子操作，比如：

if(!queue.isEmpty()) { queue.poll(obj); }
我们很难保证，在调用了isEmpty()之后，poll()之前，这个queue没有被其他线程修改。所以对于这种情况，我们还是需要自己同步： 详见

ConcurrentHashMap并发的HashMap

ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。

ConcurrentHashMap优势是才用锁分段技术，每一个Segment就好比一个自治区，读写操作高度自治，Segment之间互不影响。



ConcurrentHashMap读写过程：
Get方法：
1.为输入的Key做Hash运算，得到hash值。
2.通过hash值，定位到对应的Segment对象
3.再次通过hash值，定位到Segment当中数组的具体位置。

Put方法：
1.为输入的Key做Hash运算，得到hash值。
2.通过hash值，定位到对应的Segment对象
3.获取可重入锁
4.再次通过hash值，定位到Segment当中数组的具体位置。
5.插入或覆盖HashEntry对象。
6.释放锁。

统计ConcurrentHashMap的size个数，怎么解决一致性问题？
ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：
1.遍历所有的Segment。
2.把Segment的元素数量累加起来。
3.把Segment的修改次数累加起来。
4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。
5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。
6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。
7.释放锁，统计结束。

public int size() {
    // Try a few times to get accurate count. On failure due to
   // continuous async changes in table, resort to locking.
   final Segment<K,V>[] segments = this.segments;
    int size;
    boolean overflow; // true if size overflows 32 bits
    long sum;         // sum of modCounts
    long last = 0L;   // previous sum
    int retries = -1; // first iteration isn't retry
    try {
        for (;;) {
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    ensureSegment(j).lock(); // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    if (c < 0 || (size += c) < 0)
                        overflow = true;
                }
            }
            if (sum == last)
                break;
            last = sum;
        }
    } finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}
复制代码

为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。
为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。

mp.weixin.qq.com/s?__biz=MzI…

HashMap?ConcurrentHashMap?相信看完这篇没人能难住

ArrayList和linkedlist

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。

3.对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList.因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

Hashtable和Hashmap

1.历史原因：Hashtable是基于陈旧的Dictionary类的，HashMap是Java1.2引进的Map接口的一个实现。

2.同步性：Hashtable是线程安全的，也就是说是同步的，这个类中的一些方法保证了Hashtable中的对象是线程安全的。而HashMap则是线程异步的，因此HashMap中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用HashMap是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销，从而提高效率。

3.HashMap可以让你将空值作为一个表的条目的key或value，但是Hashtable是不能放入空值的(null)。

HashMap和TreeMap

1.HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

2.在Map中插入、删除和定位元素，HashMap是最好的选择。**但如果你要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。**使用HashMap要求添加的键类明确定义了hashCode()和equals()的实现。这个TreeMap没有调优选项，因为该树总处于平衡状态。

HashSet与TreeSet

HashSet是基于hash算法实现的，性能优于TreeSet。通常使用HashSet，在我们需要对其中元素排序的时候才使用TreeSet。

Iterator(迭代器)的用法

不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。

Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。

例如，如果没有使用Iterator，遍历一个数组的方法是使用索引：for(inti=0;i<array.size();i++) {..get(i)…}

而访问一个链表(LinkedList)又必须使用while循环：while((e=e.next())!=null){…e.data()…}

以上两种方法客户端都必须事先知道集合的内部结构，访问代码和集合本身是紧耦合，无法将访问逻辑从集合类和客户端代码中分离出来，每一种集合对应一种遍历方法，客户端代码无法复用。

更恐怖的是，如果以后需要把ArrayList更换为LinkedList，则原来的客户端代码必须全部重写。

为解决以上问题，Iterator模式总是用同一种逻辑来遍历集合：

for(Iteratorit=c.iterater(); it.hasNext();) { ...}

每一种集合类返回的Iterator具体类型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator，Tree可能返回TreeIterator，但是它们都实现了Iterator接口，因此，客户端不关心到底是哪种Iterator，它只需要获得这个Iterator接口即可，这就是面向对象的威力。

要确保遍历过程顺利完成，必须保证遍历过程中不更改集合的内容（Iterator的remove()方法除外），因此，确保遍历可靠的原则是只在一个线程中使用这个集合，或者在多线程中对遍历代码进行同步。

Collection c=new ArrayList();
c.add("abc");
c.add("xyz");
for(Iterator it=c.iterator();it.hasNext();){
         Strings=(String)it.next();
         System.out.println(s);
}
复制代码

如果你把第一行代码的 ArrayList 换成 LinkedList 或 Vector ，剩下的代码不用改动一行就能编译，而且功能不变，这就是针对抽象编程的原则：对具体类的依赖性最小。

使用Collections

Collections可以对List进行排序。因为排序会直接修改List元素的位置，因此必须传入可变List：

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("pear");
        list.add("orange");
        // 排序前:
        System.out.println(list);
        Collections.sort(list);
        // 排序后:
        System.out.println(list);
    }
}
复制代码

Collections提供了洗牌算法，即传入一个有序的List，可以随机打乱List内部元素的顺序，效果相当于让计算机洗牌：

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i=0; i<10; i++) {
            list.add(i);
        }
        // 洗牌前:
        System.out.println(list);
        Collections.shuffle(list);
        // 洗牌后:
        System.out.println(list);
    }
}
复制代码

Collections还提供了一组方法把可变集合封装成不可变集合：

封装成不可变List：List unmodifiableList(List<? extends T> list)
封装成不可变Set：Set unmodifiableSet(Set<? extends T> set)
封装成不可变Map：Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m)
这种封装实际上是通过创建一个代理对象，拦截掉所有修改方法实现的。我们来看看效果：

public class Main {
    public static void main(String[] args) {
        List<String> mutable = new ArrayList<>();
        mutable.add("apple");
        mutable.add("pear");
        // 变为不可变集合:
        List<String> immutable = Collections.unmodifiableList(mutable);
        immutable.add("orange"); // UnsupportedOperationException!
    }
}
复制代码

集合学习链接（有空看看）：geek-docs.com/java/java-c…