跳至主要內容

算法

hu18650大约 17 分钟

[toc]

算法

1. 数据结构

1.1 数组(Array)

相同类型的元素(element)组成,并且使用一块连续的内存来存储.
可以利用元素的索引(index)可以计算出该元素对于的存储地址.

特点: 提供随机访问并且容量有限

访问: O(1) // 访问特定位置元素
插入: O(n) // 最坏情况插入在头部并需要移动所有元素
删除: O(n) // 最坏情况删除在头部并需要移动所有元素

1.2 链表(LinkedList)

相同类型的元素(element)组成, 并不会按线性顺序存储数据, 使用不连续的内存空间来存储数据.

优点: 克服了数组需要预知数据大小的缺点. 充分利用计算机内存空间, 实现灵活的内存动态管理.
缺点: 比内存占用更多空间(每个节点还要存放指向其他节点的指针). 不具有数组随机读取的能力

访问: O(n) // 查找某个节点或者访问某个特定位置, 最坏情况为最后一个
插入: O(1) // 只需要知道目标位置元素的上一个元素即可
删除: O(1) // 只需要知道目标位置元素的上一个元素即可

应用场景:

  • 存储数据元素个数不确定, 需要经常添加删除

与数组区别:

  • 数组支持随机访问, 链表不支持
  • 数组使用连续内存空间, 对CPU缓存机制友好, 而链表不行
  • 数组大小固定, 而链表天然支持动态扩容. 如果数组声明过下, 需要另外申请更大内存空间存放数组元素, 然后将原数组拷贝进去, 比较耗时

1.2.1 单链表

只有一个方向, 节点只有一个后继指针next指向后面的节点. 因此在物理内存不连续.
链表第一个节点不保存任何值的head节点(头节点), 通过头节点可以变量整个链表, 尾节点指向null

1.2.2 双向链表

特殊的单链表, 尾节点指向链表头节点.

1.2.3 循环链表

节点包含2个指针, 一个prev指向前一节点, next指向后一节点

1.2.4 双向循环链表

头节点prev指向尾节点, 尾节点的next指向头节点. 构成一个环.

1.3 栈(stack)

只允许有序的线性数据集合一端(称为栈顶)进行加入数据(push)和移除数据(pop), 按照后进先出(FIFO, Last In First Out)原理运作. 在栈中, push和pop操作都发生在栈顶.

访问: O(n) // 最坏情况方位最坏一个元素
插入: O(1) // 顶端插入
删除: O(1) // 顶端删除元素

常用场景:

  • 浏览器回退前进功能
  • 检查符号是否成对出现
  • 反转字符串
  • 维护函数调用

实现:
可以通过数组实现, 也可以通过链表实现. 不管基于数组还是链表, 入栈和出栈时间复杂度为O(1)
push()(放入数据), pop()(返回栈顶元素并出栈), peek()(返回栈顶元素不出栈)等待

1.4 队列(queue)

先进先出(FIFO, first in, first out)的线性表. 具体实现通常用链表或者数组实现. 数组实现队列叫顺序队列, 链表实现队列叫链式队列. 队列只允许在尾端(rear)进行插入操作(入队enqueue), 在前端(front)进行删除操作(出队dequeue).

访问: O(n) // 最坏情况方位最坏一个元素
插入: O(1) // 后端插入
删除: O(1) // 前端删除元素

应用:

  • 阻塞队列: 队列基础上加上阻塞操作. 队列为空,出队阻塞, 队列满, 入队阻塞. 很容易实现生产者-消费者模型
  • 线程池种请求/任务队列: 线程池无空闲线程, 任务加入到队列种等待执行, 分无界对了(基于链表)和有界队列(基于数组)
  • Linux内核进程队列(基于优先级)
  • 消息队列
  • 等等

1.4.1 单队列

分为顺序队列(数组实现), 链式队列(链表实现)

当顺序队列进行出队入队操作, front和rear持续往后移动, rear移动到最坏,无法往队列添加数据, 即使有空余空间, 称为"假溢出". 还存在rear越界问题. 为了避免: 引入2个指针, front执行头元素, rear执行尾元素下一个位置, 当front等于rear事, 队列就是空队列

1.4.2 循环队列

顺序入队出队, 当加入队伍到最后一个元素, rear指针就移动到对头, 这样循环出入队.
当front == rear时, 有可能为满, 有可能为空.2种解决办法:

  1. 设置标志位flag. 当front==rear且flag=0为空, flag=1为满
  2. 队列满时保证数组还有一个空闲位置, rear指向空闲位置. 判断为满条件就是(rear+1)%QueueSize = front.

