锐客网

  1. 首页 > it技术 > >

JDK成长记9（集合篇的总结和练习）

JDK成长记9（集合篇的总结和练习）
文章图片

这一节主要是抛出一些面试题让大家检验一下学习成果，也会小结一下集合篇的知识点。 所以不会特别长。
练习-模拟面试 练习-模拟面试

先给大家讲一个简单的面试场景
快手Java面试一、二面：
（一面一般会问一些各种基础，比如集合、并发、锁、JVM、MySql、Redis，IO模型，网络模型等基本原理和知识。二面也会掺杂一些基础，还会有些项目相关、框架的原理，中间件的原理，一些架构和思想，三面也是多方面的，但是基础会少，一般是一些底层原理，系统设计或者架构等）
面试官：你好
候选人：你好
大家寒暄一下……
面试官：在你的简历上面看了你的履历……
之后你总结一面和二面，问了一些ArrayList如下问题：
\1) 新建一个ArrayList会分配内存吗?
\2) ArrayList和LinkedList的区别?
\3) ArrayList扩容机制?
\4) ArrayList的一些API，逐个分析他们的时间复杂度?
\5) Hashmap底层数据结构，什么时候转化为红黑树，put操作的流程。
\6) Hashmap线程安全吗？线程安全的方式有哪些？
再给大家讲几个比较猛的面试题
阿里面试 HashMap连环炮
\1) hash值计算的算法是什么？就是key.hashCode()吗？
\2) 默认情况下，put第一个元素时候容量大小是多少？扩容阈值又是多少？
\3) hash寻址如何进行的？
\4) hash值如果计算的相同该怎么解决冲突？
\5) HashMap扩容后怎么进行rehash的？
\6) 指定大小的HashMap，扩容阈值算法是什么？
\7) Hashmap死循环问题解释一下？
美团面试题（深入）
HashMap的JDK1.8和JDK1.7的实现不同之处？（大家可以看下JDK1.7的源码找下不同）
字节跳动面试题（果然有算法）
\1) 算法：翻转一下单向链表--->单向链表每k个元素翻转一次（升级版）
\2) 介绍HashMap ,与TreeMap区别？
\3) 用HashMap实现一个有过期功能的缓存,怎么实现？
https://blog.csdn.net/zhouyan...
ArrayList小结 ArrayList小结

1、 ArrayList的基本原理底层是一个Object数组。优点主要是随机访问快，缺点是扩容和插入和删除元素，会进行元素拷贝性能较差，不是线程安全的。
2、 创建ArrayList时，不指定大小， ArrayList第一次添加元素，会指定默认的容量大小为10。
【JDK成长记9（集合篇的总结和练习）】3、 ArrayList的扩容机制主要两点，一个是计算扩容大小=原值+原值右移1（等价1.5倍），一个是底层通过System.arraycopy来拷贝元素和创建新数组，来最终实现空间的扩容。
4、 核心方法大多是通过System.arraycopy进行拷贝元素做到的，removeIf方法中
5、 遍历通过内部类Itr遍历时向后访问，ListItr遍历时向前、向后均可访问，由于不是线程安全，通过modcout的检测，实现了fail-fast机制。
6、 Vector使用了synchronized关键字的ArrayList，线程安全，扩容是原来的2倍。Stack继承了Vector，使用数组模仿了栈的操作而已。
LinkedList小结 LinkedList小结

1、 LinkedList的基本原理，底层是一个双向链表。优点主要是插入和删除元素性能好，确定是随机访问性能差，不是线程安全的。链表元素具有prev和next、item组成，内部存在first和last两个头尾指针。
2、 在LinkedList的尾、头添加或者删除元素，使用l辅助指针记录原last元素或first指针位置。
3、 定位元素，采用二分法思想，根据size>>1进行了二分，通过for循环定位元素，时间复杂度O(n)
4、 中间添加或者删除元素时候，先定位元素，之后使用两个前后辅助指针，进行元素的插入或者删除。
HashMap小结 HashMap小结

