Algorithm and DataStruture

线性表

Vector and ArrayList

静态链表

以定长数组来实现单链表

静态链表每个结点存放的”指针域”为游标即数组下标，以数组下标来指明下一结点地址

组成

备用链表与数据链表的组合构成一个静态链表

备用链表:

  • 头结点:
    a[0]
  • 其余链表结点:
    均只存放指向下一可利用空间的游标
  • 尾元结点
    置为0

数据链表:

  • 头结点:
    仅研究无头结点的 a[1]为第一个结点且存放数据
  • 其余链表结点:
    均只存放指向下一数据结点的游标
  • 尾元结点
    置为1

尾元结点
非数组的最后一个元素，而是最后一个有实际值的结点，游标值为-1

结点结构

1
2
3
4
5
6
typedef struct StaticLinkList {
	int data;
	int next;
}StaticList[MAXSIZE];
// 使用StaticList定义等价为  struct StaticLinkList xx[MAXSIZE];

用途
对于不支持指针的高级程序设计语言和数据元素长度固定不变

静态链表的优缺点：
优点：再插入和删除时候，只需要修改游标，不需要移动元素，从而改进了顺序存储结构中插入和删除操作需要移动大量元素的缺点。

缺点：没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性。

有无可利用空间表实现方式有区别

有序表的合并

链栈

循环队列

优先队列

阻塞队列

拓展空间

单链表逆置

判断单链表是否有环，如果有，求长度与入环点

散列表-哈希表

引例1: 取N个0-100之间的数后，给定一个数n判断n是否在取得N个数中

采用数组下标0-100 来代表0-100的数 下标对应的元素值代表是否为所取的N个数之一 是为1否为0 利用数组下标来映射要查找的值

若n=5 则只需判断a[5]是否等于1即可判断5是否为所取的N个数之一
哈希函数构造方法:直接定址法

引入散列表的概念

引例2: 若N的取值范围过大，内存消耗太大上述方法不可取，采用函数取模运算，由N%size的余数值来指明存储位置，此时数组下标标明的元素处不能再存01而是存实际的N值，在搜索N值时通过余数下标找到对应值所在位置 若使用01无法判断该余数对应哪一个N值(冲突)

引入哈希函数的概念Hash(key)
哈希函数构造方法:除模取余法

引例3: 不同N值余数却相同，发生冲突

冲突解决方法

  1. 开放定址(探测)
    若出现冲突，重新探测一个空闲位置插入
    优点:
    随机访问 访问速度快
    缺点:
    不利于删除 删除某结点后 存在查询不到已存结点的情况 此时可设置delete标志来解决
    扩容问题
  2. 链地址 hashmap
    头结点为相同余数结点 其余结点为余数相同的冲突结点
    优点:
    利于插入删除
    缺点:
    冲突数量过多导致查询效率下降
  3. 优化的链地址法 hashmap
    二叉查找树(退化为链表搜索效率低)->二叉平衡树(过严苛)->红黑树
    优点:
    利于插入删除且查找效率高
    缺点:
    无法存储大数据且线程不安全

JDK1.8 在”一定情况”下采用红黑树代替链表

条件: 节点个数大于8且节点个数达到阈值

哈希函数

作用: 计算key-value组成的Node对象在数组索引下标中的位置
考虑: 容易计算得到 方便查找 冲突要少

  • 通过hashcode()函数计算key值对应的整型哈希值hash

    hashcode()函数计算可以得到32bit的二进制数，但是返回值会转换为int类型10进制

  • 将该哈希值hash映射到对应数组索引下标位置

    一般会采用取模%运算，但是仅仅%运算冲突的概率大，在hashmap下利用率不高且链表过长，
    因此在length为2的整数次幂的条件下，采用&(length-1)来计算，此时可以仍然可得到0-length-1之间的数与%运算等效，但是仍有冲突问题，所以又将该hash值的高16位与低16位作异或运算，再作&运算求下标映射，可以很大程度上使各hash最后几位不同进而减少冲突 —作异或运算因为低位相同但是高位不同也会导致哈希冲突

1
2
3
4
5
6
//核心部分
int hash(Object key) {
	int h=key.hashCode();
	return (h^(h>>>16))&(capicity-1); //capicity表示散列表大小
}

采用&运算原因:

  1. 提高计算性能，二进制数进行运算
  2. 可对32bit的hash值进行处理，高16bit与低16bit进行异或运算，进而减少冲突

&(length-1)后可得到0-length-1之间的一个数值

一般哈希函数构造方法:

  1. 直接定址法
  2. 除模取余法
  3. 随机数法
  4. 数字分析法
  5. 平方取中法
  6. 折叠法

解决冲突

开放寻址

链地址

Hashmap

什么是hashmap:

  1. 整体是一个数组
  2. 每个数组元素是一个链表or树
  3. 链表中的结点中的value存储值

初始化

初始大小:

默认16
预估数据量大小 减少动态扩容次数 提高Hashmap性能
注意:初始大小必须为2的整数次幂，若不是则系统自动转换为临近的满足条件的大小
原因：

  1. 这样length-1的值才能高一位为0，其余低位均为1，使得&运算是结果取决于hash值的低位

负载因子:

默认0.75

阈值:

初始大小×负载因子
默认12

元素个数超过阈值(0.75*散列表初始大小) 启用动态扩容 扩大为原来的2倍
注意 这里元素个数不是散列表大小 而是已有的元素个数

put方法

  1. 通过hashcode方法计算key对象的hash值
  2. 使用该hash再通过哈希函数计算对应映射位置
  3. 判断当前元素个数是否大于等于阈值，若没有则继续，否则进行扩容
  4. 创建hash对应的key-value-next结点，判断映射位置处是否有其他结点插入，无则插入
  5. 已有其他结点插入
  • 若是链表 按链表方式进行存储(遍历链表 判断是否key相同 相同将value替代 不同则继续遍历到尾结点插入)
  • 若是红黑树 按红黑树的方式进行存储(则按照红黑树的规则遍历 key值相同替代 不同尾结点处插入)

