定义

延时队列：顾名思义，是一个用于做消息延时消费的队列。但是它也是一个普通队列，所以它具备普通队列的特性，相比之下，延时的特性就是它最大的特点。

对于普通队列，如果队列里有数据，通过Pop方法可以立刻获取到队列的数据。

而对于延时队列，只有当队列里有数据，且该数据的指定消费时间小于等于当前时间，此刻该数据可被获取。

适用场景

延时队列适合用于设置一个定时器去触发某种事件的场景，如：

• 订单在十分钟之内未支付则自动取消。
• 优惠券过期提醒。

实现

先通过堆排序实现一个优先级队列，然后以时间为优先级，实现延时队列，队列里的元素指定的时间越小，优先级越高，就先出列，也就同时达到延时的效果、

面试官经常问到的一个问题，hashmap是如何实现的？今天我们就来说下原理

什么是hashmap?

map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射。而hashmap就是将key进行hash运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率极高

hash函数

根据输入的关键字得到固定长度的输出，通常是返回一个较大的整形。

hash映射

将通过hash运算得到的整数平均分配到指定位置，一般可以采用位运算或者模运算来实现。在性能方面，位运算的效率高于模运算。

寻址算法

地址是通过hash值映射得到的，那么hash映射后会出现不同的key对应到相同的地址，也就是所谓的hash冲突，为此解决冲突主要通过以下两种方法去寻址。

• 链表法：每个桶对应的是一个链表，通过遍历链表，找到对应的key。
• 开放地址法：根据初次映射的地址，遍历相邻的位置，找到对应的key。

在项目中，使用缓存是常见的提升性能的一个方法。为防止内存被无限制的消耗，使用内存缓存必须注意到一个淘汰策略，本文就介绍其中的一种算法：LRU。

什么时LRU？

LRU (Least recently used：最近最少使用)算法在缓存写满的时候，会根据所有数据的访问记录，淘汰掉未来被访问几率最低的数据。也就是说该算法认为，最近被访问过的数据，在将来被访问的几率最大。

简单的理解，就是当缓存需要淘汰时，先淘汰最早写入且最近没有被查询过的缓存元素。

前面介绍了BTree算法的实现，实际在数据库索引里用的是B+Tree。

概念

B+树是B树的一个变种算法，两者都是平衡多路查找树。

• 与BTree的区别

  1 2 3

  1.非叶子节点只存储键值信息，数据记录都存放在叶子节点中。 2.所有叶子节点之间都有一个链指针。 3.非叶子节点的关键字的个数与其子树的个数相同。

• 优点

  1 2 3

  1.IO效率更高：内部结点只有关键字，没有数据，一个结点可以容纳更多的关键字。查询时一次性读入内存中的关键字也就越多 2.查询效率稳定：因为数据全在叶子节点上，所以查询关键字的次数=树的深度，导致每一个数据的查询效率相当 3.方便范围查询：因为叶子节点之间是有链表的方式关联，所以可以直接依次查询指定范围的数据。不必重复索引。

实现

• 插入数据

  1 2 3 4 5

  1.插入数据时首先定位到数据所在的叶子节点，然后将数据插入到该节点，插入数据后的数组依然成正序排列。 2.若插入元素后该节点的关键字数量<=阶数，则直接完成插入操作即可。 3.若插入的关键字为该节点的最大值，则需要修改父节点的索引值。 4.若插入元素后，该节点的关键字数量>阶数，则需要想该节点分裂成两个节点，关键字的个数分别位floor((M+1)/2)和ceil((M+1)/2) 5.若分裂几点后导致父节点的关键字数目>阶数，则父节点也要进行相应的分裂操作。

• 查找数据

  1 2	1.根据关键字，找到对应的叶子节点。 2.对叶子节点进行遍历，找到关键字对应的数据。

• 删除数据

  1 2 3 4 5

  1.当删除某节点中最大或者最小的关键字，就会涉及到更改其双亲节点一直到根节点中所有索引值的更改。 2.删除关键字后，如果若当前节点中的关键字>=阶数/2,则直接完成删除操作 3.在删除关键字后，如果导致节点中的关键字个数<阶数/2,若其兄弟节点中含有多余的关键字，可以从兄弟节点借关键字 4.在删除关键字后，如果导致其节点中的关键字个数<阶数/2,并且其兄弟节点没有多余的关键字，则需要同其兄弟节点进行合并 5.节点合并后，需要修改父节点的关键字个数，若父节点的关键字个数<阶数/2,则递归处理。

本文将介绍btree的原理与golang的实现。

什么是Btree

B树是一种平衡的多路查找树。树，可广泛用于磁盘访问。 M阶树顺序的B树最多可以有m-1个键和M个子树。 使用B树的主要原因之一是它能够在单个节点中存储大量键，并且通过保持树的高度相对较小来存储大键值。