1、 HashMap底层数据结构，JDK1.7数组+链表、JDK1.8数组+链表+红黑树。优点访问时间复杂度O(1),很快，缺点不是线程安全的。
2、 hash值计算的算法是什么？就是key.hashCode()吗？不是，基于hashCode进行计算的,高16位和低16位进行了异或操作。让高16位尽可能计算，减少hash冲突的概率。具体：hash=hashCode^hashCode>>>16。一般称之为扰动处理。
3、 默认情况下，put第一个元素时候容量大小是多少？扩容阈值又是多少？
put第一个元素的时候默认容量时16，扩容阈值是0.75*16=12。
4、 hash寻址如何进行的？
index = (n-1) & hash等价于 index =hash % n。不过&与操作性能更高。
5、 hash值如果计算的相同该怎么解决冲突？
3种情况，第一种hash值相同，key值也相同，进行覆盖操作。第二种hash值相同，key值不同，链接为单向链表结构，第二种hash值相同，key值不同，单向链表长度达到8，会将链表变为红黑树。
6、 HashMap扩容后怎么进行rehash的？
对应hash冲突产生的3中情况，扩容rehash也有3种情况。
情况1:如果数组位置只有一个值：使用新的容量进行rehash，即e.hash & (newCap - 1)
情况2:如果数组位置有链表，根据 e.hash & oldCap == 0进行判断，结果为0的使用原位置，否则使用index + oldCap位置,放入元素形成新链表，这里不会和情况1新的容量进行rehash与运算了，index + oldCap这样更省性能。
情况3：如果数组位置有红黑树，根据split方法，同样根据 e.hash & oldCap == 0进行树节点个数统计，如果个数小于6，将树的结果恢复为普通Node，否则使用index + oldCap，调整红黑树位置，这里不会和新的容量进行rehash与运算了，index + oldCap这样更省性能。
7、 指定大小的HashMap，扩容阈值算法是什么？
由于指定容量大小时，会计算扩容阈值，会将传入的容量大小调整为最接近2的次幂大小，设置为扩容阈值，构造函数时候，只是计算了扩容阈值，没有初始化数组大小。在添加元素时候数组大小等于了扩容阈值。
为什么这么做呢？一句话，为了提高hash寻址和扩容计算的的效率。因为无论扩容计算还是寻址计算，都是二进制的位运算，效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。
8、 HashMap死循环问题
在JDK1.8引入红黑树之前,JDK1.7由于只有单向链表解决hash冲突，除了遍历性能可能会慢，还有几率在多线程同时扩容，rehash的时候发生死循环问题，造成cpu100%。
造成死循环的核心脉络有如下几步：
1、首先原位置得有hash冲突，比如链表元素有4个。
2、之后需要有2个线程，同时添加元素，均满足扩容条件，进行扩容
3、一个线程刚刚进行了rehash操作，之后另一个线程开始rehash操作，会形成环向链表
4、get操作时候发生无限死循环，cpu可能达到100%
HashMap的兄弟姐妹们小结 HashMap的兄弟姐妹们小结

1、 LinkedHashMap 继承与HashMap，底层结构基于HashMap，增加了2个before和after指针，形成双向链表，可以维护插入有序或者访问有序，访问有序可用来做LRUMap或者适用需要顺序遍历的场景，但是它仍然不是线程安全的。
2、 TreeMap 可以自定义Key值的排序规则，底层数据结构是红黑树。应用场景很灵活，可以用来请求参数排序或者最近一次心跳时间、续约时间排序，来实现心跳或续约过期机制等。
3、 HashTable和HashMap核心区别就是使用synchronized保证线程安全，这个和Vector+ArrayList很像
4、 HashSet使用了HashMap，只不过add方法时候的value都是new Object()而已，结合map的特性，同一个key值只能存在一个，map在put的时候，会hash寻址到数组的同一个位置去，然后覆盖原来的值，所以Set是去重的。默认是无序的。
5、 LinkedHashSet继承了HashSet,此时HashSet通过使用LinkedHashMap，是可以进行访问有序的保证
6、 TreeSet也同理，默认是根据key值的compare方法来排序的，可以自定义Comparator，底层使用了TreeMap，add元素时，同样是空的Object，同样去重，但是TreeSet访问是可以有序。
7、 LinkedHashSet/TreeSet/HashTable/HashSe的原理都极其简单，都是基于之前的HashMap、LinkedHashMap、TreeMap而已。
阅读源码的思想和方法总结 阅读源码的思想和方法总结

1、 抓大放小的、对先脉络后细节、连蒙带猜的思想
2、 举例子、画图的方法
观念心态成长总结 观念心态成长总结

5个更重要
? 成长比成功更重要
? 改变自己比改变别人更重要
? 榜样比说服力更重要
? 借力比努力更重要
? 相信比知道更重要
3个坚持秘诀
? 坚持的三个秘诀之一视觉化
? 坚持的三个秘诀之一目标化
? 坚持的三个秘诀之一个性化

本文由博客一文多发平台 OpenWrite 发布！

    推荐阅读


    上一篇：Android入门教程 | Fragment （加载方法与通信）

    下一篇：GitOps|GitOps 应用实践系列 - 综述