Java集合类知识点总结

PAGE15Java集合类Java集合类 11. Map 31.1. HashMap 31.1.1. 底层实现 31.1.2. 特点 31.1.3. 源码分析 41.1.4. 多线程可能出现的问题 51.2. ConcurrentHashMap 61.2.1. 底层实现 61.2.2. 源码分析 71.3. HashTable 91.3.1. HashTable是线程安全的，因为所有方法上都加了synchronized关键字。 91.3.2. HashTable的key和value都不可以为null。 91.3.3. 扩容时，capacity=2*capacity+1 91.3.4. 数组默认大小为11 91.3.5. 查找下标时，没有使用hash&length-1，而是直接进行计算的 91.4. TreeMap 101.4.1. 底层实现为红黑树 101.4.2. TreeMap是一个有序的key-value集合，基于红黑树实现。该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序 101.4.3. 接口实现 101.4.4. Entry 111.5. LinkedHashMap 111.5.1. 底层是数组+链表+红黑树+双向链表 111.5.2. 维护链表顺序和访问顺序 111.5.3. LinkedHashMap可以通过构造参数accessOrder来指定双向链表是否在元素被访问后改变其在双向链表中的位置。 111.5.4. 当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，recordAccess方法什么也不会做。 111.5.5. LRU实现 112. Collection 122.1. List 122.1.1. ArrayList 122.1.2. LinkedList 132.1.3. CopyOnWriteArrayList 132.2. Set 142.2.1. HashSet 142.2.2. TreeSet 152.2.3. LinkedHashSet 15MapHashMap底层实现1.7数组+链表数组的优点是访问速度快，但是插入删除操作慢因为数组在内存中是连续存放的，因此存取很快链表的优点是插入删除速度快，但是访问速度慢由于链表不是连续存放的，因此插入删除时，只需要修改前后指针的指向即可，不需要移动元素位置1.8数组+链表+红黑树拉链法由头插法改为了尾插法因为头插法在多线程的时候可能会导致死循环链表长度大于8的时候转化为红黑树红黑树的时间复杂度为logn,线性表查找的平均时间复杂度为n/2,因此在链表长度为8时进行转化效率最高红黑树的转化也是比较消耗性能的链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表特点存取的时间复杂度为O(1)源码分析put()1.判断key是否为null，如果为null，调用putlForNullKey，将key插入到数组下标为0的位置2.调用hash()方法计算key的hashcode，得到hash值3.调用indexFor()方法进行取模运算，得到元素的下标位置1.indexFor方法为：h&(length-1)2.使用与运算，计算速度更快，因为二进制运算比十进制运算效率更高(十进制运算还需要将二进制转化为十进制)3.length之所以要设定为2次幂，就是为了这个indexFor方法服务4.可以让散列更加均匀，length-1的最后一位为1，因此进行与运算时，可以散列到奇数和偶数的下标位置，如果对length直接取模，由于length为2次幂，所以最后一位一定为0，所以与运算的结果一定是偶数，这也就导致奇数下标的位置不能被散列到。4.依次和该下标位置上的链表中的node节点比较key是否相等e.hash==hash&&((k=e.key)==key||key.equals(k))首先判断e.hash==hash是因为不同的key值也可能被散列到同一个位置，因此首先判断hash值，如果不相等则两个key肯定不等如果相等，再通过==和equals比较是否相等，之所以要先判断hash值是否相等，是因为equal()很耗性能，因此先判断hash值能够提高效率重写了hashcode()方法就必须重写equals方法5.如果相等，更新value值，如果不相等，使用头插法(1.7)/尾插法(1.8)将entry(1.7)/Node(1.8)插入到链表中get()和put()方法类似，获取到桶的下标，再在链表上查找key值，再获取key对应的value值resize()当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容扩容时，令capacity为原来的两倍。1.7时，需要new一个新数组，并对旧数组上的所有元素进行indexFor()操作确定下标地址,这一步很费时，1.8时只需判断hash值的左边新增的那一位是否为1，即可判断此节点是留在原地lo还是移动去高位hi,如果为1，则移动去高位，否则不变1.7时，扩容的时候可能出现死循环，1.8没有这个问题构造方法在第一次put()的时候，数组才初始化数组的长度为大于指定值的最小二次幂数组默认大小为16多线程可能出现的问题1.扩容时可能出现死循环2.put的时候可能被失效/覆盖线程A,B同时调用addEntry方法，同时获取到了相同的头节点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。3.修改的时候可能被覆盖线程A,B先后修改同一key值的value，会导致覆盖4.put非null元素后get出来的却是null扩容时调用的transfer方法，在获取数组的每个头节点的时候，在将e=头节点之后，都会将头节点置空，此时get可能导致获取到的值为0ConcurrentHashMap底层实现1.7segment数组+HashEntry数组(数组+链表)chm由一个segment数组组成segment每个segment元素包含一个HashEntry数组，每个HashEntry包含一个链表HashEntry大部分成员变量都为finalfinalkkeyvolatileVvaluefinalinthashfinalHashEntry<K,V>next1.8数组+链表+红黑树源码分析put()基本流程1.7通过两次hash确定第一次Hash定位到Segment通过segmentFor()函数进行,计算方式也和indexFor()相同SegmentMaskssize-1SegmentShift32-sshiftssize是大于ConcurrentLevel的最小二次幂第二次Hash定位到元素所在的链表的头部定位方法和HashMap中的indexFor()相同通过segment.lock加锁1.8通过两次hash确定通过CAS+synchronized加锁1.如果没有hash冲突就直接通过CAS插入2.如果有hash冲突或者CAS操作失败，说明存在并发情况，使用synchronized加锁3.如果插入成功就调用addCount（）方法统计size，并且检查是否需要扩容源码分析1.ensureSegment1.判断是否被其他线程初始化，这里使用了getObjectVolatile()方法