• 概念

  1 2 3

  根节点：最顶层节点 叶子节点：没有子树的节点就是叶子节点 度数：在树中，每个节点的子节点（子树）的个数就称为该节点的度（degree）。

• 特点

  1 2	1.每个叶结点具有相同的深度，也就是树的高度。 2.节点的元素以非降序排序，即x.k <= x.k1 <= ... <= x.kn。且 t-1 <=n <= 2t-1

使用场景

Btree主要用于提高访问数据的效率，比如数据库的索引文件。

实现

• 插入

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178

  package btree import "sort" // Item是一个接口类型，含有一个Less方法，通过这个接口可以实现类似泛型的功能。 type Item interface { Less(than Item) bool } // IntItem 定义元素类型为int型 type IntItem int // Less returns true if int(a) < int(b). func (a IntItem) Less(b Item) bool { return a < b.(IntItem) } // Items 元素数组 type Items []Item // find 查询元素对应的位置 // 比如数组为 [1,3,5], 查找3时，返回1, true;查找4时，返回2, false func (items Items) find(t Item) (index int, found bool) { // search方法使用二分搜索去返回元素中最小的满足[0,n)中最小的满足f(i)函数为true的索引i，如果f(i)为true，则f(i+1)也为true i := sort.Search(len(items), func(i int) bool { return t.Less(items[i]) }) if i > 0 && !items[i-1].Less(t) { // 当上一个元素刚好和t相等时，返回下标和true return i - 1, true } // 返回第一个大于目标元素的数组索引 return i, false } // insertAt 按指定位置插入一个Item func (items *Items) insertAt(index int, item Item) { *items = append(*items, nil) // 扩展一个位置出来 if index < len(*items) { // 可能index==len，需要插入的位置就在最后一个 copy((*items)[index+1:], (*items)[index:]) // 位置后面的往后挪一下 } (*items)[index] = item // 覆盖指定位置的数据 } // node 定义树的节点 type node struct { items Items // 元素数组 children children // 子节点的指针数组 } // split 将一个节点分裂成包含左右子节点的一个父节点，使得node的items和children减半，且父节点只保留中间一个元素 func (n *node) split(mid int) (Item, *node) { if len(n.items)-1 < mid { panic("error index") } upItem := n.items[mid] // 新增加一个节点 newNode := &node{} // 将原节点的元素分一半给新节点 newNode.items = append(newNode.items, n.items[mid+1:]...) // 原节点只保存一半 n.items = n.items[:mid] // 子节点也要分半 if n.children != nil { newNode.children = append(newNode.children, n.children[mid+1:]...) n.children = n.children[:mid+1] } return upItem, newNode } // maybeSplitChild 对children进行判断 // 1.node的items和children元素个数分别+1,保证不破坏btree的属性 // 2.保证了后续插入查询地柜下沉到node的某一个子树的时候，子树items未满 func (n *node) maybeSplitChild(childIndex, maxCap int) bool { l := len(n.children[childIndex].items) // 如果items已满，则进行一次分裂 if l >= maxCap { upItem, newNode := n.children[childIndex].split(l / 2) // 将中间的那个数据项插入到childIndex的位置 n.items.insertAt(childIndex, upItem) // 将新节点插入到children里，位置为childIndex+1 n.children.insertAt(childIndex+1, newNode) return true } else { return false } } // insert 插入元素 func (n *node) insert(item Item, maxCap int) Item { // 查找元素合适的插入位置 index, found := n.items.find(item) if found { return item } // 是叶子节点，直接将数据插入items if len(n.children) == 0 { n.items.insertAt(index, item) return nil } // 不是叶子节点，看看i处的子Node是否需要分裂， 这里的操作是为了保证后面进行插入下沉到子节点时，子节点n.children[index]一定未满 if n.maybeSplitChild(index, maxCap) { // 分裂了，导致当前node的变化，需要重新定位 // 保证插入查询能下沉到items符合范围的子树中 inTree := n.items[index] // 获取新升级的item switch { case item.Less(inTree): // 要插入的item比分裂产生的item小，i没改变 case inTree.Less(item): index++ // 要插入的item比分裂产生的item大，i++ default: // 分裂升level的item和插入的item一致，替换 out := n.items[index] n.items[index] = item return out } } // 递归插入到items符合插入范围的子树 return n.children[index].insert(item, maxCap) } // children 子节点 type children []*node // insertAt 按指定位置插入一个Item func (c *children) insertAt(index int, n *node) { *c = append(*c, nil) // 扩展一个位置出来 if index < len(*c) { // 可能index==len，需要插入的位置就在最后一个 copy((*c)[index+1:], (*c)[index:]) // 位置后面的往后挪一下 } (*c)[index] = n // 覆盖指定位置的数据 } type btree struct { degree uint // 树的度 root *node // 根节点 } // MinCap 返回节点元素个数的下界 func (tree *btree) MinCap() int { return int(tree.degree - 1) } // MaxCap 返回节点元素的上届 func (tree *btree) MaxCap() int { return int(2*tree.degree - 1) } // Insert 插入元素 func (tree *btree) Insert(item Item) Item { //如果是空树，则创建根后插入 if tree.root == nil { tree.root = new(node) tree.root.items = append(tree.root.items, item) return nil } // 判断根节点的元素个数是否已达上限 // 如果根结点已满，先对根节点进行分裂处理 if len(tree.root.items) >= tree.MaxCap() { midIndex := len(tree.root.items) / 2 upItem, newNode := tree.root.split(midIndex) newRoot := new(node) newRoot.items = append(newRoot.items, upItem) newRoot.children = append(newRoot.children, tree.root, newNode) tree.root = newRoot } return tree.root.insert(item, tree.MaxCap()) } func New(degree uint) *btree { return &btree{degree: degree} }

