java基础

HashMap

数据结构

数组

ArrayList和LinkedList的区别实值数组和链表的区别

用连续的存储单元存储数据。（有索引）

特点：查询快(O(1))，删除和插入慢(O(N))

注：因为连续的存储单元，所以新增，删除数据时，存储单元下标都要整体移动，进行插入和
删除。

image.png

链表

查询慢，插入快

产生hash冲突用链表

是一种物理存储单元上非连续，非顺序的存储结构（无索引）

特点：插入快，查找慢（插入，删除的时间复杂度为 O(1),查找遍历的时间复杂度为O(N)）

注：删除其实和插入一样，删除直接给值赋null，因为无索引，所以需要从头节点遍历到尾节点

image.png

算法：哈希算法（也叫散列）

就是把任意长度值（key）通过散列算法变换成固定长度的key（地址）通过这个地址进行访问的数据结构。

它通过把键值码映射到表中一个位置来访问记录，以加快查找速度。

即通过字符串算出它的ascii编码（阿斯克编码），进行mod（取模）,算出哈希表的下标。

ascii编码（阿斯克编码）会重复，mod（取模）来减少数组长度，产生哈希冲突（碰撞）

1.7之前插入，用头插法，头插法在多线程的时候会引起一些问题，如循环链表，耗尽cpu性能

为了解决这个问题，1.8后插入，采用尾插法

红黑树（O（logn））

查询比链表快，但是插入比链表慢

jdk8新增了红黑树数据结构

红黑树维持 小中大 左中右 这样的结构

TREEIFY_THRESHOLD =8 阙值 ？？因为有一个定理 根据统计学 统计出来的，叫泊松定理。

当链表的长度 >=8 时会转换为红黑树,小于用链表

线程池

原理：在线程池内创建一定数量的线程对象放到缓冲池里面，当来任务时候，把任务放在线程中执行；

当任务大于缓冲池中的线程时，可以先把任务放在队列中存储，等待之前任务执行完成，释放线程；

当队列（FIFIO原则，即先进先出）中的长度达到限制时，有些任务存储不下，线程池会再次创建线程对象，与队列中的进行完成任务；

当线程池线程数达到最大线程数时，执行拒绝策略；

待续。。。。。。。