文章大纲

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

二: HashMap和Hashtable的区别

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

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

五: 解决Hash冲突的方法

每日小结

大家好,这里是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,有任何面试问题可以私信我,欢迎大家投稿面试题目哦!