• 💂 个人网站: IT学习日记
• 🤟 版权: 本文由【IT学习日记】原创、需要转载请联系博主
• 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

前言

• 大家好,这里是IT学习日记,相信大家对今年IT的行情应该也有所了解了，从大厂到小厂，各种裁员消息。公司裁员我们无法决定，我们能做的就是不断提升自己，提前准备。

• 本系列文章主要分享了之前博主真实面试中遇到的一些问题，希望能够帮助准备就业或者跳槽的朋友。

一:List、Set、Map有什么特点,适用的场景

(一) 结构和特点

  一:List

  有序的、可以重复,根据不同的实现,底层可以是数组(ArrayList、Vector)或者链表(LinkedList)。

  结构是数组的可以通过下标进行访问,适用于查找,增删满(因为要维护下标),结构是链表的,增删快(可以直接修改指针指向即可),查询慢(需要遍历链表获取)。

  二:Set

  无序的、不能重复,根据不同的实现,底层可以是哈希表和链表(如:LinkedHashSet)和红黑树(如:TreeSet)。

  LinkedHashSet由哈希表和链表组成,链表保证存放的元素有序性,哈希表保证存放的数据唯一性。

  TreeSet由红黑树构成,通过对比元素返回值是否为0判断元素的唯一性,同时提供了自然排序(比较类实现Comparable接口)和自定义排序(传入Comparator比较器类实现比较细节)

  三:Map

  存储的格式是键值对的方式,键需要唯一,值可以重复,根据不同的实现,底层可以是由哈希表(HashMap)或者哈希表+链表(LinkedHashMap)或者红黑树(TreeMap)组成。

  HashMap判断重复的逻辑: 先比较元素的hashCode方法判断是否相同,如果相同再比较equals方法,如果是true则表示key已存在,不进行保存,如果equals返回false,则添加键值对到哈希表中。

(二) 总结

二: HashMap和Hashtable的区别

  1、作者不一样,HashMap的作者有Doug Lea,而Hashtable的作者有Arthur van Hoff

  2、产生的时间不一样,HashMap是jdl1.2才有的,Hashtable是jdk1.0就有了

  3、继承的父类不一样,HashMap的父类是AbstractMap,Hashtable的父类是Dictionary

  4、判断key存在的api不一样,Hashtable可以使用contains或者containsKey,而HashMap只能通过containsKey

  5、Hashtable不支持key和value为null、HashMap支持key和value为null

  6、Hashtable是线程安全的,在方法中添加了synchronized,HashMap不是线程安全的(要线程安全则使用concurrentHashMap)

  7、初始化容量大小和扩容大小不同。HashMap的默认大小是16,扩容的大小为原来的2倍,Hashtable的初始化大小是11,扩容的大小为原来的2n+1

三: 为什么HashMap的默认大小是16

  1、首先理解碰撞的意思: 两个不同元素,但是Hash函数的值相同,则表示碰撞

  2、HashMap底层是数组 + 链表(1.8后当集合元素大于等于64个且链表长度大于8时会转为红黑树),key的index计算方式 = key.hash & (数组长度 - 1),由此看出key的index取值主要取决于hashcode的后n位(因为hashmap的长度是2的倍数,长度-1则后n位转为2进制数时都为1,与key的hash过后的值进行与运算,则如果此时key的hashcode足够均匀,则不会产生碰撞,所以,默认值肯定是2的倍数,16的取值是创建者经过大量测试后得到一个比较合理的值,这个值并不需要纠结,回答的时候只要答出这个逻辑即可)。

四: 数组、链表、哈希表的区别

  1、数组: 连续的一篇存储区间,占用内存严重,故空间复杂度高,二分查找事件复杂度为O（1）,寻址容易,插入和删除困难(因为剩下的需要移动坐标)

  2、链表: 存储区间松散,占用内存宽松,通过指针关联前后元素位置,所以空间复杂度小,时间复杂度大,达到了O(n),寻址困难,插入和删除容易

  3、哈希表: 即链表的数组,结合了两者的特点

    (1)、元素存储到数组的位置: index = key.hash() & (len - 1)

    (2)、HashMap是一个线性数组,内部由Entry对象组成,每一个Entry对象包括key、value、hashCode、next(下一个元素)组成,key为Null的元素放在数组下标为0的链表中。

五: 解决Hash冲突的方法

  1、开放定址法

  开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

  2、再Hash(哈希)法

  再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数
计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

  3、链地址池法

  每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。(HashMap就是使用该种方式解决Hash冲突问题)

  4、建立公共溢出区

  将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

小结

   不积跬步，无以至千里；不积小流，无以成江海。今天播种努力的种子,总会有一天发芽!

   欢迎大家关注,如果觉得文章对你有帮助,不要忘记一键三连哦,你的支持是我创作更加优质文章的动力,希望大家都能够早日拿到心仪的Offer,有任何面试问题可以私信我,欢迎大家投稿面试题目哦!

  该篇文章已经被收录在个人开源专栏：《IT知识小屋》中。专栏以小白视角切入，讲解通俗易懂，内容包含IT各方向知识(JAVA基础、进阶、面试真题、算法、面试采坑经验、996公司等)，是IT知识学习+面试首选IT小屋。

• Gitee地址：IT知识小屋

• Gihub地址：IT知识小屋