文章目录??一、Iterable接口????二、Collection接口????三、List接口????3.1ArrayList类【重点】????3.2linkedList 类【重点】????3.3Vector类????四、Set接口????4.1HashSet【重点】????4.2TreeSet【重点】????4.3LinkedHashSet????五、Map集合????5.1Entry类????5.2HashMap类【重点】????5.3TreeMap【重点】????5.4HashTable????5.5LinkedHashMap????5.6 Properties类??
一、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类【重点】线程不安全。基于一个Object[]数组实现（底层就是一个数组），默认数组是个空数组，可以插入空数据，可以随机访问。如果要查找是否存在某个值，需要遍历数组匹配，时间复杂度是O(n)。由于通过存放的是动态数组，arrayList重写序列化方法readObject和writeObject，只序列化有值的数组位置。transient Object[] elementData; //存放元素的数组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);}add(int index,E e)指定位置添加元素： 同样会检查容量，然后会基于system.arrayCopy数组复制将index位置开始的数据往后一位复制，最后将index位置的数据赋为e。addList(Collection c) 添加一个集合，同样会检查容量，由于添加的是一个集合，1.5倍扩容可能不够存放即将存放的集合，这时判断不够存放，会将新数组的大小扩容为原数组大小加上c的大小。remove(int index)方法也是基于数组复制，将index位置后面的数据往前一位复制，将index位置的数据顶掉。foreach基于普通for循环实现的，建议用增强for循环效率高些。3.2linkedList 类【重点】线程不安全，有序的集合，按照插入顺序排序。基于双向链表实现，查找数据的时候会判断index偏向尾节点还是头节点，偏向头节点则从头节点开始遍历查找，反之同样。通过空间换时间，查找时间复杂度o(n/2)。集合实现内部类node, 包含数据、指向上一节点的node对象和指向下一节点的node对象。集合维护起始节点和结束节点。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));}//返回了指定下标的NodeNode<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这些方法来具体进行链表的操作。 /*remove(int index) 需要先找到这个位置的节点花费o(n/2)，移动指针将该位置的节点e的上一个节点的next指向e的下一个节点，e的下一个节点的prev指向e的上一个节点。3.3Vector类线程安全，类似ArrayList加上了同步。（底层也是一个数组）与ArrayList类似也是维护一个数组，但是Vector操作数组的方法都在方法上加上synchronized进行同步处理。向量集合底层是一个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【重点】存储结构是哈希表（数组+链表+红黑树（jdk1.8之后））底层基于??HashMap??，hashSet就是基于hashMap实现的，创建hashSet底层就是创建一个hashMap,存放数据基于hashMap的key不能重复，map的value存放一个固定的对象。hashSet的遍历就是基于hashMap的key集合进行遍历。(具体实现可看下面的 HashMap)线程不安全，用于让存放的数据去重。无序，无下标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【重点】存储结构是红黑树（平衡二叉查找树）线程不安全底层基于??TreeMap??，具体实现可看下面的 TreeMapprivate 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底层基于??LinkedHashMap?? 实现，通过LinkedHashMap中的方法实现了顺序存值。具体实现可看下面的LinkedHashMappublic 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类【重点】无序的线程不安全，key value形式的集合。JDK7和JDK8的区别是resize的方式不同（尾插法和头插法），hash冲突处理方式也不同，jdk7就是单纯的链表，JDK8链表长度大于等于8，并且数组元素个数大于等于64的时候，会转成红黑树，小于等于6时再退成链表。hashmap基于数组和链表实现（jdk8加上了红黑树），数组默认容量是16，负载因子是0.75，当容量（总节点数）大于等于16 * 0.75=12时会发生扩容（扩容大小为原来的一倍），扩容的方式是创建一个新数组，将老数组的值都重新计算hash值存放进去。hashmap通过与数组容量减1相与进行位运算，即hash % size = hash & size-1，实现和数组容量取余相同的效果，位运算性能会更好，但是也要求了数组大小是2的幂，如果不是2的幂减1就不是全是1的二进制数。如果创建hashMap指定的容量不是2的幂，会自动替换成大于这个容量的且最近这个容量的2的幂，比如设置9则会自动替换成16。put（）方法，hashmap通过hash算法计算key的hashcode值，再与数组容量减1相与，得到数组下标，如果该数组下标没有存在数据，则直接存放进去，如果该位置已经存在数据，则以链表的形式将该位置的数据连接起来，jdk8在链表长度大于等于8，并且数组元素个数大于等于64的时候，会将链表转换成红黑树。在容量超过 容量*负载因子 时，会发生扩容，jdk7和jdk8扩容的方式不同。新数组冲突数据jdk7使用的是头插法和jdk8是尾插法，jdk7头插法会导致死循环。jdk7的头插法，jdk8的尾插法，简单来说就是：当元素被放入时，通过计算要放在链表中，（头插法就是将该元素放在这个链表中第一个元素的前面，而尾插法就是将该元素放在这个链表中最后一个元素的后面）。jdk8虽然通过尾插法解决了死循环的问题，但是hashMap追求的是高性能，并没有对共享变量做安全控制，在多线程环境下肯定会出现变量被覆盖，并发修改某个位置的值造成数据丢失各种问题，因此如果是多线程环境，要用concurrentHashMap。get方法：通过计算key的hash值取余得到对应数组位置，取出该位置的数据并比较hash值,和==比较或equals比较，比较相同则返回，不同则判断是树节点还是普通节点，树节点通过遍历树节点判断，普通节点则遍历链表判断。首次创建不会分配数组，put数据的时候发现为空才创建数组。为什么设置成8转红黑树，因为红黑树查找平均时间复杂度为log(2)N，链表遍历平均是N/2,8以下的查找效率差不多，但是链表的插入效率会好很多，链表插入是o(1),红黑是树是log(2)N。为什么设置6转链表，与上面同理，不设置7是防止map频繁增加和删除，频繁转换节点结构。5.3TreeMap【重点】线程不安全实现了有序TreeMap是一个的有序的key——value集合，基于存放数据进行比较排序，继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口底层由红黑树实现，不可以存放NULL。构造函数可以接收一个Comparator比较器，用于自定义比较方法，如果没有设置Comparator则通过类本身实现的Comparable进行元素比较（如果类没有实现Comparable转换就报错了）。get()方法，自上而下比较节点（二叉查找树规则）put()方法先查找应该存放的位置，存放后校验是不是符合红黑树特性，不符合则进行变色旋转调整。remove()方法，寻找到替换节点，将替换节点替换掉删除节点，然后判断被删除的节点是不是黑色，如果是的话说明此时红黑树已经不满足特性，需要旋转和变色重新调整树结构。5.4HashTable线程安全，与hashMap类似，但是方法上都加上了syschronized同步，不可以存放NULL。默认大小11，总节点数（包含链表中的节点）超过容量*负载因子则扩容，扩容两倍+1扩容。基于数组和链表实现，类似jdk7 hashMap。插入数据采用头插法。相同位置的节点，先进的会在链表后面。5.5LinkedHashMap继承hashMap,线程不安全。有序的hashMap，实际上存储还是和hashMap一致，但是底层类似LinkedList维护多一个双向链表用于保存节点的顺序，支持两种排序，一种是按照插入顺序排序成员变量accessOrder=false，一种是按照访问顺序排序成员变量accessOrder=true（访问顺序包括查询节点和修改已存在的key的节点，都会修改该节点的位置），默认accessOrder=false，即按照插入顺序排序。内部封装了一个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); }}put方法，使用hashMap的put方法，但是重写了put方法调用到的几个方法，newNode、newTreeNode、afterNodeAccess、afterNodeInsertion。newNode方法的改动：创建Node改为创建Entry。linkedHashMap内部维护两个成员变量，Entry head和 Entry tail，用于存放头节点和尾节点，创建第一个节点会设置成head和tail为该节点，之后每创建一个节点会修改尾节点tail为当前的节点，旧的尾节点after设置为当前节点，新的尾节点before设置成旧的尾节点。即head-><-node1-><-node2-><-tail,通过双向链表将所有节点连接起来。newTreeNode方法和newNode加上一样的操作。（newNode是创建普通节点，newTreeNode是创建树节点）。afterNodeAccess方法：hashMap在插入节点的时候如果当前的key已经存在会修改当前key对应的value，修改value后hashMap会调用afterNodeAccess方法。这个方法在hashMap中是一个空方法，LinkedHashMap实现了这个方法。在这个方法中判断如果accessOrder=true并且当前节点不是尾节点，则会将该节点移动到尾节点。具体操作就是移动该节点的前后节点的指针，把指向当前节点的after和before互连，然后把该节点替换成尾节点，旧的尾节点after指向该节点。（即按照访问顺序排序才会移动已存在的key节点）afterNodeInsertion方法（用于给子类实现LRU）：hashMap在put方法的最后会调用这个方法，同样hashMap没有实现，LinkedHashMap实现了。但是在LinkedHashMap里面这个方法是没有任何意义的，这个方法的作用是移除头节点，但是移除前会调用removeEldestEntry方法判断要不要移除，LinkedHashMap这个方法固定会返回false，也就是永远不会移除。这样设计的目的是，如果开发者想要实现一种机制，当集合的总数达到一定数量后，把最早插入的节点移除或者把最近最少访问的节点移除(也就是移除头节点)，那么继承LinkedHashMap并重写这个方法就可以了，开发者可以在里面自定义策略返回true和false。remove方法调用hashMap的remove,remove方法调用了afterNodeRemoval，LinkedHashMap实现这个方法删除双向链表中该节点。get方法,LinkedHashMap自己实现了这个方法，获取节点和hashMap一样，加了一步判断accessOrder=true会把该节点移动到双向链表尾部。entrySet遍历集合，封装了个内部迭代器，通过遍历双向链表实现。5.6 Properties类Java配置文件中用的居多可以直接通过load方法加载配置文件，通过store方法存储配置文件泛型锁定，为两个String类型
【文章转自日本多IP站群服务器 japzq.html提供，感恩】你被雨淋湿的心，是否依旧。
