golang本身对常用集合的封装还是比较少的，主要有数组（切片）、双向链表、堆等。在工作中可能用到其他常用的集合，于是我自己对常用的集合进行了封装，并对原理做了简单介绍，代码库地址：，代码都是经过测试的，欢迎下载使用，反馈的问题我会第一时间修复
arraysort使用数组保存数据，新增的时候通过类似二分查找找到插入位置，插入位置后面的数据往后移动一位，插入新元素，查找就是二分查找，删除就是通过二分查找找到对应的元素，之后的元素都向前移动一位。时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(n) |
| 删除 | o(n) |
| 查找 | o(logn) |
通过链表头指针和链表尾两个指针将所有元素链接在一起，可以快速的在表头和表尾插入元素，删除和查找都是遍历链表，查找对应的元素，删除还需要改变指针指向。时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(1) |
| 删除 | o(n) |
| 查找 | o(n) |
队列先进先出，循环队列采用数组保存元素，以循环的方式在数组中添加元素，当数组写满之后自动扩容，元素个数小于1m时二倍扩容，大于等于1m时每次加1m，删除元素的时候需要将对应的位置赋值为空指针，方便被删除的元素被回收。时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 进队列 | o(1) |
| 出队列 | o(1) |
队列先进先出，实现和单链表类似，进栈是在表尾添加元素，出栈就是表头出栈，即表头指向表头的下一个元素，相对数组实现的循环队列，链表队列不存在扩容的问题，但每个元素多了一个指针。时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 进队列 | o(1) |
| 出队列 | o(1) |
优先级队列采用小堆实现，小堆采用数组保存数据，按照完全二叉树的方式操作数据，每个节点的值都小于等于左右子节点的值，保证了每次出队的都是最小值，即按照顺序出队。
时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 进队列 | o(logn) |
| 出队列 | o(logn) |
栈先进后出，采用数组保存元素，每次进栈的是栈顶元素，出栈的也是栈顶元素，当数组写满之后自动扩容，元素个数小于1m时二倍扩容，大于等于1m时每次加1m。时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 进栈 | o(1) |
| 出栈 | o(1) |
队列先进先出，采用单链表保存数据，进栈是在表头添加元素，出栈就是表头出栈，即表头指向表头的下一个元素，相对数组实现的循环队列，链表队列不存在扩容的问题，但每个元素多了一个指针。时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 进栈 | o(1) |
| 出栈 | o(1) |
对golang的map简单封装，增加了一些方法。对于golang中map的实现原理请看我的这篇文章：，时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(1) |
| 修改 | o(1) |
| 查询 | o(1) |
| 删除 | o(1) |
就是map+读写锁，时间复杂度和map一样
双向链表 + map，双向链表按照顺序保存新增的元素，可以按照添加的顺序遍历数据，增删改查时间复杂度都和map一样
通过二叉搜索树保存数据，后面会详细介绍二叉搜索树，使用二叉搜索树就不存在扩容的问题，hashmap则存在扩容的问题，时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(logn) |
| 修改 | o(logn) |
| 查询 | o(logn) |
| 删除 | o(logn) |
lru的实现原理其实和linkmap几乎一样，只不过lru在修改或是查询的时候都会将被访问的元素移到链表的表头，表尾的数据是最先被淘汰的，时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(1) |
| 修改 | o(1) |
| 查询 | o(1) |
| 删除 | o(1) |
提供二叉搜索树的增删改查功能，删除相对复杂点，时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(logn) |
| 修改 | o(logn) |
| 查询 | o(logn) |
| 删除 | o(logn) |
堆是对golang本身container/heap的简单封装，大堆中某个节点的值总是不大于其父节点的值；堆总是一棵完全二叉树。，时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(logn) |
| 查询 | o(n) |
| 删除 | o(logn) |
堆是对golang本身container/heap的简单封装，小堆中某个节点的值总是不小于其父节点的值；堆总是一棵完全二叉树。，时间复杂度如下：
| 功能 | 时间复杂度 |
|---|---|
| 新增 | o(logn) |
| 查询 | o(n) |
| 删除 | o(logn) |
如对本文有疑问， 点击进行留言回复！！
我要评论
网友评论