golang实现常用集合原理介绍

chentaihan · · 875 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

golang本身对常用集合的封装还是比较少的,主要有数组(切片)、双向链表、堆等。在工作中可能用到其他常用的集合,于是我自己对常用的集合进行了封装,并对原理做了简单介绍,代码库地址:https://github.com/chentaihan/container,代码都是经过测试的,欢迎下载使用,反馈的问题我会第一时间修复 #golang实现常用集合原理介绍 ## [ArraySort排序数组](https://github.com/chentaihan/container/blob/master/array/arraySort.go) ArraySort使用数组保存数据,新增的时候通过类似二分查找找到插入位置,插入位置后面的数据往后移动一位,插入新元素,查找就是二分查找,删除就是通过二分查找找到对应的元素,之后的元素都向前移动一位。时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(n\) | | 删除 | **O**\(n\) | | 查找 | **O**\(logn\) | ## [LinkList单链表](https://github.com/chentaihan/container/blob/master/link/linkList.go) 通过链表头指针和链表尾两个指针将所有元素链接在一起,可以快速的在表头和表尾插入元素,删除和查找都是遍历链表,查找对应的元素,删除还需要改变指针指向。时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(1\) | | 删除 | **O**\(n\) | | 查找 | **O**\(n\) | ## [Queue循环队列](https://github.com/chentaihan/container/blob/master/queue/queue.go) 队列先进先出,循环队列采用数组保存元素,以循环的方式在数组中添加元素,当数组写满之后自动扩容,元素个数小于1M时二倍扩容,大于等于1M时每次加1M,删除元素的时候需要将对应的位置赋值为空指针,方便被删除的元素被回收。时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 进队列 | **O**\(1\) | | 出队列 | **O**\(1\) | ## [QueueLink链表队列](https://github.com/chentaihan/container/blob/master/queue/queueLink.go) 队列先进先出,实现和单链表类似,进栈是在表尾添加元素,出栈就是表头出栈,即表头指向表头的下一个元素,相对数组实现的循环队列,链表队列不存在扩容的问题,但每个元素多了一个指针。时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 进队列 | **O**\(1\) | | 出队列 | **O**\(1\) | ## [PriorityQueue优先级队列](https://github.com/chentaihan/container/blob/master/queue/priorityQueue.go) 优先级队列采用小堆实现,小堆采用数组保存数据,按照完全二叉树的方式操作数据,每个节点的值都小于等于左右子节点的值,保证了每次出队的都是最小值,即按照顺序出队。 时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 进队列 | **O**\(logn\) | | 出队列 | **O**\(logn\) | ## [Stack栈](https://github.com/chentaihan/container/blob/master/stack/stack.go) 栈先进后出,采用数组保存元素,每次进栈的是栈顶元素,出栈的也是栈顶元素,当数组写满之后自动扩容,元素个数小于1M时二倍扩容,大于等于1M时每次加1M。时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 进栈 | **O**\(1\) | | 出栈 | **O**\(1\) | ## [StackLink链表栈](https://github.com/chentaihan/container/blob/master/stack/stackLink.go) 队列先进先出,采用单链表保存数据,进栈是在表头添加元素,出栈就是表头出栈,即表头指向表头的下一个元素,相对数组实现的循环队列,链表队列不存在扩容的问题,但每个元素多了一个指针。时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 进栈 | **O**\(1\) | | 出栈 | **O**\(1\) | ## [Map](https://github.com/chentaihan/container/blob/master/hashmap/map.go) 对golang的map简单封装,增加了一些方法。对于golang中map的实现原理请看我的这篇文章:[https://www.cnblogs.com/hlxs/p/10408961.html](https://www.cnblogs.com/hlxs/p/10408961.html),时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(1\) | | 修改 | **O**\(1\) | | 查询 | O\(1\) | | 删除 | O\(1\) | ## [MapSync同步map](https://github.com/chentaihan/container/blob/master/hashmap/mapSync.go) 就是map+读写锁,时间复杂度和map一样 ## [LinkMap](https://github.com/chentaihan/container/blob/master/hashmap/linkMap.go) 双向链表 + map,双向链表按照顺序保存新增的元素,可以按照添加的顺序遍历数据,增删改查时间复杂度都和map一样 ## [TreeMap](https://github.com/chentaihan/container/blob/master/hashmap/treeMap.go) 通过二叉搜索树保存数据,后面会详细介绍二叉搜索树,使用二叉搜索树就不存在扩容的问题,hashmap则存在扩容的问题,时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(logn\) | | 修改 | **O**\(logn\) | | 查询 | O\(logn\) | | 删除 | O\(logn\) | ## [LRU](https://github.com/chentaihan/container/blob/master/cache/lru.go) lru的实现原理其实和LinkMap几乎一样,只不过lru在修改或是查询的时候都会将被访问的元素移到链表的表头,表尾的数据是最先被淘汰的,时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(1\) | | 修改 | **O**\(1\) | | 查询 | O\(1\) | | 删除 | O\(1\) | ## [BinaryTree二叉搜索树](https://github.com/chentaihan/container/blob/master/tree/binaryTree.go) 提供二叉搜索树的增删改查功能,删除相对复杂点,时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(logn\) | | 修改 | **O**\(logn\) | | 查询 | O\(logn\) | | 删除 | O\(logn\) | ## [heap大堆](https://github.com/chentaihan/container/blob/master/heap/bigHeap.go) 堆是对golang本身container/heap的简单封装,大堆中某个节点的值总是不大于其父节点的值;堆总是一棵完全二叉树。,时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(logn\) | | 查询 | O\(n\) | | 删除 | O\(logn\) | ## [heap小堆](https://github.com/chentaihan/container/blob/master/heap/smallHeap.go) 堆是对golang本身container/heap的简单封装,小堆中某个节点的值总是不小于其父节点的值;堆总是一棵完全二叉树。,时间复杂度如下: | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(logn\) | | 查询 | O\(n\) | | 删除 | O\(logn\) | 项目地址:https://github.com/chentaihan/container 项目地址:https://github.com/chentaihan/container 项目地址:https://github.com/chentaihan/container

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

875 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传