1.5 图

图就是由顶点的有穷非空集合和顶点之间的边组成G(V, E), G代表图, V代表顶点, E代表边

  • 顶点: 图中数据元素, 图至少由一个顶点
  • 边: 顶点之间的关系用边标识
  • 度: 顶点包含多少条边. 有向图种还区分出度(该顶点出去的边), 入度(进入该顶点的边)
  • 无向图: 顶点关系是双向的, 就不用关注方向, 不用带箭头的边表示
  • 有向图: 顶点关系是有向的
  • 无权图: 只关心关系的有无, 不关心关系的强弱
  • 带权图: 即关心关系有无, 又关心关系强度(一般描述距离等). 带权边一个数值表示权值, 代表关系的强度

1.5.1 图的存储

1.5.1.1 邻接矩阵存储

用二维矩阵存储. 邻接矩阵比较浪费内存空间. 无向图的邻接矩阵是一个对称矩阵, 顶点i,j有关系, 那么j,i必定有关系.

  1. 顶点i和顶点j有关系,且权值为n, 那么图A[i][j]=n;
  2. 无向图只关心关系有无, 那么图A[i][j]=1; 无关系则图A[i][j]=0;
1.5.1.2 邻接表存储

用一个链表来存储某个顶点的所有后继相邻顶点. 对于顶点Vi, 把所有邻接与Vi的顶点Vj组成单链表, 这个单链表称为Vi的邻接表

1.5.2 图搜索

1.5.2.1 广度优先搜索
  1. 将要搜索的源顶点放入队列
  2. 去除队首节点, 并放入输出, 将首节点后继节点(未访问)放入队列(注意, 如果后续节点在队列中已存在, 则不加入队列)
  3. 循环上面的过程
  4. 最后一个节点后续顶点为空(没有未访问过顶点). 队列为空, 结束
1.5.2.2 深度优先搜索
  1. 将要搜索的源顶点放入栈
  2. 取出栈顶, 并放入输出, 将首节点后继节点(未访问)放入栈(注意, 如果后续节点在队列中已存在, 则不加入队列)
  3. 循环上面的过程
  4. 最后一个节点后续顶点为空(没有未访问过顶点). 栈为空, 结束
1.4.2.3 区别

广度使用队列(队列头都是先同级再下级), 深度使用栈(栈都是先下级, 再返回网上找上级)

1.6 堆

堆是满足条件的树: 每个节点值都大于或者等于(或者小于等于)子树中所有节点值.

堆不一定是完全二叉树, 只是为了方便存储和索引, 用完全二叉树形式来表示堆.
可以看成近似的完全二叉树

用途: 当只关心所有数据中的最大值或者最小值, 存在多次获取最大值最小值, 多次插入删除时, 就可以使用堆.

有序数组: 初始化O(你log(n)), 查找最大最小值(O(1)), 更新(插入删除))(O(n))
堆: 初始化(O(nlog(n))), 查找最大最小值(O(1)), 更新(插入删除))(O(log(n)))

  • 最大堆: 每个节点值都大于子树所有节点值
  • 最小堆: 每个节点值都小于子树所有节点值

1.6.1 堆存储

使用数组存储二叉树, 又方便索引
根节点序号为1, 树中任意节点i, 左子树序号为 2i, 右子节点序号为2i+1

digraph heap {
  "21" -> "15"
  "21" -> "19"
  "15" -> "10"
  "15" -> "7"
  "10" -> "5"
  "10" -> "2"
  "19" -> "3"
  "19" -> "1"
}
index0123456789
value-2115191073152

插入
模拟最大堆:

  1. 先将要插入的数据放入最后
  2. 从底向上, 如果父节点比该元素小,则该节点和父节点交换, 直到无法交换为止

删除
删除堆顶元素后, 为了保持堆的性质, 需要对堆结构进行跳转, 过程称为堆化.分为2种

  1. 自顶向上堆化
    a) 删除堆顶元素, 使下标为1的位置空出
    b) 比较叶子节点, 也就是下标为2,3的数组元素, 较大的填充到1的位置
    c) 循环比较空出来的左右子节点. 较大者转移到空位, 直到堆的最底部

这时可以发现可能再数组种出现了null值(气泡), 导致存储空间的浪费.

  1. 自顶向下堆化
    a) 删除堆顶元素, 使下标为1的位置空出
    b) 将最后一个元素移至堆顶
    c) 不断下沉, 比较左右节点, 按照插入的逻辑执行, 让子节点沉下去