• 删除

• 查找

本文将介绍Bitmap的使用场景与算法实现。

什么是Bitmap

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。比如将第4位字节设为1，就代表某个集合已存在ID为4的记录。

适用场景

由于存储数据的是非常小的字节，所以bitmap能节省超大空间，可以用来处理大量数据的排序、查询以及去重。

实现

Bitmap

• 实现
  通过一个uint64的变量可以存储64位数据。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

  package bit // Bitmap 支持存储64个字节 type Bitmap uint64 func (b Bitmap) Set(pos uint64) Bitmap { // 1.根据位移运算，得到一个指定位置为1的数字，比如pos为4,则得到的是 0001 0000 // 2.通过按位异或运算将值设置上去 return b | (1 << pos) } func (b Bitmap) Clear(pos uint64) Bitmap { // 1.位移运算得到指定位置为1的数字，如：0001 0000 // 2.取反,如：1110 1111 // 3.按位与,如b为 0011 0000,最终结果为: 0010 0000 return b & ^(1 << pos) } func (b Bitmap) Has(pos uint64) bool { // 1.位移运算得到指定位置为1的数字，如：0001 0000 // 2.按位与,如b为 0011 0000,得到结果为：0001 0000 // 3.只要结果不为0,则证明该位上的值为1 return (b & (1 << pos)) != 0 } // toNums 读取数据 func (b Bitmap) toNums(offset uint64, nums *[]uint64) { for i := uint64(0); i < 64; i++ { if b.Has(i) { *nums = append(*nums, i+offset) } } } func (b Bitmap) Count() int { val := b // 将b的二进制分为32等份，计算每个部分含1的个数。 // 示例：10 11 10 01 00 11 10 11 00 01 10 01 10 00 01 00 10 11 10 01 00 11 10 11 00 01 10 01 10 00 01 00 // 经过运算：01 10 01 01 00 10 01 10 00 01 01 01 01 00 01 00 01 10 01 01 00 10 01 10 00 01 01 01 01 00 01 00 val = (val & 0x5555555555555555) + ((val >> 1) & 0x5555555555555555) // 后面的计算就是一步步地将每部分的值加起来 // 第1部分+第2部分，第3部分+第4部分，...第31部分+第32部分 val = (val & 0x3333333333333333) + ((val >> 2) & 0x3333333333333333) // 第1部分+第2部分，第3部分+第4部分，...第15部分+第16部分 val = (val & 0x0F0F0F0F0F0F0F0F) + ((val >> 4) & 0x0F0F0F0F0F0F0F0F) // 第1部分+第2部分，第3部分+第4部分，...第7部分+第8部分 val = (val & 0x00FF00FF00FF00FF) + ((val >> 8) & 0x00FF00FF00FF00FF) // 第1部分+第2部分，第3部分+第4部分 val = (val & 0x0000FFFF0000FFFF) + ((val >> 16) & 0x0000FFFF0000FFFF) // 第1部分+第2部分 val = (val & 0x00000000FFFFFFFF) + ((val >> 32) & 0x00000000FFFFFFFF) // 更为精简的操作 //val -= (val >> 1) & 0x5555555555555555 //val = (val>>2)&0x3333333333333333 + val&0x3333333333333333 //val += val >> 4 //val &= 0x0f0f0f0f0f0f0f0f //val *= 0x0101010101010101 return int(val) }

本文介绍在golang项目中，基于tcp协议的面向网络编程。

通信协议

一般来说，基于C/S架构实现的项目，都是基于长链接来实现的。协议有http、tcp、udp,重点介绍tcp。

流程说明

• 服务端

  1 2 3

  1.监听端口 2.接收客户端的tcp链接 3.创建goroutine,接收该链接的请求数据，并将相应数据发送给客户端。

