Java集合类知识点总结.doc

《Java集合类知识点总结.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Java集合类Java集合类11.Map31.1.HashMap31.1.1.底层实现31.1.2.特点31.1.3.源码分析41.1.4.多线程可能出现的问题51.2.ConcurrentHashMap61.2.1.底层实现61.2.2.源码分析71.3.HashTable91.3.1.HashTable是线程安全的，因为所有方法上都加了synchronized关键字。91.3.2.HashTable的key和value都不可以为null。91.3.3.扩容时，capacity=2*capacity+191.3.4.数组默认大小为1191

2、.3.5.查找下标时，没有使用hash&length-1，而是直接进行计算的91.4.TreeMap101.4.1.底层实现为红黑树101.4.2.TreeMap是一个有序的key-value集合，基于红黑树实现。该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序101.4.3.接口实现101.4.4.Entry111.5.LinkedHashMap111.5.1.底层是数组+链表+红黑树+双向链表111.5.2.维护链表顺序和访问顺序111.5.3.LinkedHashMap可以通过构造参数accessOr

3、der来指定双向链表是否在元素被访问后改变其在双向链表中的位置。111.5.4.当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，recordAccess方法什么也不会做。111.5.5.LRU实现112.Collection122.1.List12152.1.1.ArrayList122.1.2.LinkedList132.1.3.CopyOnWriteArrayList132.2.Set142.2.1.

4、HashSet142.2.2.TreeSet152.2.3.LinkedHashSet15151.Map1.1.HashMap1.1.1.底层实现1.7数组+链表数组的优点是访问速度快，但是插入删除操作慢因为数组在内存中是连续存放的，因此存取很快链表的优点是插入删除速度快，但是访问速度慢由于链表不是连续存放的，因此插入删除时，只需要修改前后指针的指向即可，不需要移动元素位置1.8数组+链表+红黑树拉链法由头插法改为了尾插法因为头插法在多线程的时候可能会导致死循环链表长度大于8的时候转化为红黑树红黑树的时间复杂度为logn,线性表查找的平均时

5、间复杂度为n/2,因此在链表长度为8时进行转化效率最高红黑树的转化也是比较消耗性能的链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表1.1.2.特点15存取的时间复杂度为O(1)1.1.1.源码分析put()1.判断key是否为null，如果为null，调用putlForNullKey，将key插入到数组下标为0的位置2.调用hash()方法计算key的hashcode，得到hash值3.调用indexFor()方法进行取模运算，得到元素的下标位置1.indexFor方法为：h&(length-1)2.使用与运算，计算速度

6、更快，因为二进制运算比十进制运算效率更高(十进制运算还需要将二进制转化为十进制)3.length之所以要设定为2次幂，就是为了这个indexFor方法服务4.可以让散列更加均匀，length-1的最后一位为1，因此进行与运算时，可以散列到奇数和偶数的下标位置，如果对length直接取模，由于length为2次幂，所以最后一位一定为0，所以与运算的结果一定是偶数，这也就导致奇数下标的位置不能被散列到。4.依次和该下标位置上的链表中的node节点比较key是否相等e.hash==hash&&((k=e.key)==key

7、

8、key.equals

9、(k))首先判断e.hash==hash是因为不同的key值也可能被散列到同一个位置，因此首先判断hash值，如果不相等则两个key肯定不等15如果相等，再通过==和equals比较是否相等，之所以要先判断hash值是否相等，是因为equal()很耗性能，因此先判断hash值能够提高效率重写了hashcode()方法就必须重写equals方法5.如果相等，更新value值，如果不相等，使用头插法(1.7)/尾插法(1.8)将entry(1.7)/Node(1.8)插入到链表中get()和put()方法类似，获取到桶的下标，再在链表上查找ke

10、y值，再获取key对应的value值resize()当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容扩容时，令capacity为原来的两倍。1.