java基础知识分享

数组

1.数组的定义、下标

1.数组(Array)是一种用连续的内存空间存储相同数据类型
数据的线性数据结构。
2.数组下标为什么从0开始
寻址公式是：baseAddress+i*dataTypeSize,计算下标的内存地址效率较高
3.查找的时间复杂度
随机（通过下标）查询的时间复杂度是O(1)
查找元素（未知下标）的时间复杂度是O()
查找元素（未知下标但排序）通过二分查找的时间复杂度是0(log)
4.插入和删除时间复杂度
插入和删除的时候，为了保证数组的内存连续性，需要挪动数组元素，平均
时间复杂度为O(n)

2.扩容

ArrayList默认容量为10，每次扩容是当前容量N + N右移一位 故为1.5倍

3.Arrays.asList转换List之后，如果修改数组的内容，list会受影响吗？反过来呢

会 因为Arrays.asList使用的是数组的拷贝，并没有复制数据
反过来list转数组则不会受影响 因为底层实现是数组复制了list的数据

4.ArrayList和linkList的区别

	ArrayList	LinkList
底层结构	动态数组结构	双向链表
效率	查找快，新增删除（需要拷贝数据）慢	查找忙，新增删除快
空间	连续的内存空间 省	双向链表 需要存储头尾指针 更耗空间
线程安全	线程不安全 建议在方法内部使用	线程不安全

5.二叉搜索树、红黑树、散列表

二叉搜索树（Binary Search Tree, BST）
定义：
二叉搜索树是一种特殊的二叉树，它满足以下性质：

  1)节点的左子树只包含小于当前节点的数。
  2)节点的右子树只包含大于当前节点的数。
  3)所有左子树和右子树也分别为二叉搜索树。

红黑树（Red-Black Tree）
定义：
红黑树是一种自平衡的二叉搜索树，它通过维护额外的信息——每个节点的颜色（红色或黑色），来确保树的高度大致保持在log n级别，从而在插入、删除和查找操作中保持较高的效率。红黑树满足以下性质：

  1)每个节点要么是红色，要么是黑色。
  2)根节点是黑色。
  3)每个叶子节点（NIL节点，空节点）是黑色。
  4)如果一个节点是红色的，则它的两个子节点都是黑色的（也就是说在一条路径上不能出现相邻的红色节点）。
  5)从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
优点：

保证了在最坏情况下基本动态集合操作的时间复杂度为O(log n)。
是一种高效的查找树，同时也维持了排序顺序。
缺点：

相比于普通的二叉搜索树，红黑树的实现更复杂，因为它需要维护额外的信息（节点颜色）和进行旋转操作来保持树的平衡。
插入和删除操作比简单的二叉搜索树更耗时，因为它们需要额外的颜色检查和可能的树旋转

1.什么是散列表？
散列表(Hash Table)又名哈希表/Hash表
根据键(Key）直接访问在内存存储位置值(Vlue)的数据结构
由数组演化而来的，利用了数组支持按照下标进行随机访问数据
2.散列冲突
散列冲突又称哈希冲突，哈希碰撞
指多个key映射到同一个数组下标位置
3.散列冲突-链表法（拉链）
数组的每个下标位置称之为桶(bucket)或者槽(slot)
每个桶（槽）会对应一条链表
hash冲突后的元素都放到相同槽位对应的链表中或红黑树中

5.Hashmap的实现原理

hashmap是由数组+链表+红黑树 当链表长度大于8且数组长度大于64才会转化为红黑树，当红黑树节点数量小于6时转化为链表

6.HashMap put方法流程

HashMapl的put方法的具体流程
1.判断键值对数组table是否为空或为null,否则执行resize0进行扩容（初始化）
2.根据键值key计算hash值得到数组索引
3.判断table[叮==null,条件成立，直接新建节点添加
4.如果table[]==null,不成立
  4.1 判断table[i的首个元素是否和key一样，如果相同直接覆盖value
  4.2 判断table[i是否为treeNode,即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对
  4.3 遍历table[,链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入
      操作，遍历过程中若发现key已经存在直接覆盖value

7.扩容

讲一讲HashMap的扩容机制
。在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩
容都是达到了扩容阈值（数组长度*0.75）
·每次扩容的时候，都是扩容之前容量的2倍：
·扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
。没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置
·如果是红黑树，走红黑树的添加
·如果是链表，则需要遍历链表，可能需要拆分链表，判断e.hash&oldCap)是否为0，该元素的位置要么停留在原始位置，要么移
动到原始位置+增加的数组大小这个位置上

为什么扩容的数组长度是2的n次幂
1.重新计算索引速度更快
2.2的N次幂取模运算可以用 与运算代替

8.寻址算法

1.计算key的hashcode
2.对hashcode进行二次hassh 再使用扰动算法（ hash ^ hash>>>16 )右移16位再与原值进行异或运算）
3.2的指数n 取模运算可以用 hash&(n-1)代替 主要就是位运算更快

9.jdk1.7 hashmap死锁问题

jdk1.7 hashmap扩容时使用头插法，多线程迁移数据时，
数据假设为A->B一个线程读取了链表A 及下一个节点B。
这时候另一个线程扩容完成 导致链表数据为B->A，线程一执行时读取B的下一个节点为A 形成A-B-A
数据查找时遍历链表就会现成死循环

10.conHashMap

聊一下ConcurrentHashMap
1.底层数据结构：
JDK1.7底层采用分段的数组+链表实现
●
JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树
2.加锁的方式
●JDK1.7采用Segment分段锁，底层使用的是ReentrantLock
JDK1.8采用CAS添加新节点，采用synchronized锁定链表或红黑二叉树的首节
点，相对Segment分段锁粒度更细，性能更好