• 客户端

  1 2 3

  1.建立与服务端的链接 2.发送请求数据，接收服务端返回的响应数据 3.关闭链接

• 时序图
  

在C/S模型下，需要服务端主动推送大量数据时，通过定时或按数量到达一定条件时，将数据批量取出，实现合并推送，减少推送次数。

定义

设计一个队列，将元素不停的往队列里添加，直到满足某个条件后，可以将多个元素一并取出。

• 接口说明

  1 2 3 4 5 6 7 8 9 10 11 12 13

  // Batcher 批处理接口 type Batcher interface { // 数据入列 Put(interface{}) error // 数据出列 Get() ([]interface{}, error) // 更新缓冲区 Flush() error // 弃用 Dispose() // 是否已弃用 IsDisposed() bool }

• 结构图
  

本文介绍在golang开发的过程中，如何进行性能分析与优化。

Golang的性能之谜

Golang号称高并发语言，我们是否还需要对golang项目进行性能分析与优化呢？答案当然是需要，因为就算再牛逼的语言，也会因为使用不当，写出来的代码性能很低。下面我们就来慢慢盘点golang的性能分析与优化。

sync.Mutex

在我们的项目中，某些时候为了保证并发情况下的安全性，需要用到锁。比如以下代码：

1

算法思想主要有分治算法、回溯法、贪心算法、动态规划法等，本文介绍分治算法。

定义

将一个复杂的问题分成两个或更多个相同或相似的子问题，求得子问题的解，再合并就得到原问题的解。其核心思想是“分而治之”。

基本思路

• 分：将一个问题分解成多个相似且足够小的子问题。
• 治：通常通过递归的方式，对子问题进行求解。
• 合并：将子问题的解合并得到原问题的解。

典型算法

快速排序

• 算法描述

  1 2 3

  1.选择数组的第一个数作为基数，将后面的数与之比较，较小的放右边，较大的放左边，分成2个数组。 2.通过递归的方式对上述两个数组再次拆分。 3.直到无法拆分为止，整个数组就变成有序的数组。

  快速排序的时间复杂度是 O(nlogn)。

• 实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  // QuickSort 快速排序,left为数组的第一个下标，right为数组的最后一个下标 func QuickSort(items []int, left, right int) { low := left // 临时变量,低位下标 high := right // 临时变量，高位下标 if low > high { // 无法再分，作为截止条件 return } flag := items[low] // 设置基数，用于对比 for low < high { // 循环条件 for low < high && items[high] >= flag { // 从右往左遍历，直到发现比基数小的数 high-- } items[low] = items[high] // 将较小的数放在低位地址 for low < high && items[low] <= flag { // 从左往右遍历，直到发现比基数大的数 low++ } items[high] = items[low] // 将较大的树放在高位地址 } items[low] = flag // 经过一轮遍历后，将基数赋值给低位地址，形成左边为比基数小的数组，右边为比基数大的数组 QuickSort(items, left, low-1) // 递归，分解 QuickSort(items, low+1, right) // 递归，分解 }

• 使用

  1 2 3 4 5

  func main() { items := []int{5,1,3,9,8,2,6,4,7} QuickSort(items, 0, len(items)-1) fmt.Println(items) }

归并排序

• 算法描述

  1 2 3

  1.分：将n个元素的序列分成n/2个子序列，每个子序列含两个元素。 2.治：比较子序列，形成有序数组。 3.合并：通过递归的方式，对两个数组进行排序并合并成一个数组。直到全部完成合并。

• 实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

  // 自顶向下归并排序，排序范围在[left,right)的数组 func MergeSort(items []int, left, right int) { // 元素数量大于1时才进入递归 if right - left > 1 { // 将数组一分为二 middle := (left + right) / 2 // 递归对左边的数组进行排序 MergeSort(items, left, middle) // 递归对右边的数组进行排序 MergeSort(items, middle, right) // 合并 merge(items, left, middle, right) } } // 归并 func merge(arr []int, low, middle, high int) { leftLen := middle-low // 左数组的长 rightLen := high-middle // 右数组的长 // 使用临时数组来存储将要排序的元素 temp := make([]int, 0, leftLen+rightLen) // 遍历对比两个数组的每个元素 l, r := 0, 0 for l < leftLen && r < rightLen{ lValue := arr[low+l] // 左边数组的元素 rValue := arr[middle+r] // 右边数组的元素 // 比较找到较小的，先放入临时数组 if lValue < rValue { temp = append(temp, lValue) l++ }else { temp = append(temp, rValue) r++ } } // 将剩下的元素追加到临时数组里 temp = append(temp, arr[low + l:middle]...) temp = append(temp, arr[middle+r:high]...) // 此刻临时数组已变成有序的，将其元素复制到原数组里 for idx, val := range temp { arr[low+idx] = val } }

思考

该如何在实际环境中使用到这种分治思想呢？