66 java集合和泛型_16 _java集合类的原理总结

一、Iterable接口

定义了迭代集合的迭代方法

iterator()
forEach() 对1.8的Lambda表达式提供了支持

二、Collection接口

定义了集合添加的通用方法

int size();
boolean isEmpty();
boolean contains();
boolean add();
boolean addAll();
boolean remove();
 	removeAll();
Object[] toArray(); //等方法（可查看api学习）

三、List接口

• 有序、有下标、元素可重复

E get();
E set();
E indexOf();
int lastIndexOf();
ListIterator listIterator(); //等方法（可查看api学习）

3.1ArrayList类【重点】

1. 线程不安全。

2. 基于一个Object[]数组实现（底层就是一个数组），默认数组是个空数组，可以插入空数据，可以随机访问。如果要查找是否存在某个值，需要遍历数组匹配，时间复杂度是O(n)。由于通过存放的是动态数组，arrayList重写序列化方法readObject和writeObject，只序列化有值的数组位置。

    transient Object[] elementData; //存放元素的数组
   

3. add(E e)添加元素方法： 会检查数组容量是否够存放新加的数据，判断如果不够存放就会进行扩容，首次扩容判断是否当前维护的数组是空数组，是的话初始化一个容量为10的数组，不是的话按照当前数组容量1.5倍扩容。

   private static final int DEFAULT_CAPACITY = 10; //默认容量为10
      /*
      没有向集合添加元素时，容量为0，是一个空数组，
      当添加任意一个元素后，就变成了10
      每次扩容大小是原来的1.5倍
      */
      
   transient Object[] elementData; //存放元素的数组
   private static final Object[] EMPTY_ELEMENTDATA = {};
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
      
   private int size;//实际的元素个数
      
      //无参构造
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //空数组赋值为数组
   }
      
      
   //add() 方法
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!  增加容量
       elementData[size++] = e;
       return true;
   }
   private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //（10，1）
       }
   
       ensureExplicitCapacity(minCapacity);
   }
   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
   
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }
   private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);  //扩容1.5倍
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   

4. add(int index,E e)指定位置添加元素： 同样会检查容量，然后会基于system.arrayCopy数组复制将index位置开始的数据往后一位复制，最后将index位置的数据赋为e。

5. addList(Collection c) 添加一个集合，同样会检查容量，由于添加的是一个集合，1.5倍扩容可能不够存放即将存放的集合，这时判断不够存放，会将新数组的大小扩容为原数组大小加上c的大小。

6. remove(int index)方法也是基于数组复制，将index位置后面的数据往前一位复制，将index位置的数据顶掉。

7. foreach基于普通for循环实现的，建议用增强for循环效率高些。

3.2linkedList 类【重点】

1. 线程不安全，有序的集合，按照插入顺序排序。

2. 基于双向链表实现，查找数据的时候会判断index偏向尾节点还是头节点，偏向头节点则从头节点开始遍历查找，反之同样。通过空间换时间，查找时间复杂度o(n/2)。集合实现内部类node, 包含数据、指向上一节点的node对象和指向下一节点的node对象。集合维护起始节点和结束节点。

