前言

我们在面试时候,数据集合肯定是必不可少的一个内容,要想代码写得好,不应该把瓶子使用的精妙

小知识

1.1、时间复杂度on、o1、o(log n)区别

  • o1 只需要查询一次就能找到元素,例如get(index)下标查询
  • on 需要从头查到尾,时间不知道多久,例如根据元素查询的链表Map
  • o(log n) 范围性以此类推查询,缩短时间,红黑树、二叉树

数组和链表区别

  • 数组:保证数据有序、可以基于下标查询,时间复杂度O1,删除需要移动下标。
  • 链表:有单向链表和双向链表区别,可以基于下标查询但是时间复杂度On,增删只需要改变指针引向
    image.png

一、ArrayList集合源码分析

1.2、底层原理

采用数组形式实现

1.3、扩容

add():扩容因子是1.5倍

1.4、缩容

remove():将目标元素后面的所有元素向前移动1个位置,时间复杂度为on

1.5、时间复杂度

时间复杂度On

1.6、优缺点

查询快,新增删除慢

1.7、ArrayList和Vector

  • 相同:都是数组实现的,默认初始容量为10
  • 不同:
    • Vector线程安全,ArrayList线程不安全
    • Vector扩容2倍,ArrayList扩容1.5倍

二、Vector集合

2.1、数据结构

数组结构

2.2、时间复杂度

O1

2.3、扩容

原来2倍

2.4、安全

线程安全

三、、LinkedList集合源码分析

3.1、原理

基于双向链表结构
image.png

四、HashMap集合源码

详情见源码分析那一章节面试题

4.1、HashMap是否允许key重复

不允许,比较hash值相等并且equal不等

4.2、只有扩容,没有缩容

五、HashSet集合源码分析

5.1、底层原理

基于HashMap实现,key为HashSet存放的元素 value值空的object对象

5.2、为什么是无序的

因为HashMap遍历key就是无序的

5.3、底层数据结构模型是什么

数组+链表+红黑树

上一篇 下一篇