这样就不会有气泡产生了.

1.6.2 堆排序

堆排序分为2个步骤

  1. 建堆: 将一个无序数组建立一个堆
    a) 最后一个元素的父节点及其之前的元素(也就是所有最底层节点上的中间节点), 都是非叶节点. 如果节点个数为n, 那么就需要对n/2到1的节点进行自顶向上(沉底)堆化
    b) 那么就从n/2到1开始, 从n/2节点开始进行下沉操作,一直到1号为止
    c) 对应树完成一个最大堆

  2. 排序, 将堆顶元素取出, 剩余元素进行堆化, 反复迭代,直到所有元素取出为止.
    a) 采用自顶向下(沉底)堆化, 一开始将末尾移至堆顶, 将取出的最大元素放入队尾
    b) 再往继续执行, 将栈顶元素放入倒数第二个, 倒数第二个在剩余堆(去除倒数2个数)情况下继续自顶向下堆化
    c) 递归, 直到只有一个元素, 放入顶层. 堆化完成
    d) 整个排序完成

1.7 树

现实种倒的树. 每个非空树只有一个根节点
特点:

  1. 任意两个节点, 有且仅有唯一一条路径联通
  2. 如果有n个节点, 那么有n-1条边
  3. 不包含回路

1.7.1 二叉树

每个节点最多只有2个分支的树结构, 分支通常称为"左子树", "右子树", 且分支具有左右次序, 不能随意颠倒, 第i层最多有 2(i-1)个节点, 深度为k的二叉树最多有2k-1个节点

满二叉树: 每层节点都达到最大值.深度为k的二叉树有2k-1个节点

完全二叉树: 除最后一层外, 剩余层都是满的, 并且最后一层要么满, 要么是在右边缺少连续若干节点. 性质: 父节点和子节点序号有对应关系. 若父节点序号为i, 左节点序号为2i, 又子节点序号为2i+1 (见堆图)

平衡二叉树: 可以是一个空树, 如果不为空树, 左右两个子树高度差不能超过1, 并且左右两个子树也是平衡二叉树.

下图也是一个平衡二叉树(节点0左子树高度为0, 右子树高度为1, 符合条件)

digraph heap {
  "0":se -> "1":nw
  "1":se -> "2":nw
  "2":se -> "3":nw
}

上图这种树已退化成链表, 叫斜树.

二叉树由于父子节点和兄弟节点又特殊关系, 可在搜索和修改时, 相对于链表更加快捷遍历.

所以希望在父节点, 左子树和右子树节点尽可能一样多, 相差不超过1层.

存储:
链式存储: 数据data(不一定单一数据, 可是多种不同类型), 左节点指针left, 右节点指针right

顺序存储: 数组存储. 每个位置仅存节点数据data. 根节点为1, 如果存储在数据下标为i的位置, 左子节点为2 * i的位置, 右子节点存储在2 * i+1位置. 如果存储的不是完全二叉树, 数组种就会出现空隙, 导致内存利用率降低

遍历:
前序遍历: 先遍历根节点, 再递归找左节点, 再从下往上找右节点.

public void preOrder(TreeNode root){
	if(root == null){
		return;
	}
	system.out.println(root.data);
	preOrder(root.left);
	preOrder(root.right);
}

中序遍历: 先遍历中序中左子树, 再输出根节点, 再中序遍历右子树

public void inOrder(TreeNode root){
	if(root == null){
		return;
	}
	inOrder(root.left);
	system.out.println(root.data);
	inOrder(root.right);
}

后序遍历: 是先递归后序遍历左子树, 再递归后序遍历右子树, 最后输出根结点的值

public void postOrder(TreeNode root){
	if(root == null){
		return;
	}
	postOrder(root.left);
	postOrder(root.right);
	system.out.println(root.data);
}

1.7.2 红黑树

TreeMap, TreeSet, HashMap中都用到
特点:

  1. 每个节点非黑即红
  2. 根节点都是黑色
  3. 每个叶子节点都是黑色的空节点(nil节点)
  4. 如果节点是红色, 那么它的子节点必须是黑色的(反之不一定)
  5. 从根节点到叶节点或空节点的每条路径, 必须包含相同数目的黑色节点(即相同的黑色高度)

1.7.3 B-树

1.7.4 B+树

1.7.5 B*树

1.7.6 LSM树

2. 排序