3. add(E e)方法 将现在的结尾节点下一个指向e,将e改为结尾节点，速度快。

   transient int size = 0; //容量大小(节点个数)
   
   transient Node<E> first;//链表的头节点
   
   transient Node<E> last; //链表的尾节点
   
   public LinkedList() { //无参构造
   }
   
   //add()方法
   public boolean add(E e) {
       linkLast(e);
       return true;
   }
   void linkLast(E e) {
       	
       //获取最后一个元素
       final Node<E> l = last;   
       //新创建一个节点，其尾结点为null
       final Node<E> newNode = new Node<>(l, e, null);  
       //将last节点指向刚刚创建的新节点
       last = newNode;
       //如果此时集合为null，则令第一个节点也为该元素，否则就将这个元素的下一个节点设置为新创建的节点
       if (l == null)
           first = newNode;
       else
           l.next = newNode;
       size++; //节点数量增加
       modCount++;
   }
   private static class Node<E> {//结点类
       E item;
       Node<E> next;
       Node<E> prev;
   
       Node(Node<E> prev, E element, Node<E> next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
    }
   

   ​ add(int index,E e)指定位置添加元素

   //LinkedList支持指定的索引处增加节点
   public void add(int index, E element) {
       	//检查传入的索引是否符合要求
           checkPositionIndex(index);
   		//如果这个索引是最后一个节点，则直接添加
           if (index == size)
               linkLast(element);
           else
               //否则
               linkBefore(element, node(index));
   }
   //返回了指定下标的Node
   Node<E> node(int index) {
           // assert isElementIndex(index);
   		//如果此时的下标小于节点的一半，相当于一个二分查找的方法，
           if (index < (size >> 1)) {
               Node<E> x = first;
               for (int i = 0; i < index; i++)
                   x = x.next;
               return x;
           } else {
               Node<E> x = last;
               for (int i = size - 1; i > index; i--)
                   x = x.prev;
               return x;
           }
   }    
       //将需要插入的元素进行插入
   void linkBefore(E e, Node<E> succ) {
           // assert succ != null;
           final Node<E> pred = succ.prev;
           final Node<E> newNode = new Node<>(pred, e, succ);
           succ.prev = newNode;
           if (pred == null)
               first = newNode;
           else
               pred.next = newNode;
           size++;
           modCount++;
   }
   
   /*
      实现的思想可以归结为：每一次的插入或者移除，都是通过node()方法获取指定的Node节点，然后通过linkBefore或者linkLast这些方法来具体进行链表的操作。 
   /*
   

4. remove(int index) 需要先找到这个位置的节点花费o(n/2)，移动指针将该位置的节点e的上一个节点的next指向e的下一个节点，e的下一个节点的prev指向e的上一个节点。

3.3Vector类

1. 线程安全，类似ArrayList加上了同步。

2. （底层也是一个数组）与ArrayList类似也是维护一个数组，但是Vector操作数组的方法都在方法上加上synchronized进行同步处理。

3. 向量集合

4. 底层是一个Object[]数组，初始容量为10，数组容量不够的时候自动扩容为原来的一倍

   protected Object[] elementData; ///存放元素的数组
   
   public Vector() { //初始容量为10
           this(10);
   }
   
   int oldCapacity = elementData.length; //数组容量不够的时候自动扩容为原来的一倍
           int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                            capacityIncrement : oldCapacity);
   
   

四、Set接口

• 无序，无下标，元素不可重复（底层均为Map集合实现）

4.1HashSet【重点】

1. 存储结构是哈希表（数组+链表+红黑树（jdk1.8之后））
2. 底层基于 HashMap，hashSet就是基于hashMap实现的，创建hashSet底层就是创建一个hashMap,存放数据基于hashMap的key不能重复，map的value存放一个固定的对象。hashSet的遍历就是基于hashMap的key集合进行遍历。(具体实现可看下面的 HashMap)
3. 线程不安全，用于让存放的数据去重。
4. 无序，无下标

private transient HashMap<E,Object> map;

//无参构造
public HashSet() {
        map = new HashMap<>();
}

//add()方法
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

4.2TreeSet【重点】

1. 存储结构是红黑树（平衡二叉查找树）
2. 线程不安全
3. 底层基于 TreeMap，具体实现可看下面的 TreeMap

private transient NavigableMap<E,Object> m; //存放生成的TreeMap集合

// 作为值添加到TreeMap中，即每一个Entry的键不同但值相同，都是一个对象的地址
private static final Object PRESENT = new Object();

TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
}

//无参构造
public TreeSet() {
        this(new TreeMap<E,Object>());
}

//add()方法
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
}

4.3LinkedHashSet

1. 底层基于 LinkedHashMap 实现，通过LinkedHashMap中的方法实现了顺序存值。具体实现可看下面的LinkedHashMap

public LinkedHashSet() {
        super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

五、Map集合

• 键值对的形式存储结构 ，键不可重复，无序，无下标

int size();
isEmpty();
containsKey();
containsValue();
get();
put();
remove(; 
keyset();
values();
entrySet(); //等方法（可查看api学习）

5.1Entry类

• Map类的内部类，存储的就是键值对，用来获取所有的键值

5.2HashMap类【重点】

1. 无序的
2. 线程不安全，key value形式的集合。
3. JDK7和JDK8的区别是resize的方式不同（尾插法和头插法），hash冲突处理方式也不同，jdk7就是单纯的链表，JDK8链表长度大于等于8，并且数组元素个数大于等于64的时候，会转成红黑树，小于等于6时再退成链表。
4. hashmap基于数组和链表实现（jdk8加上了红黑树），数组默认容量是16，负载因子是0.75，当容量（总节点数）大于等于16 * 0.75=12时会发生扩容（扩容大小为原来的一倍），扩容的方式是创建一个新数组，将老数组的值都重新计算hash值存放进去。
5. hashmap通过与数组容量减1相与进行位运算，即hash % size = hash & size-1，实现和数组容量取余相同的效果，位运算性能会更好，但是也要求了数组大小是2的幂，如果不是2的幂减1就不是全是1的二进制数。如果创建hashMap指定的容量不是2的幂，会自动替换成大于这个容量的且最近这个容量的2的幂，比如设置9则会自动替换成16。
6. put（）方法，hashmap通过hash算法计算key的hashcode值，再与数组容量减1相与，得到数组下标，如果该数组下标没有存在数据，则直接存放进去，如果该位置已经存在数据，则以链表的形式将该位置的数据连接起来，jdk8在链表长度大于等于8，并且数组元素个数大于等于64的时候，会将链表转换成红黑树。在容量超过 容量*负载因子 时，会发生扩容，jdk7和jdk8扩容的方式不同。新数组冲突数据jdk7使用的是头插法和jdk8是尾插法，jdk7头插法会导致死循环。
7. jdk7的头插法，jdk8的尾插法，简单来说就是：当元素被放入时，通过计算要放在链表中，（头插法就是将该元素放在这个链表中第一个元素的前面，而尾插法就是将该元素放在这个链表中最后一个元素的后面）。
8. jdk8虽然通过尾插法解决了死循环的问题，但是hashMap追求的是高性能，并没有对共享变量做安全控制，在多线程环境下肯定会出现变量被覆盖，并发修改某个位置的值造成数据丢失各种问题，因此如果是多线程环境，要用concurrentHashMap。
9. get方法：通过计算key的hash值取余得到对应数组位置，取出该位置的数据并比较hash值,和==比较或equals比较，比较相同则返回，不同则判断是树节点还是普通节点，树节点通过遍历树节点判断，普通节点则遍历链表判断。
10. 首次创建不会分配数组，put数据的时候发现为空才创建数组。
11. 为什么设置成8转红黑树，因为红黑树查找平均时间复杂度为log(2)N，链表遍历平均是N/2,8以下的查找效率差不多，但是链表的插入效率会好很多，链表插入是o(1),红黑是树是log(2)N。为什么设置6转链表，与上面同理，不设置7是防止map频繁增加和删除，频繁转换节点结构。

5.3TreeMap【重点】

1. 线程不安全
2. 实现了有序
3. TreeMap是一个的有序的key——value集合，基于存放数据进行比较排序，继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口
4. 底层由红黑树实现，不可以存放NULL。
5. 构造函数可以接收一个Comparator比较器，用于自定义比较方法，如果没有设置Comparator则通过类本身实现的Comparable进行元素比较（如果类没有实现Comparable转换就报错了）。
6. get()方法，自上而下比较节点（二叉查找树规则）
7. put()方法先查找应该存放的位置，存放后校验是不是符合红黑树特性，不符合则进行变色旋转调整。
8. remove()方法，寻找到替换节点，将替换节点替换掉删除节点，然后判断被删除的节点是不是黑色，如果是的话说明此时红黑树已经不满足特性，需要旋转和变色重新调整树结构。

5.4HashTable

1. 线程安全，与hashMap类似，但是方法上都加上了syschronized同步，不可以存放NULL。
2. 默认大小11，总节点数（包含链表中的节点）超过容量*负载因子则扩容，扩容两倍+1扩容。基于数组和链表实现，类似jdk7 hashMap。
3. 插入数据采用头插法。相同位置的节点，先进的会在链表后面。

5.5LinkedHashMap

1. 继承hashMap,线程不安全。

2. 有序的hashMap，

3. 实际上存储还是和hashMap一致，但是底层类似LinkedList维护多一个双向链表用于保存节点的顺序，支持两种排序，一种是按照插入顺序排序成员变量accessOrder=false，一种是按照访问顺序排序成员变量accessOrder=true（访问顺序包括查询节点和修改已存在的key的节点，都会修改该节点的位置），默认accessOrder=false，即按照插入顺序排序。

4. 内部封装了一个Entry，继承了HashMap的Node类，封装多了两个参数，before和after用于指向节点前后的数据（跟hashMap的Node节点的next不一样，next是存储hash冲突后链表的下一个节点，befor和after是全局的节点顺序）。代码如下：

   static class Entry<K,V> extends HashMap.Node<K,V> {
           Entry<K,V> before, after;
           Entry(int hash, K key, V value, Node<K,V> next) {
               super(hash, key, value, next);
           }
   }
   

5. put方法，使用hashMap的put方法，但是重写了put方法调用到的几个方法，newNode、newTreeNode、afterNodeAccess、afterNodeInsertion。

6. newNode方法的改动：创建Node改为创建Entry。linkedHashMap内部维护两个成员变量，Entry head和 Entry tail，用于存放头节点和尾节点，创建第一个节点会设置成head和tail为该节点，之后每创建一个节点会修改尾节点tail为当前的节点，旧的尾节点after设置为当前节点，新的尾节点before设置成旧的尾节点。即head-><-node1-><-node2-><-tail,通过双向链表将所有节点连接起来。

7. newTreeNode方法和newNode加上一样的操作。（newNode是创建普通节点，newTreeNode是创建树节点）。

8. afterNodeAccess方法：hashMap在插入节点的时候如果当前的key已经存在会修改当前key对应的value，修改value后hashMap会调用afterNodeAccess方法。这个方法在hashMap中是一个空方法，LinkedHashMap实现了这个方法。在这个方法中判断如果accessOrder=true并且当前节点不是尾节点，则会将该节点移动到尾节点。具体操作就是移动该节点的前后节点的指针，把指向当前节点的after和before互连，然后把该节点替换成尾节点，旧的尾节点after指向该节点。（即按照访问顺序排序才会移动已存在的key节点）

9. afterNodeInsertion方法（用于给子类实现LRU）：hashMap在put方法的最后会调用这个方法，同样hashMap没有实现，LinkedHashMap实现了。但是在LinkedHashMap里面这个方法是没有任何意义的，这个方法的作用是移除头节点，但是移除前会调用removeEldestEntry方法判断要不要移除，LinkedHashMap这个方法固定会返回false，也就是永远不会移除。这样设计的目的是，如果开发者想要实现一种机制，当集合的总数达到一定数量后，把最早插入的节点移除或者把最近最少访问的节点移除(也就是移除头节点)，那么继承LinkedHashMap并重写这个方法就可以了，开发者可以在里面自定义策略返回true和false。

10. remove方法调用hashMap的remove,remove方法调用了afterNodeRemoval，LinkedHashMap实现这个方法删除双向链表中该节点。

11. get方法,LinkedHashMap自己实现了这个方法，获取节点和hashMap一样，加了一步判断accessOrder=true会把该节点移动到双向链表尾部。

12. entrySet遍历集合，封装了个内部迭代器，通过遍历双向链表实现。

5.6 Properties类

1. Java配置文件中用的居多
2. 可以直接通过load方法加载配置文件，通过store方法存储配置文件
3. 泛型锁定，为两个String类型