数据结构

数组

数组是一种用连续的内存空间存储相同数据类型的线性数据结构

数组下标为什么从0开始

寻址公式是：baseAddress+i*dataTypeSize

计算下表的内存地址效率较高，少一次加减操作

数组查找的时间复杂度

1.通过下标查询O(1)

2.位置下标查找O(n)

3.位置下标但排序，二分法查找O(logn)

插入与删除时间复杂度

插入和删除时，为了保证数组内存的连续性，需要挪动数组元素，平均时间复杂度为O(n)

ArrayList底层的实现原理

1.ArrayList底层使用动态数组实现的

2.ArrayList初始容量为0，当第一次添加数据时才会初始化为10

3.ArrayList在进行扩容时容量是原来的1.5倍，每次扩容都要拷贝数组

4.ArrayList在添加数据时

a.确保数组已使用长度(size)加1之后足够存下一个数据

b.计算数组的容量,若当前数组已使用长度+1后的大于当前的数组长度,则用grow方法扩容(1.5倍)

c.确保新增的数据有地方存储之后,则将新元素添加到位于size的位置上

d.返回添加成功布尔值

ArrayList list = new ArrayList(10)中的list扩容几次

无扩容,用add方法时才扩容

如何实现数组和list之间的转换

List转为array是toArray, array转为List是asList

list转array,修改list后array不影响

array转list,修改arrat后list也会修改

ArrayList和LinkedList的区别

1.底层数据结构

a.ArrayList是动态数组的数据结构实现

b.LinkedList是双向链表的数据结构实现

2.操作数据效率

a.查找已知索引:ArrayList是O(1),LinkedList是O(n)

b.查找未知索引:都是O(n)

c.新增与删除:arraylist尾部是O(1),其余是O(n)

​ Linkedlist头部是O(1),其余是O(n)

3.内存空间占用

1.ArrayList底层是数组,内存连续,节省内存

2.LinkedList底层是双线链表,需要存储数据和两个指针,更占用内存

4.线程安全

ArrayList和LinkedList都不是线程安全的

若要保证线程安全,有两个方案

a.在方法内使用,局部变量是线程安全的

b.使用线程安全的ArrayList与LinkedList—>加锁SynchronizedList

二叉树

二叉搜索树(子节点左小右大): 查增删(一般是O(logn), 极端是O(n))

红黑树:是一种自平衡的二叉搜索树

红黑树的5个性质:

1.节点要么是红色,要么是黑色

2.根节点都是黑色

3.叶子节点都是黑色的空节点

4.红黑树中红色节点的子节点都是黑色

5.从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点时,若不符合这些性质会发生旋转,以达到所有性质

增删查都是O(logn)

什么是散列表(哈希表)

1.散列表又名哈希表

2.根据键(key)直接访问在内存存储位置值(value)的数据结构

3.由数组演化而来,利用了数组支持按照下标随机访问数据

散列冲突

1.散列冲突又称哈希冲突,哈希碰撞

2.指多个key映射到同一个数组下标位置

散列冲突-链表法(拉链)

1.数组的每个下表位置称之为桶(bucket)或槽(slot)

2.每个bucket都会对应一条链表或红黑树

3.hash冲突后的元素都会放到相同槽位对应的链表或红黑树中

Hashmap的实现原理

1.底层使用hash表(散列表)数据结构,即数组+链表;红黑树

2.添加数据时,计算key的值确定元素在数组中的下标

a.key相同则替换

b.不同则存入链表或红黑树中

获取数据通过key的hash计算数组下表获取元素

HashMap的jdk1.7和jdk1.8有什么区别

1.jdk1.8之前采用拉链法,数组＋链表

2.jdk1.8之后采用数组+链表+红黑树,链表长度大于8且数组长度大于64则会从链表转化为红黑树

HashMap的put方法的具体流程

1.判断链值对数组table是否为空或null,否则执行resize()进行扩容

2.根据键值key计算hash值得到数组索引

3.判断table[i]==null,条件成立就直接新建节点添加

4.若table[i]==null不成立,则

a.判断table[i]的首个元素是否和key一样,若相同则直接覆盖value

b.判断table[i]是否为treeNode,即table[i]是否为红黑树,如果是红黑树,则直接在树中插入键值对

c.遍历table[i],链表尾部插入数据然后判断链表长度是否大于8,大于8转为红黑树,在红黑树中执行插入操作,遍历过程中若发现了key已经存在则直接覆盖

5.插入成功后,判断实际存在的键值对size是否超过了最大thread(数组长度*0.75),若超过就扩容

HashMap的扩容机制

1.在添加元素或初始化时需要调用resize方法进行扩容,第一次添加数据初始化数组长度为16,以后每次扩容都是达到了扩容阈值(数组长度*0.75)

2.每次扩容的时候都是扩容之前容量的2倍

3.扩容之后会新创建一个数组,需要把老数组中的数据挪动到新的数组中

a.没有hash冲突的节点,则直接使用e.hash&(newCap-1)计算新数组的索引位置

b.如果是红黑树,则走红黑树的添加

c.如果是链表则需要遍历链表,可能需要拆分链表,判断e.hash&oldCap是否为0,若为0,该元素停留在原始位置,否则移动至原始位置+增加的数组大小这个位置上

HashMap的寻址算法

1.计算对象的hashcode()

2.再进行调用hash()方法进行二次哈希,hashcode值右移16位再异或运算,让哈希分布更为均匀

3.最后(capacity-1)&hash得到索引

为何HashMap的数组长度一定是2的次幂

1.计算索引时效率更好:如果是2的n次幂可以使用位与运算代替取模

2.扩容时重新计算索引效率更高:hash&oldCap==0的元素留在原来的位置,否则新位置=旧位置+oldCap