XIAOSUO 记录个人学习的足迹

摘要：什么是哈希算法 定义 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 如何设计一个优秀的哈希算法 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈希值。 哈希算法的常见应用 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 散列函数 散列函数中用到的哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。 负载均衡 需求 如何实现一个会话粘滞（session sticky）的负载均衡算法？也就是说，在一次会话中的所有请求都路由到同一个服务器上。 解决方案 通过哈希算法对客户端IP或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，就可以把同一个IP过来的请求都路由到同一个后端服务器上。 数据分片 如何统计“搜索关键词”出现的次数？ ①需求描述 假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？ ②问题分析 这个问题有两个难点，第一个是搜索的日子很大，没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据，处理时间会很长。 ③解决方案 先对数据进行分…… 阅读全文

摘要：什么是跳表 为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。 跳表的时间复杂度 计算跳表的高度 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。 计算跳表的时间复杂度 假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。 跳表的空间复杂度及如何优化 计算索引的节点总数 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为O(n)。 如何优化时间复杂度 如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。 高效的动态插入和删除 跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O…… 阅读全文

摘要：什么是二分查找 二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。 时间复杂度分析 时间复杂度 假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。 认识O(logn) 这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？ 因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。 由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。 如何实现二分查找 循环实现 func binarySearch1([]int a, val int) int { start := 0 end := len(a) - 1 for start = end { // 不要使用（start + end）/ 2 防止超出边界 mid := start + (end - start) / 2 if a[mid] val { end = mid - 1 } else if a[mid] val { start = mid + 1 } else { return mid } } return -1 } 注意事项： 循环退出条件是：start=end，而不是startend。 mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) 1)，因为相比除法运算来说，计算机处理位运算要快得多。 start和end的更新：sta…… 阅读全文

摘要：一、如何选择合适的排序算法？ 排序算法一览表 时间复杂度 是稳定排序？ 是原地排序？ 冒泡排序 O(n^2) 是 是 插入排序 O(n^2) 是 是 选择排序 O(n^2) 否 是 快速排序 O(nlogn) 否 是 归并排序 O(nlogn) 是 否 桶排序 O(n) 是 否 计数排序 O(n+k)，k是数据范围 是 否 基数排序 O(dn)，d是纬度 是 否 为什选择快速排序？ 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。 同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。 二、如何优化快速排序？ 导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下： 三数取中法 从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。 如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。 随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 警惕快排的递归发生堆栈溢出，有2中解决方法，如下： 限制递归深度，一旦递归超过了设置的阈值就停止递归。 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。 三、通用排序函数实现技巧 数据量不大时，可以采取用时间换空间的思路 数据量大时，优化快排分区点的选择 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致 四、Go语言排序函数的实现 golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作，是基于首中尾中值的很复杂的变种 func quickSort(data Interface, a, b, maxDepth int) { for b-a 12 …… 阅读全文

摘要：一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。 对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。 二、桶排序（Bucket sort） 算法原理： 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 使用条件 要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。 数据在各个桶之间分布是均匀的。 代码实现 func tongSort(values []int) { t := make([]int, 10) for _, val := range values { t[val]++ } res := make([]int, 0, len(values)) for index, val := range t { //循环把排序元素添加到新的数组中 for ; val 0; val-- { res = append(res, index) } } fmt.Println(res) } 适用场景 桶排序比较适合用在外部排序中。 外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。 应用案例 需求描述： 有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序 但内存有限，仅几百MB 解决思路： 扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。 第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。 每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。 将100个小文件依次放入内存并用快排排序。 所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。 注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。 三、计数排序（Counting sort） 算法原理 计数其实就是桶排序的一种特殊情况。 当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶 …… 阅读全文