一、java集合类的整体继承关系

image.png

可以看出java集合的顶层接口分两类：Collection，Map
两个工具类：Collections，Arrays
Collection接口中定义了15种方法：

image.png

1.8之后还新增了
Stream<E> stream()
Stream<E> parallelStream()
stream与parallelStream可以理解为一种高级版的Iterator。基于stream的函数式变成可以让程序变的更简洁。
下面是一个获取list集合中字符串长度大于4的程序，分别比较了三种方式普通的，基于stream及parallelStream的运行比较

public static void main(String[] args){
        List<String> handles = new ArrayList<>();
        for (int i= 0;i<2000000;i++){
            List<String> lists = Arrays.asList(new String[]{"abcdsd","bcd","efgdddd","你是谁啊啊啊啊啊","b你爸的加拉水电费"});
            handles.addAll(lists);
        }

        long start0 = System.currentTimeMillis();
        List<String> result0 = new ArrayList<>();
        for (int i=0; i<handles.size(); i++){
            if (handles.get(i).length() > 4){
                result0.add(handles.get(i).substring(1));
            }
        }
        long end0 = System.currentTimeMillis();
        System.out.println("noStream运行时间" + (end0-start0)); //2890


        long start1 = System.currentTimeMillis();
        List<String> result = handles.stream().filter(e->e.length() > 4).map(e->e.substring(1)).collect(toList());
        long end1 = System.currentTimeMillis();
        System.out.println("stream运行时间：" + (end1-start1));//2899

        long start2 = System.currentTimeMillis();
        handles.parallelStream().filter(e->e.length() > 4).map(e->e.substring(1)).collect(toList());
        long end2 = System.currentTimeMillis();
        System.out.println("parallelStream" + (end2-start2));//2500
    }

nostream与stream速度相当，parallelStream速度要比

Map接口与Collection接口地位相同，都是根接口，Map中提供了3个角度来分析Map
Set<K> keySet():所有key的集合
Collections<V> values()：所有value的集合
Set<Map.Entry<k,v>> entrySet()：key和value的集合，
需要遍历map集合时建议使用第三种方式，因为这种方式是构造map集合的方式，最节省时间，第一种方式获取key，value需要遍历2次。第二种方式只能获取value的值，它的速度与entry的速度应该差不多。
阿里编程规范中遍历Map的key-Value对时使用EntrySet()的方式

二、Set、List、Map的几种常用的实现类及注意事项

1、List接口是一个元素有序的、可以重复、可以为 null 的集合，常用的实现类，ArrayList，LinkedList这两个实现类的底层的存储结构，ArrayList采用的是数组结构，

image.png

LinkedList采用的是双向链表结构。

image.png

下面是ArrayList及LinkedList的add、set、及remove操作
1、ArrayList

public void add(int index,E element){ 
    /*检查下标是否越界，代码不在拷贝*/ 
    //若需要扩容，则增大底层数组的长度 
    ensureCapacity(size + 1); 
    //给index下标之后的元素（包括当前元素）的下标加1，空出index位置（将elementData从index起始，复制到index+1的职位 
    System.arraycopy(elementData,index,elementData,index + 1,size - index); 
    //赋值index位置元素 
    elementData[index] = element; 
    //列表的长度+1 
    size++; 
} 

注：这里ArrayList会进行扩容判断，如果需要扩容就会以当前容量的1.5倍进行扩容。在用浅拷贝的方式对数组元素进行后移。
也是由于这个原因，阿里的开发手册中有了下面这条建议。

image.png

public E remove(int index){ 
    //下标校验 
    RangeCheck(index); 
    //修改计数器+1 
    modCount++; 
    //记录要删除的元素 
    E oldValue = (E)elementData(index); 
    //有多少个元素向前移动 
    int numMoved = size - index - 1; 
    if(numMoved > 0) 
        //index后的元素向前移动一位 
        System.arraycopy(elementData,index + 1,elementData,index,numMoved); 
    //列表长度减1，并且最后一位设为null 
    elementData[--size] = null; 
    //返回删除的值 
    return oldValue; 
} 

这是arrayList的删除操作，同样需要对数组元素进行部分移动。

与之对应的LinkedList的操作如下：

public void add(int index,E element){ 
    addBefore(element,(index==size?header:entry(index))); 
} 

private Entry<E> addBefore(E e,Entry<E> entry){ 
    //组装一个新的节点，previous指向原节点的前节点，next指向原节点 
    Entry<E> newEntry = new Entry<E>(e,entry,entry.previous); 
    //前节点的next指向自己 
    newEntry.previous.next = newEntry; 
    //后节点的previous指向自己 
    newEntry.next.previous = newEntry; 
 
    //长度+1 
    size++; 
    //修改计数器+1 
    modCount ++; 
 
    return newEntry; 
} 

private E remove(Entry<E> e){ 
    //取得原始值 
    E result = e.element; 
    //前节点next指向当前节点的next 
    e.previous.next = e.next; 
    //后节点的previouse指向当前节点的previous 
    e.next.previous = e.previous; 
 
    //置空当前节点的next和previous 
    e.next = e.previous= null; 
    //当前元素置空 
    e.element = null; 
 
    //列表长度减1 
    size --; 
    //修改计数器+1 
    modCount++; 
 
    return result; 
} 

