数组
数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构。
面试题:为什么数组索引从0开始?假如从1开始会怎么样?
操作数组的时间复杂度
当未知数组查询时,时间复杂度为 O(n)
总结
——————————————————————————————————————————————
ArrayList
ArrayList底层的实现原理是什么
- ArrayList底层是用动态的数组实现的
- ArrayList初始容量为0,当第一次添加数据的时候才会初始化容量为10
- ArrayList在进行扩容的时候是原来容量的1.5倍,每次扩容都需要拷贝数组
- ArrayList在添加数组的时候
- 确保数组已使用长度(size)加1之后足够存下下一个数据
- 计算数组的容量,如果当前数据已使用长度+1后的大于当前的数组长度,则调用grow方法扩容(原来的1.5倍)
- 确保新增的数据有地方存储之后,则将新元素添加到位于size的位置上
- 返回添加成功布尔值
如何实现数组和List之间的转换
——————————————————————————————————————————————————
链表
单向链表
- 链表中的每一个元素称之为结点(Node)
- 物理存储单元上,非连续、非顺序的存储结构
- 单向链表:每个结点包括两部分:一个是存储数据元素的数据源,另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next
双向链表
- 每个结点不止有一个后继指针next指向后面的结点
- 有一个前驱指针prew指向前面的结点
相比于单链表:
- 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址
- 支持双向遍历,增加操作的灵活性
总结
——————————————————————————————————————————————————
ArrayList和LinkedList的区别是什么?
1.底层数据结构
- ArrayList是动态数组的数据结构实现
- LinkedList是双向链表的数据结构实现
2.操作数据效率
-
ArrayList按照下标查询的时间复杂度O(1) 【内存是连续的,根据寻址公式】,LinkedList不支持下标查询
-
查询(未知索引):ArrayList需要遍历,链表也需要遍历,时间复杂度都是O(n)
-
新增和删除
- ArrayList尾部插入和删除,时间复杂度是O(1);其他部分增删需要挪动数组,时间复杂度是O(n)
- LinkedList头尾节点增删时时间复杂度是O(1),其他都需要遍历链表,时间复杂度是O(n)
3.内存空间占用
- ArrarList底层是数组,内存连续,节省内存
- LinkedList是双向链表需要存储数据,和两个指针,更占用内存
4.线程安全
-
ArrayList和LinkedList都不是线程安全的
-
如果需要保证线程安全,有两种方案:
-
在方法内使用, 局部变量则是线程安全的
-
使用线程安全的ArrayList和LinkedList
List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>()); List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());
-
——————————————————————————————————————————————————
HashMap
二叉树
红黑树
散列表(Hash Table)
散列表(Hash Table)又名哈希表/Hash表,是根据键(key)直接访问在内存存储位置值(Value)的数据结构,它是由数组演化而来的,利用了数组支持按照下标进行随机访问数据的特性。
1.什么是散列表?
- 散列表(Hash Table)又名哈希表/Hash表
- 根据键(key)直接访问在内存存储位置值(Value)的数据结构
- 由数组演化而来的,利用了数组支持按照下标进行随机访问数据
2.散列冲突
- 散列冲突又称哈希冲突,哈希碰撞
- 指多个key映射到同一数组下标位置
3.散列冲突-链表法(拉链)
- 数组的每个下标位置称之为桶(bucket)或槽(slot)
- 每个桶(槽)对应一条链条
- hash冲突后的元素都放到相同槽位对应的链表中或红黑树中
HashMap的实现原理
数据结构:底层使用hash表数据结构,即数组和链表或红黑树
- 往HashMap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
- 存储时,如果出现hash值相同的key,此时有两种情况。
- 如果key相同,则覆盖原始值
- 如果key不同(出现哈希冲突),则将当前的key-value放入链表或红黑树中
- 获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值
HashMap的jdk1.7和jdk1.8有什么区别
- JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合,数组中的每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可
- JDK1.8在解决哈希冲突时有较大的变化,当链表长度大于阙值(默认为8)时并且数组长度达到64时,将链表转化成红黑树,以减少搜索时间。扩容resize()时,红黑树拆分成树的结点数小于等于临界值6个,则退化成链表。
HashMap的put方法的具体流程
- HashMap是懒惰加载,在创建对象时并没有初始化数组
- 在无参的构造函数中,设置了默认的加载因子是0.75
- 判断键值对数组table是否为空或为null,否则执行resize()进行扩容(初始化)
- 根据键值key计算hash值得到数组索引
- 判断table[i] == null,条件成立,直接新建节点添加
- 如果table[i] == null,不成立
- 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value
- 判断table[i]是否为treeNode,即table[i]是否为红黑树,如果是红黑树,则直接在树中插入键值对
- 遍历table[i],链表的尾部插入数据,然后判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,遍历过程中若发现key已经存在直接覆盖value
- 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold(数组长度*0.75),如果超过,进行扩容
HashMap的扩容机制
- 在添加元素或者初始化的时候需要调用resize方法进行扩容,第一次添加数据初始化数组长度为16,以后每次都是达到扩容阙值(数组长度*0.75)
- 每次扩容的时候,都是扩容之前容量的2倍
- 扩容之后,会新创建一个数组,需要把老数组中的数据挪动到新的数组中
- 没有hash冲突的节点,则直接使用e.hash & (newCap - 1)计算新数组的索引位置
- 如果是红黑树,走红黑树的添加
- 如果是链表,则需要遍历链表,可能需要拆分链表,判断(e.hash & oldCap)是否为0,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上