免费做请帖的网站,坡头网站开发公司,商务网站建设与维护 ppt,鸿蒙app开发公司目录
①HashMap的理解#xff1f;以及为什么要把链表转换为红黑树#xff1f;②HashMap的put#xff1f;③HashMap的扩容#xff1f;④加载因子为什么是0.75#xff1f;⑤modcount的作用#xff1f;⑥HashMap与HashTable的区别#xff1f;⑥HashMap中1.7和1.8的区别以及为什么要把链表转换为红黑树②HashMap的put③HashMap的扩容④加载因子为什么是0.75⑤modcount的作用⑥HashMap与HashTable的区别⑥HashMap中1.7和1.8的区别⑦HashMap与ConcurrentHashMap的区别⑧ArrayList和LinkedList的区别 ArrayList底层是数组并且线程不安全。初始大小为0第一次add的时候扩容(扩容使用grow()方法)为10再次扩容则为1.5倍。
Vector底层也是数组但是线程安全因为其方法被synchronized修饰。
LinkedList底层是双向链表增加删除效率高查效率低要遍历链表。
HashSet底层其实是HashMap即数组链表红黑树。
TreeSet底层是TreeMap。 ①HashMap的理解以及为什么要把链表转换为红黑树 答HashMap是双列集合中存放以k-v键值对(并且支持null)的一种集合类型其底层在jdk1.7之前为数组链表在jdk1.8引入了红黑树底层实现就变成了链表数组红黑树(当链表的长度大于8并且数组的长度大于64时链表就会树化为红黑树)。并且HashMap的底层采用链地址法来解决哈希冲突。引入红黑树的原因链表长度变长就会导致查找的效率降低将链表转换为红黑树可以加快查询效率。因为链表查询时间复杂度是O(n),而红黑树的查询时间复杂度是O(log n)。(如果数据直接在数组上时间复杂度就是O(1)) ②HashMap的put ①构造器HashMap初始化时就只设置了一下加载因子(0.75) ②put方法
第一步首先通过hash()方法去计算出哈希值 第二步判断table是否为空为空就调用resize()方法去创建一个初始大小为16的table
第三步然后根据数组长度和哈希值得到索引位置再判断这个位置是否为空如果为空就创建一个Node然后放进去 第四步如果不为空则去判断其hash值和Key是否相同如果都是相同的就会将其value替换掉 第五步如果比较出key不相同则去链表上循环比较直到找到有相同的hash值和key替换掉就退出如果整个链表上都没有的话就会在链表的尾部插入加入后就会判断是否要扩容还是树化。 ③HashMap的扩容 答首先hashmap在创建的时候是一个空的然后在第一次put的时候去检查到table为空就调用resize()方法给扩容到初始大小16。
然后一直添加数据当发现链表的长度大于8的时候就会调用treeifBin()方法去树化不是直接树化而是还要先判断数组的长度是否大于64如果没有的话就还是先会调用resize()去扩容数组为2倍的长度直到判断出链表长度大于8并且数组长度大于64时才会把链表转换为红黑树再添加数据进去。 ④加载因子为什么是0.75 答首先加载因子是表示hashmap的扩容阈值当元素数量到达数组长度的0.75就会发生扩容。0.75是默认的加载因子我们也可以设置成自己想要的值为什么0.75首先加载因子的选择是一种权衡如果加载因子较小就到导致频繁的扩容发生导致哈希表的填充度较低可能会浪费空间。如果加载因子较大虽然减少了扩容的频率也会导致更多的哈希冲突的发生导致链表的长度增加从而影响性能。所以默认的0.75在大多数情况下能够提供较好的性能和空间利用率。所以官方文档中有一段话说明了0.75提供了一个时间复杂度和空间复杂度的一个折中点。 ⑤modcount的作用 答首先modcount是用来记录被修改的次数。每次put或者remove都会使其加一。这个字段一般是用来实现快速失败(fast-fail)和保证数据一致性的比如说一个线程在对集合进行遍历的时候会首先把modcount放到一个expectedmodcount中然后遍历的时候会去比较当前的modcount和expectedmodcount此时如果当另外一个线程去修改或者删除了集合元素时会使modcount1然后该线程就会发现此时有并发修改的发生就会抛出一个并发修改的异常这样去避免数据不一致和错误的情况。 ⑥HashMap与HashTable的区别 答其都是map下的集合都是存储k-v键值对的。区别在于
①首先HashMap是线程不安全的HashTable则是线程安全的因为其所有的方法都加了synchronized关键字但是这样导致了性能大大降低所以HashMap的效率要比HashTable快。
②HashTable底层是基于数组链表实现的而HashMap在jdk1.7时是数组链表但在jdk1.8的时候引入了红黑树在链表长度大于8并且数组长度大于64时链表会转换为红黑树。
③HashMap的默认初始大小为16扩容容量为2倍而HashTable默认初始大小为11扩容容量为2n1。
④HashMap可以null作为键值但是null键只能有一个而Hashtable不行。 而且像现在不推荐使用HashTable ⑥HashMap中1.7和1.8的区别 答①首先底层结构1.7是数组加链表1.8是数组链表红黑树。提高了插入和查询的效率。
②插入数据的方式1.7是头插法1.8是尾插法。
③1.7中哈希算法比较复杂为了提高Key的散列性存在各种右移和异或运算而1.8引入了红黑树简化了哈希算法节省CPU资源。 ⑦HashMap与ConcurrentHashMap的区别 答首先二者都是以k-v键值对存储数据的集合。其区别在于
①HashMap是线程不安全的ConcurrentHashMap是JUC下的是线程安全的在jdk1.7的时候是通过分段锁来实现的线程安全jdk1.8则是用Synchronized和CAS以及volatile来保证了线程的安全。
②HashMap允许以null作为键值而ConcurrentHashMap不允许因为要避免空值在多线程并发场景下的歧义问题即如果一个线程读到了一个null的数据无法判断其是空值还是不存在。
③ConcurrentHashMap支持协助扩容而HashMap扩容时需要暂停其他操作。 ④迭代HashMap迭代器因为有modcount的使用导致其他线程修改或删除时遍历失败而ConcurrentHashMap则提供了安全的迭代器。 ⑧ArrayList和LinkedList的区别 答首先他们都是实现了List接口的集合。主要区别在于
①数据结构ArrayList是数组实现的而LinkedList是双向链表实现的。
②访问效率ArrayList的访问效率比LinkedList快。ArrayList的访问的时间复杂度是O(1)可以通过下标直接定位而LinkedList访问的时间复杂度是O(n)只能通过遍历链表去找到。
③增加和删除LinkedList的增加和删除的效率要比ArrayList快。因为LinkedList只要去修改前后元素的指针即可而ArrayList要移动插入点或者删除点后面的元素位置。
④空间占用LinkedList的占用空间比ArrayList大因为LinkedList的每个节点不仅要保存数据吗还要保存前后元素的指针。
