golang實現(xiàn)常用集合原理介紹

ArraySort排序數(shù)組

ArraySort使用數(shù)組保存數(shù)據(jù)，新增的時候通過類似二分查找找到插入位置，插入位置后面的數(shù)據(jù)往后移動一位，插入新元素，查找就是二分查找，刪除就是通過二分查找找到對應(yīng)的元素，之后的元素都向前移動一位。時間復(fù)雜度如下：

LinkList單鏈表

通過鏈表頭指針和鏈表尾兩個指針將所有元素鏈接在一起，可以快速的在表頭和表尾插入元素，刪除和查找都是遍歷鏈表，查找對應(yīng)的元素，刪除還需要改變指針指向。時間復(fù)雜度如下：

Queue循環(huán)隊列

隊列先進(jìn)先出，循環(huán)隊列采用數(shù)組保存元素，以循環(huán)的方式在數(shù)組中添加元素，當(dāng)數(shù)組寫滿之后自動擴(kuò)容，元素個數(shù)小于1M時二倍擴(kuò)容，大于等于1M時每次加1M，刪除元素的時候需要將對應(yīng)的位置賦值為空指針，方便被刪除的元素被回收。時間復(fù)雜度如下：

QueueLink鏈表隊列

隊列先進(jìn)先出，實現(xiàn)和單鏈表類似，進(jìn)棧是在表尾添加元素，出棧就是表頭出棧，即表頭指向表頭的下一個元素，相對數(shù)組實現(xiàn)的循環(huán)隊列，鏈表隊列不存在擴(kuò)容的問題，但每個元素多了一個指針。時間復(fù)雜度如下：

PriorityQueue優(yōu)先級隊列

優(yōu)先級隊列采用小堆實現(xiàn)，小堆采用數(shù)組保存數(shù)據(jù)，按照完全二叉樹的方式操作數(shù)據(jù)，每個節(jié)點的值都小于等于左右子節(jié)點的值，保證了每次出隊的都是最小值，即按照順序出隊。

時間復(fù)雜度如下：

Stack棧

棧先進(jìn)后出，采用數(shù)組保存元素，每次進(jìn)棧的是棧頂元素，出棧的也是棧頂元素，當(dāng)數(shù)組寫滿之后自動擴(kuò)容，元素個數(shù)小于1M時二倍擴(kuò)容，大于等于1M時每次加1M。時間復(fù)雜度如下：

StackLink鏈表棧

隊列先進(jìn)先出，采用單鏈表保存數(shù)據(jù)，進(jìn)棧是在表頭添加元素，出棧就是表頭出棧，即表頭指向表頭的下一個元素，相對數(shù)組實現(xiàn)的循環(huán)隊列，鏈表隊列不存在擴(kuò)容的問題，但每個元素多了一個指針。時間復(fù)雜度如下：

Map

對golang的map簡單封裝，增加了一些方法。對于golang中map的實現(xiàn)原理請看我的這篇文章：http://www.rzrgm.cn/hlxs/p/10408961.html，時間復(fù)雜度如下：

MapSync同步map

就是map+讀寫鎖，時間復(fù)雜度和map一樣

LinkMap

雙向鏈表 + map，雙向鏈表按照順序保存新增的元素，可以按照添加的順序遍歷數(shù)據(jù)，增刪改查時間復(fù)雜度都和map一樣

TreeMap

通過二叉搜索樹保存數(shù)據(jù)，后面會詳細(xì)介紹二叉搜索樹，使用二叉搜索樹就不存在擴(kuò)容的問題，hashmap則存在擴(kuò)容的問題，時間復(fù)雜度如下：

LRU

lru的實現(xiàn)原理其實和LinkMap幾乎一樣，只不過lru在修改或是查詢的時候都會將被訪問的元素移到鏈表的表頭，表尾的數(shù)據(jù)是最先被淘汰的，時間復(fù)雜度如下：

BinaryTree二叉搜索樹

提供二叉搜索樹的增刪改查功能，刪除相對復(fù)雜點，時間復(fù)雜度如下：

heap大堆

堆是對golang本身container/heap的簡單封裝，大堆中某個節(jié)點的值總是不大于其父節(jié)點的值；堆總是一棵完全二叉樹。，時間復(fù)雜度如下：

heap小堆

堆是對golang本身container/heap的簡單封裝，小堆中某個節(jié)點的值總是不小于其父節(jié)點的值；堆總是一棵完全二叉樹。，時間復(fù)雜度如下：