golang本身對常用集合的封裝還是比較少的，主要有陣列（切片）、雙向鏈表、堆等，在作業中可能用到其他常用的集合，于是我自己對常用的集合進行了封裝，并對原理做了簡單介紹，代碼庫地址：https://github.com/chentaihan/container，代碼都是經過測驗的，歡迎下載使用，反饋的問題我會第一時間修復
ArraySort排序陣列
ArraySort使用陣列保存資料，新增的時候通過類似二分查找找到插入位置，插入位置后面的資料往后移動一位，插入新元素，查找就是二分查找，洗掉就是通過二分查找找到對應的元素，之后的元素都向前移動一位，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(n) |
| 洗掉 | O(n) |
| 查找 | O(logn) |
LinkList單鏈表
通過鏈表頭指標和鏈表尾兩個指標將所有元素鏈接在一起，可以快速的在表頭和表尾插入元素，洗掉和查找都是遍歷鏈表，查找對應的元素，洗掉還需要改變指標指向，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(1) |
| 洗掉 | O(n) |
| 查找 | O(n) |
Queue回圈佇列
佇列先進先出，回圈佇列采用陣列保存元素，以回圈的方式在陣列中添加元素，當陣列寫滿之后自動擴容，元素個數小于1M時二倍擴容，大于等于1M時每次加1M，洗掉元素的時候需要將對應的位置賦值為空指標，方便被洗掉的元素被回收，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 進佇列 | O(1) |
| 出佇列 | O(1) |
QueueLink鏈表佇列
佇列先進先出，實作和單鏈表類似，進堆疊是在表尾添加元素，出堆疊就是表頭出堆疊，即表頭指向表頭的下一個元素，相對陣列實作的回圈佇列，鏈表佇列不存在擴容的問題，但每個元素多了一個指標，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 進佇列 | O(1) |
| 出佇列 | O(1) |
PriorityQueue優先級佇列
優先級佇列采用小堆實作，小堆采用陣列保存資料，按照完全二叉樹的方式操作資料，每個節點的值都小于等于左右子節點的值，保證了每次出隊的都是最小值，即按照順序出隊，
時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 進佇列 | O(logn) |
| 出佇列 | O(logn) |
Stack堆疊
堆疊先進后出，采用陣列保存元素，每次進堆疊的是堆疊頂元素，出堆疊的也是堆疊頂元素，當陣列寫滿之后自動擴容，元素個數小于1M時二倍擴容，大于等于1M時每次加1M，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 進堆疊 | O(1) |
| 出堆疊 | O(1) |
StackLink鏈表堆疊
佇列先進先出，采用單鏈表保存資料，進堆疊是在表頭添加元素，出堆疊就是表頭出堆疊，即表頭指向表頭的下一個元素，相對陣列實作的回圈佇列，鏈表佇列不存在擴容的問題，但每個元素多了一個指標，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 進堆疊 | O(1) |
| 出堆疊 | O(1) |
Map
對golang的map簡單封裝，增加了一些方法，對于golang中map的實作原理請看我的這篇文章：https://www.cnblogs.com/hlxs/p/10408961.html，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(1) |
| 修改 | O(1) |
| 查詢 | O(1) |
| 洗掉 | O(1) |
MapSync同步map
就是map+讀寫鎖，時間復雜度和map一樣
LinkMap
雙向鏈表 + map，雙向鏈表按照順序保存新增的元素，可以按照添加的順序遍歷資料，增刪改查時間復雜度都和map一樣
TreeMap
通過二叉搜索樹保存資料，后面會詳細介紹二叉搜索樹，使用二叉搜索樹就不存在擴容的問題，hashmap則存在擴容的問題，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(logn) |
| 修改 | O(logn) |
| 查詢 | O(logn) |
| 洗掉 | O(logn) |
LRU
lru的實作原理其實和LinkMap幾乎一樣，只不過lru在修改或是查詢的時候都會將被訪問的元素移到鏈表的表頭，表尾的資料是最先被淘汰的，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(1) |
| 修改 | O(1) |
| 查詢 | O(1) |
| 洗掉 | O(1) |
BinaryTree二叉搜索樹
提供二叉搜索樹的增刪改查功能，洗掉相對復雜點，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(logn) |
| 修改 | O(logn) |
| 查詢 | O(logn) |
| 洗掉 | O(logn) |
heap大堆
堆是對golang本身container/heap的簡單封裝，大堆中某個節點的值總是不大于其父節點的值；堆總是一棵完全二叉樹，，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(logn) |
| 查詢 | O(n) |
| 洗掉 | O(logn) |
heap小堆
堆是對golang本身container/heap的簡單封裝，小堆中某個節點的值總是不小于其父節點的值；堆總是一棵完全二叉樹，，時間復雜度如下：
| 功能 | 時間復雜度 |
|---|---|
| 新增 | O(logn) |
| 查詢 | O(n) |
| 洗掉 | O(logn) |
專案地址：https://github.com/chentaihan/container 專案地址：https://github.com/chentaihan/container 專案地址：https://github.com/chentaihan/container
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/24413.html
標籤：Go
下一篇：MySQL的事務隔離級別是什么？