结论：在数据需要进行大量删除及新增的时候，LinkedList的速度要比ArrayList的快很多建议使用ArrayList，在数据查询及修改指定元素值时，ArrayList速度要比LinkedList速度快。
注意：在使用ArrayList的sublist()方法时需要注意，不能将sublist()集合强转成ArrayList否则会报java.util.RandomAccessSubList cannot be cast to java.util.ArrayList异常，因为Sublist这个内部类没有继承ArrayList

public void test(){
 List<String> items = Arrays.asList(new String[]{"a","b","c"});
      List<String> results = new ArrayList<>();
      results.addAll(items);
      List<String> sublist = results.subList(0,3);
      sublist.remove(1);
      for (String str : results){
          System.out.println(str);
      }
}

最后输出的结果是a,c,因此asList()方法并没有创建新的集合，还是引用的原来的内存。

2、set是一种无序不可重值可以为null集合，它的实现类有hashSet及LinkedHashSet，当需要对元素进行去重存储时，可以选择set集合。

3、hashMap:Node<K,V> table, Set<Map.Entry<K,V>> entrySet
传统hashMap的缺点：它的存储结构是数组+链表的形式，当大量的元素hash值相同时会被放入同一个桶中，此时的就相当于一个单链表查找时间复杂度为o(n).

java1.8之前hashMap的存储使用的是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。在1.8之后采用红黑树来优化这个问题查找时间复杂度为（Ologn），在1.8中hashmap的存储的具体过程在链表的长度小于8时任然采用之前的数据接口当长度大于8是采用红黑树结构。红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则可以保证红黑树结构在插入、删除、查找时的最坏时间复杂度为 O(logn)。（红黑树的详细介绍https://blog.csdn.net/u011240877/article/details/53329023）

image

原先的链表节点：

static class Node<K,V> implements Map.Entry<K,V> {
    //哈希值，就是位置
    final int hash;
    //键
    final K key;
    //值
    V value;
    //指向下一个几点的指针
    Node<K,V> next;
    //...
}

jdk1.8中新增的红黑树结构

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

加入红黑树之后的整个hashMap的put操作

image.png

3、被忽略的Set与Map的联系：
Set代表的是一种集合元素无序，集合元素不可重复的集合，Map则代表一种由多个Key-Value对组成的集合，Map集合类似于传统的关联数组。表面上看，Map和Set毫无关联，但其实Map和Set之间有莫大的关联，可以说，Map是Set的扩展。
Set及Map的继承体系

image.png

这张图可以明显地看出Set与Map有着极其相似的继承体系。
实际上
Map的key是无序的不能重复的，所以Map的所有key的集合实际上就是一个Set集合，事实上Map中的keySet方法也是这样实现的
从Set到Map，如果将（key-value）看做一个整体，将Entry放入到Set中，实际上Set就转化成了Map集合。
利用Set实现一个Map集合就变得很简单了
1、定义一个实体类存储k-v

public class SimpleEntry<K,V> implements Map.Entry<K,V>,Serializable {
    private K key;
    private V value;

    public SimpleEntry(K key,V value){
        this.key = key;
        this.value = value;
    }
    public SimpleEntry(Map.Entry<? extends K,? extends V> entry){
        this.key = entry.getKey();
        this.value = entry.getValue();
    }
    @Override
    public K getKey() {
        return key;
    }

    @Override
    public V getValue() {
        return value;
    }

    @Override
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object object){
        if(object == this){
            return true;
        }
        if(object.getClass() == SimpleEntry.class){
            SimpleEntry se = (SimpleEntry) object;
            return se.getKey().equals(getKey());
        }
        return  false;
    }
    public int hashCode(){
       return  key == null?0:key.hashCode();
    }

    @Override
    public String toString() {
        return key+"="+value;
    }
}

2、继承hashSet实现一个hashMap2

public class HashMap2<K,V> extends HashSet<SimpleEntry<K,V>> {
    @Override
    public void clear() {
        super.clear();
    }
     //判断是否包含某个key
    public boolean containsKey(K key){
          return super.contains(new SimpleEntry<K, V>(key,null));
    }
    //判断是否包含某个value
    public boolean containsValue(V value){
      for(SimpleEntry<K,V> se :this){
         if(se.getValue().equals(value)){
              return true;
          }
      }
        return false;
    }
    //根据Key取出Value
    public V get(K key){
           for(SimpleEntry<K,V> se:this){
               if(se.getKey().equals(key)){
                   return se.getValue();
               }
           }
        return null;
    }
    //存放入该Map中
    public V put(K key,V value){
       add(new SimpleEntry<K, V>(key,value));
        return value;
    }
    //存放一个Map的key-value对放入该Map中
    public void putAll(Map<? extends K,? extends V> map){
       for(K key:map.keySet()){
           add(new SimpleEntry<K, V>(key,map.get(key)));
       }
    }
    //根据指定key删除指定key-value对
    public V removeEntry(K key){
       for(Iterator<SimpleEntry<K,V>> it = this.iterator();it.hasNext();){
         SimpleEntry<K,V> en = it.next();
           if(en.getKey().equals(key)){
               V v = en.getValue();
               it.remove();
               return  v;
           }
       }
        return null;
    }
    public int size(){
        return super.size();
    }
}

最后这是Map中实现类是否安全，能否键值为空的一个比较
具体的线程安全的实现细节，有兴趣的可以自己看一下，这里没有做总结

image.png