Java集合/面试题

首先一张图:了解五花八门的集合继承关系!图片说明
太烦了没关系,缩略版如下:
图片说明
总体上来看,常用的、常问的有三个接口:List有序列表、Set集合、Map键值对集合。

1.List:有序列表(元素可重复)

(1)ArrayList:数组

  • 底层结构:Object[]数组
  • 初始化:ArrayList的构造函数有三个:
    ①无参:数组初始化为默认的空数组。(添加第一个元素的时候才会初始化为容量为10的数组)
    ②参数为int(即指定大小数组):如果参数小于10,则创建容量为10的数组,否则创建指定大小的数组。
    ③参数为Collection类型:将参数转化为数组,如果数组为空则指向默认空数组,否则查看数组的类型是否是Object类型,不是的话要复制转换为Object类型。
  • 添加新元素:先移动游标,然后判断是否需要扩容,需要则先扩容,在将元素后移将新元素的位置腾出来(尾部添加省略这一步),之后在将新元素放在腾出来的指定位置。
  • 扩容:先看扩容的大小,如果扩容的大小小于10,则创建一个新数组容量为10,否则就1.5倍数组扩容。
  • 删除元素:删除指定索引的元素,将该索引后的元素前移一位,最后将游标前移;删除指定元素,首先遍历找到该元素的索引,然后通过索引删除该元素。

    (2)LinkedList:双向链表

  • 底层结构:双向链表
  • 添加新元素:
    ①头部添加:新元素的后继指针指向头指针指向的元素,头指针指向的元素的前驱指针指向新元素,头指针指向新元素。
    ②尾部添加:新元素的前驱指针指向尾指针指向的元素,尾指针指向的元素的后继指针指向新元素,尾指针指向新元素。
  • 删除元素:从头指针开始遍历,找到对应元素后将待删除元素的前驱指针指向的元素的后继指针指向待删除元素的后继指针指向的元素,待删除元素的后继指针指向的元素的前驱指针指向待删除元素的前驱指针指向的元素。

    (3)Vector:向量

    与ArrayList相比,多了通过synchronized保证线程安全。

    2.Map:键值对集合(键不可重复)

    (1)HashMap:

  • 底层结构:
    JDK1.7:数组+链表
    JDK1.8:数组+链表+红黑树
    (通过红黑树来优化查询速度,当链表上元素个数大于8转化为红黑树,小于8则转化为链表)
  • 初始化:构造函数有四个:
    数组的默认初始化大小为16,默认负载因子为0.75。
    ①无参:负载因子初始化为默认值0.75。
    ②参数为int(指定容量):调用构造函数③(int,int),负载因子为默认值0.75。
    ③参数为int,int(指定容量,指定负载因子):判断指定的容量、负载因子的合法性。
    ④参数为Map类型:先判断对于参数的大小,更新数组的元素个数大小,遍历将每个键值对放进hashmap中。
  • 添加新元素:先判断对于添加元素后的元素总个数是否需要扩容,如果需要,先扩容,之后进行散列,如果对应位置为null则直接创建新的节点放进去,如果对应位置有元素,则遍历判断,如果有相同key的覆盖,遍历结束如果没有找到相同的key则在链表尾部插入新节点。
    (1.7中使用了头插法插入节点,1.8中使用尾插法,目的是为了避免链表环化问题)。
  • 扩容:如果旧数组的大小>0则创建新数组,大小为旧数组的2倍。如果旧数组为空则创建的新数组长度为16。之后如果旧数组不为空则要把旧数组的键值全部重新hash到新数组中。
    计算新位置的时候:如果当前位置上的链表只有一个元素e,则通过e.hash & (newCap-1)计算出新位置直接放过去;
    如果当前位置上的链表不止一个元素,则可能会分成两部分:一部分仍在原位置e.hash & (oldCap-1),另一部分在hash & (newCap-1) == hash &(oldCap*2-1)即原下标+旧数组长度;(hash & oldCap) == 0的在原位置上,而不满足的是在新位置上。
  • 删除元素:先进行hash散列,如果散列的位置上链表只有一个元素则判断是否元素hash相等,key值相等,相等删除该节点;如果不止一个元素则遍历判断后在删除。
  • 查找元素:通过key查找元素时,会通过hash散列到对应的链表上,先判断链表头元素的hash、key是否相等,相等则直接返回;如果不相等则遍历链表判断后找到在返回,如果结束仍然没有找到返回null。

    (2)HashTable:

    与HashMap相比,多了通过synchronized保证线程安全。

    (3)LinkedHashMap:

    与HashMap相比,通过头指针、尾指针,并给每个Node<K,V>添加了前后指针,来记录元素的插入顺序。

    (4)TreeMap:

  • 底层结构:红黑树
    数据结构之红黑树 暂时没写....

    3.Set:集合(元素不可重复)

    (1)HashSet:基于HashMap实现的,value=null

    (2)LinkedHashSet:基于LinkedHashMap实现的,value=null

    (3)TreeSet:基于TreeMap实现的,value=null

全部评论
很强
点赞 回复 分享
发布于 2021-07-14 21:42

相关推荐

头像
03-14 11:23
已编辑
北京邮电大学 管理咨询
211勇闯初创小公司头破血流系列3这件事不是发生在我身上的,但前同事们参与创作的积极性空前高涨,为了习惯,还是都采用第一人称的视角来看这出大戏。有一天老板在我们的眼皮底下接了一个电话,最终敲定了去北京出差的时间,下周一。他得意洋洋地说,这单下来保底五百万的流水,如果成了,我们都能得到五位数的提成。这对于一群刚上班的人来说是天大的诱惑,我们经历了周末的无偿加班,把他去北京所需要的文件都准备好了。只是在去北京的周一当天,老板睡过头了。整个上午都没见他的踪影,给他发文件也不会,打电话问问题也不接,直到中午才姗姗来迟。当然,这只是拉开了这场恐怖出差的序幕。只见他来了也不紧不慢的,手指在办公室转了一圈,...
姜大力:补充: 1.五百万的单子根本没有五百万,只是过去展示拼装的产品并简单考察。该项目只是竞标,项目内容是商业街区改造; 2.决策是当天上午10点半左右老板珊珊来迟后突发奇想去北京,中午1点在催促下着急出发,没有任何出差补助; 3.出发之前已经知道进京证不好使了,但还是执意要开车去; 4.实习生实打实连续开了***小事车,非常辛苦,工资在转正后只有两千五; (有疑问会继续补充)
点赞 评论 收藏
分享
牛客963010790号:一般是hr拿着老板账号在招人不是真是老板招
点赞 评论 收藏
分享
落叶随风呀:学校不好就放两栏,专业能力往前移, 政治面貌不是党员不如不写,籍贯湖南衡阳,或者湖南,浅尝辄止 基本信息排版不够美观,没有对齐 简历上花里胡哨的东西去掉 项目我不评价,因为我能力有限,且对mcu了解不足 但是这份简历掌握的水平,你可以海投试试,工作没问题但是工资应该不会高,因为搞mcu的小公司多
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务