扩容机制

hashmap采用懒扩容机制，仅在调用put方法时才会触发

  1. 扩容后容量变为原来的2倍
  2. 实际上是创建一个新的容量为原来2倍的数组并且需要将原数组元素进行迁移
  3. 重新计算各元素的哈希值，因为哈希函数计算映射内存时候用到了size

优化

  1. 红黑树引入
  • 链表长度到8,且数组长度到64
  1. 初始化时候注意初始大小与负载因子的设置 减少动态扩容次数

Hashtable

synchronized

线程安全 对每一个操作上锁，同步约束，但是性能三者最差

与hashmap的区别；

  1. 初始容量为11
  2. key值与value值不能为null 因为其hash函数没有对null情况作处理
  3. 扩容后为2倍原容量+1

    ConcurrentHashmap

    分段锁

一致性哈希算法

树

树的非递归遍历

决策树

线索二叉树

在某种遍历次序下可以找寻某结点在该遍历次序下的前驱后继结点

实现:

n个结点的二叉树有n+1空指针域，若某结点左指针域为空，则使该指针域指向其某种遍历次序下的直接前驱，右->直接后继

结点结构:

增设两个int型的标志域，ltag，rtag 若为0，指向孩子结点，若为1指向线索

优化：

增设一头结点，该头结点左指针域指向原头结点，右指针域指向遍历次序的最后一个结点
解决遍历序列两端结点指针域悬浮问题，悬浮的指针域指向该头结点即可

线索化：

写出对应遍历序列，遍历所有结点，结点孩子为空指针则将该指针域线索化

代码：

略

赫夫曼树

B-树–B+树

数据库的底层结构为B+树

引例:

  1. select user from User where id=100
  2. select user from User where id<100
  3. select user from User where id<100 and name=’李勇’

选择底层结构考虑因素

数据量庞大，无法存储与内存中，只能存储于磁盘中，因此涉及磁盘读取问题，一次读取一页(磁盘1页可存16K数据)
既存在精确查找还存在范围查找，部分查找
每个结点需要能存放足够多的数据

数据库不使用红黑树做底层结构的原因

红黑树一个结点只能存放一个数据，然后读取磁盘一次读取一页16k的数据，磁盘IO时间消耗太大(读取次数多且一次读取浪费的空间也多)，且树过长

解决方法

一个结点存多个数据
多叉树

B-树

M阶B-树的重要特性

结点最多有m颗子树，m-1个关键字，m>=2
除了根节点和叶子结点外，其余各结点至少有ceil(m/2)个结点，ceil为上取整
非叶子结点的根结点至少有两颗子树

M阶B-树的构建过程

  • 有序添加

    添加关键字时保证树满足排序树性质

    结点添加数据后结点中关键字有序

    找叶子结点添加

  • 中间分裂 若M为偶数，取中间考前考后均可

    当根结点的关键字个数等于阶数时，从m/2关键字处分裂，该关键字单独构成一个结点，其两颗子树分别为其原始左边所有关键字组成的新结点与其原始右边所有关键字组成的新结点

    当非根节点的关键字个数等于阶数时，中间分裂，分裂出的关键字有序添加在该结点的父节点中，该结点以该关键字为中心再次分裂为两个结点作分裂关键字的”左右子树”

缺点

结点存放索引+数据地址，数据地址占用大量空间
范围查找时，仍需遍历每个结点以获取数据，使得索引失效
操作复杂，查找每个结点均需要 磁盘中去取索引 ->数据地址 ->提取记录 稳定性不强

B+树

M阶B+树的重要特性

结点最多有m颗子树，m个索引，m>=2
除了根节点和叶子结点外，其余各结点至少有ceil(m/2)个索引，ceil为上取整
非叶子结点的根结点至少有两颗子树
叶子结点的高度一致

注意: 条件上与B-树的区别

  1. B+树仅有叶子结点存储数据，其余结点均仅存索引
  2. B+树叶子结点互连成一个双向链表
  3. B+树的各结点最大索引数限制为m阶数

M阶B+树的构建过程

  • 有序添加

    添加关键字时保证树满足排序树性质

    结点添加数据后结点中关键字有序

    找叶子结点添加

  • 最值分裂

    区别在于结点中索引数满阶时不再是从中间开始分裂，而是从最值(最大，最小索引)处分裂

  • 删除关键字 不完善哈

    关键字在终端结点

    1. 若该关键字所在结点的关键字数目比最小临界大，则直接删
    2. 否则无法直接删除，看其兄弟结点的关键字数是否大于最小临界，大于则借
    3. 否则需要与兄弟结点合并

关键字不在终端结点

  1. 关键字所在结点中关键字数大于最小临界，用其相邻关键字替代(左子树中最大或右子树中最小)
  2. 关键字所在结点中关键字数不大于最小临界，先合并后再删除

优点

  1. 仅叶子结点存储数据，大大提高了页空间利用率
  2. 叶子结点互连为双向链表，范围查找时，仅需找到边界处，根据此双向链表遍历查找即可，无需再依次访问磁盘提取
  3. 分裂时从最值处分裂，这样对应索引引向的子树结点均为大于or小于该索引值的索引，结点的最大索引数变为阶数，也使得叶子双向链表有序，方便遍历

阶数M

由磁盘页的大小与字段大小决定

组合查询

  • 最左原则
  • 叶子结点不存数据记录，而是存组合索引以及对应记录的记录地址

平衡二叉树-AVL

红黑树