2.使用segment[0]的属性来初始化其他槽

3.使用while()循环，内部使用CAS操作，尝试初始化槽2.segment.put()get()get不需要加锁，因为HashEntry的value值设定为了volatile如果get()到的是null值，则可能这个key，value对正在put的过程中，如果出现这种情况，那么就通过lock加锁来保证取出的value是完整的resize()构造函数先根据ConcurrentLevel构造出Segment数组Segment数组大小是不大于concurrentLevel的最大的2的指数每个Segment中的HashEntry数组的大小都是大于指定大小的最小二次幂每个hashEntry的大小为大于initialCapacity/concurrentLevel的最小二次幂初始参数initialCapacity(每个HashEntry的长度)loadFactor：扩容因子concurrencyLevel：并发度，指Segment数组的长度remove在定位到待删除元素的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去。尾结点指向e的下一个结点。e后面的结点不需要复制，它们可以重用。因为HashEntry中的next是final，所以只能先把待删除之前的元素复制了再删除sizesize操作就是遍历了两次Segment，每次记录Segment的modCount值，然后将两次的modCount进行比较，如果相同，则表示期间没有发生过写入操作，就将原先遍历的结果返回，如果不相同，就需要将所有的Segment都锁住，然后一个一个遍历了，HashTableHashTable是线程安全的，因为所有方法上都加了synchronized关键字。HashTable的key和value都不可以为null。扩容时，capacity=2*capacity+1数组默认大小为11查找下标时，没有使用hash&length-1，而是直接进行计算的TreeMap底层实现为红黑树能够保证树总是平衡的，如果插入删除导致树不平衡，会自动进行调整变色左旋右旋查找的平均时间复杂度为O(logN)主要规则1.每个节点或者是黑色，或者是红色。2.根节点是黑色3.叶子节点为黑色4.如果一个节点是红色的，则它的子节点必须是黑色的5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。TreeMap是一个有序的key-value集合，基于红黑树实现。该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序接口实现NavigableMap是SortedMap接口的子接口，在其基础上扩展了一些方法，例如floorEntry，lowEntry,ceilingEntry等为了防止外部修改Entry，使用了ExportEntry修饰floorEntry等方法SortedMap定义按照key排序的Map结构，能够令Map按照key的自然顺序或者构造器顺序进行排序。Entry包含了left，right，parent节点LinkedHashMap底层是数组+链表+红黑树+双向链表同时使用一个额外的双向链表来维护链表的访问顺序维护链表顺序和访问顺序Node节点额外增加了before和after指针，用于维护链表的访问顺序next指针用来维护链表顺序LinkedHashMap可以通过构造参数accessOrder来指定双向链表是否在元素被访问后改变其在双向链表中的位置。当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，recordAccess方法什么也不会做。LRU实现插入数据后对调用afterNodeInsertion，afterNodeInsertion()方法中会调用removeEldestEntry，如果removeEldestEntry(first)返回true，按照LRU策略，那么会删除头节点(注意这里删除的是头节点！！！所以每次访问元素或者插入元素之后都要将该元素放到链表末尾)。这个也是实现LRU的关键点！！！！！CollectionListArrayList底层实现动态数组能够实现随机存取实现了RandomAccess接口fail-fast机制在使用迭代器遍历list时，如果modCount和expectedCount不匹配，就会直接抛出异常modCount在AbstractList中定义使用迭代器自带的remove()函数的时候，如果删除了list中元素，不会出现fail-fast,因为迭代器会调整modCount和expectedCount值自定义了序列化方法因为arrayList的底层数组中，可能存在值为null的元素，序列化这些元素是没有意义的，因此自定义了序列化方法，只序列化数组中非null的元素通过readObject()和writeObject()方法实现源码实现扩容：capacity=1.5*capacity通过Arrays.copyOf()System.copyOf()每次扩容的时候，都会传入一个minCapacity,即扩容之后的数组长度，对于add方法，是原size+1,对于addAll方法，是size+newSize,如果原数组长度*1.5仍不能存放所需的元素，那么就会直接令数组长度为minCapacityArrayList是插入前扩容,扩容逻辑为ensureCapacityInternal()>ensureExplicitCapacity()>grow()LinkedList底层实现双向链表常用apiaddofferremove适合插入删除多的场合CopyOnWriteArrayList和ArrayList基本一模一样