2.1 冒泡排序

  • 比较相邻元素, 如果第一个比第二个大,交换两个
  • 对每一对相邻元素做相同工作, 从开始到结尾, 最后元素就是最大数
  • 针对所有元素重复以上步骤, 除了最后一个
  • 重复步骤, 直到排序完成
    最佳情况: O(n), 最差情况O(n2), 平均O(n2)

2.2 选择排序

最稳定排序, 时间复杂度都是O(n2). 唯一好处不占用额外内存空间.

  • 从首位元素开始遍历
  • 如果当前位与后面所有位比较, 比当前位小则交换数据, 直到末尾
  • 再开始比较第二位, 第三位.. 直到末尾位完成排序

时间复杂度: O(n2)

2.3 快速排序

通过一趟排序将待排序记录分隔位独立的2个部分, 一部分记录的关键字均比另外一部分关键字小. 则分别对这两部分继续排序, 以达到整个序列有序. 分治法

  • 从数列选择一个元素作为基准
  • 重新排列数列, 所有与那苏比基准值小的摆放到基准之前, 大的放到之后. 相同可放到任意边.在这个分区退出后, 该基准就处于数列中间位置, 这个过程称为分区
  • 递归把小于基准的子数量和大于基准的子数列排序

最佳情况: O(nlog(n)), 最差情况O(n2), 平均O(nlog(n))

3. 查找

3.1 二分查找

效率较高的查找方法, 前提时数据结构必须排序. 缺点是待查表为有序表. 且插入删除困难.

二分查找计算中间值: mid = low + (high - low)/2. (如果使用(low + high)/2存在数据溢出风险)

时间复杂度: O(log2n)

5. 其他算法

5.1 布隆过滤器

位数组判断一个元素是否属于这个集合(存在误报), 但不在这个集合肯定不在.

错误率估计:

  1. m位的位数组中, 没被设置位1的概率为(1−1/m)(1-1/m)
  2. k个hash函数映射到n个元素, 需要计算 k*n给位置1. 那么计算之后, 某位仍为0的概率为(1 - 1/m)kn, 约为 e(-kn/m), 错误概率为 1-e(-kn/m)

最优hash函数个数:
当e(-kn/m), 出错概率为最低, 即当 k=ln(2)*(m/n)时, 错误率最低, 这时错误率为(1/2)k = 0.6189(m/n)

位数组大小选择:
给定错误率E, 可以推算出 m>n * log2(1/E)时, 错误概率不会超过E, 上面推算出k=ln(2) * (m/n)时, 出错率最低, 为了让错误率再hash函数最优解时, 错误率不会超过E, m>=log2(e)* (n *log2(1/E)). 这个值正常情况下m最小值的1.44倍

hash函数的选择
hash函数k=ln(2)*m/n时, 错误率最低0.6185m/n.例如哈希函数个数k取10, 位数组大小m设为字符串个数n的20倍时, false positive发生的概率是0.0000889. hash函数的选择应该使得同一个元素的hash值分布的尽量的分散, 减少这K个hash函数的冲突率, 最简单的方式是使用同一个hash函数, 但这个hash函数使用不用的k个参数

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true); // 根据hash结果, 获得hash值, 将hash值的对应的bit位设置为1
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

5.2 一致性hash算法

普通hash函数最大作用是散列, 在形式上具有相同性质的数据, 打散成随机的, 均匀分布的数据. 如果hash 集群发生数量N的变化. 之前的Hash映射就全部失效.
一致性Hash通过构建环状hash空间代替线性hash空间来解决问题

原理:

  1. 将整个hash值空间组织成一个虚拟圆环, 如某hash函数H的值空间为0 - 231-1. 那么整个hash空间环为: 整个空间按照顺时针方向组织, 0和231-1在零点方向重合.
  2. 对服务器使用hash进行一次hash, 选择服务器的ip或者主机名作为关键字hash, 就可以确定每台及其在hash环上的位置.
  3. 将数据key使用相同的hash函数计算出哈希值, 并确定此数据在环上的位置, 并此位置沿环顺时针行走, 第一台遇到的服务器就是该定位到的服务器.
  4. 当其中一台宕机, 这台服务器对应的key被重定位到下一个节点. 受影响的数据仅此服务器在其环空间中的前一台服务器(沿逆时针方向行走遇到的第一台服务器)之间的数据, 其他不受影响
  5. 增加一台服务器, 受影响的数据仅此新服务器在其环空间中的前一台服务器(沿逆时针方向行走遇到的第一台服务器)之间的数据, 其他不受影响
上次编辑于:
贡献者: hu18650