柚子快報(bào)邀請碼778899分享：Go基本數(shù)據(jù)結(jié)構(gòu)

http://yzkb.51969.com/

1.jdk豐富的數(shù)據(jù)結(jié)構(gòu)

Jdk提供了許多基本數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，這些數(shù)據(jù)結(jié)構(gòu)是Java Collections Framework的一部分，位于java.util包中。以下是一些常見的數(shù)據(jù)結(jié)構(gòu)：

ArrayList：一個(gè)可調(diào)整大小的數(shù)組實(shí)現(xiàn)，支持快速隨機(jī)訪問。 LinkedList：一個(gè)雙向鏈表實(shí)現(xiàn)，支持快速插入和刪除。 HashSet：基于哈希表的Set實(shí)現(xiàn)，不保證集合的迭代順序。 LinkedHashSet：類似于HashSet，但維護(hù)著一個(gè)運(yùn)行于所有元素的雙重鏈表。 TreeSet：基于紅黑樹的NavigableSet實(shí)現(xiàn)，元素處于排序狀態(tài)。 HashMap：基于哈希表的Map實(shí)現(xiàn)，不保證映射的順序。 LinkedHashMap：類似于HashMap，維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈表。 TreeMap：基于紅黑樹的NavigableMap實(shí)現(xiàn)，鍵處于排序狀態(tài)。 PriorityQueue：基于優(yōu)先級堆的無界隊(duì)列，元素處于自然排序狀態(tài)。 ArrayDeque：一個(gè)雙端隊(duì)列實(shí)現(xiàn)，支持從兩端插入和移除。 ConcurrentHashMap：一個(gè)線程安全的HashMap實(shí)現(xiàn)。 CopyOnWriteArrayList：一個(gè)線程安全的變長數(shù)組實(shí)現(xiàn)。 CopyOnWriteArraySet：一個(gè)線程安全的Set實(shí)現(xiàn)。

JDK提供了如此多的數(shù)據(jù)結(jié)果，程序員只需了解每種數(shù)據(jù)結(jié)果的特點(diǎn)，即可應(yīng)付大部分日常開發(fā)。說實(shí)在的，對于數(shù)據(jù)結(jié)構(gòu)，即使經(jīng)驗(yàn)豐富的開發(fā)（包括筆者自己），很多人都是只知其然而不知其所以然。

在這里分享一個(gè)面試經(jīng)歷，筆者曾經(jīng)一個(gè)同事，中山大學(xué)碩士生，技術(shù)杠杠的。然而在一場面試卻掛了，?面試官問了一個(gè)問題，講講紅黑樹的數(shù)據(jù)結(jié)構(gòu)。

說這個(gè)故事不是說數(shù)據(jù)結(jié)構(gòu)不重要，只是側(cè)面說明了jdk內(nèi)嵌的數(shù)據(jù)結(jié)果多么豐富，可以解決實(shí)際開發(fā)90%以上的問題。

2.Go基本數(shù)據(jù)結(jié)構(gòu)

Go以簡潔著稱，只提供3種數(shù)據(jù)結(jié)構(gòu)（后續(xù)可能會拓展，畢竟效率是第一生產(chǎn)力?。?/p>

2.1.數(shù)組

數(shù)組是一個(gè)固定長度的數(shù)據(jù)類型，用于存儲一段具有相同類型元素的數(shù)據(jù)塊。其占有的內(nèi)存是連續(xù)的，可以快速迭代數(shù)組里的每個(gè)元素。

2.1.1.申明數(shù)組

當(dāng)數(shù)組初始化時(shí)，每個(gè)元素被初始化為對應(yīng)的零值

// 申明包含5個(gè)元素的整形數(shù)組

var array [5]int

// 初始化為零值 [0 0 0 0 0]

fmt.Print(array)

使用字面量聲明數(shù)組

import "fmt"

func main() {

// 申明一個(gè)包含5個(gè)元素的數(shù)組，并進(jìn)行初始化

array1 := [5]int{1,2,3,4,5}

// 使用...自動(dòng)計(jì)算數(shù)組長度

array2 := [...]int{1,2,3,4,5,6}

fmt.Println(array1)

fmt.Println(array2)

}

2.1.2.基本操作

func main() {

// 申明一個(gè)包含5個(gè)元素的數(shù)組，并進(jìn)行初始化

array := [5]int{1,2,3,4,5}

// 修改索引為2的元素

array[2] = 30

// 遍歷數(shù)組

for i := 0; i < len(array); i++ {

fmt.Println(array[i])

}

// 使用range遍歷

for i,value := range array {

fmt.Println(i, value)

}

// 數(shù)組復(fù)制，只有類型及長度都一樣才可進(jìn)行！

var array2 [5]int = array

fmt.Println(array2)

}

2.1.3.在函數(shù)間傳遞數(shù)組

在函數(shù)之間傳遞變量時(shí)，總是以值的方式。如果數(shù)組很大，無疑開銷很大。因?yàn)闊o論數(shù)組有多長，都會完整復(fù)制一份新的。（這一點(diǎn)與C語言不同，C傳遞數(shù)組給函數(shù)時(shí)，傳遞的是首元素的地址，相當(dāng)于傳遞了指針）

import "fmt"

func main() {

// 100萬個(gè)元素，需要8M

var array [1e6]int64

// 將數(shù)組復(fù)制傳遞給函數(shù)

test(array)

// 函數(shù)內(nèi)部的操作不會影響到原數(shù)組

fmt.Println(array[1])

}

func test(a [1e6]int64) {

a[1]=100

fmt.Println(len(a))

// 函數(shù)內(nèi)部修改了元素值，操作的是復(fù)制品

fmt.Println(a[1])

}

2.1.4.傳遞引用

為了避免耗時(shí)耗內(nèi)存的復(fù)制操作，可以只傳入指向數(shù)組的指針

func main() {

// 100萬個(gè)元素，需要8M

var array [1e6]int64

test(&array)

// 函數(shù)內(nèi)部的修改，會影響原數(shù)組的內(nèi)容

fmt.Println(array[1])

}

func test(a *[1e6]int64) {

// 修改索引為1的元素的值

a[1]=100

fmt.Println(len(a))

// 內(nèi)部通過指針修改元素值

fmt.Println(a[1])

}

2.2.切片

切片，實(shí)質(zhì)上為動(dòng)態(tài)數(shù)組，相當(dāng)于java的ArrayList。這種結(jié)構(gòu)可以通過append函數(shù)按需自動(dòng)增長，也可以對切片再次切片來縮小一個(gè)切片的大小。

2.2.1.內(nèi)部實(shí)現(xiàn)

切片是一個(gè)很小的對象，對底層數(shù)組進(jìn)行了抽象，并提供相關(guān)的操作方法。切片內(nèi)部有3個(gè)字段，分別是指向數(shù)組的指針，元素個(gè)數(shù)（長度）和切片允許增長的元素個(gè)數(shù)（容量）。如下圖所示：

2.2.2.創(chuàng)建與初始化

使用make函數(shù)創(chuàng)建切片

func main() {

// 只指定長度，那么切片的容量等于長度

slice := make([]int, 5)

// 同時(shí)指定長度，容量

slice2 := make([]int, 5, 10)

}

?通過切面字面量申明切片（與通過字面量申明數(shù)組非常相似，只是中括號內(nèi)部少了...）

color := []string{"red", "green", "blue"}

2.2.3.nil與空切片

nil切片

有時(shí)(例如函數(shù)要求返回一個(gè)切片但發(fā)生異常)，程序可能需要申明一個(gè)值為nil的切片。只需在申明時(shí)不做任何初始化。如下所示：

// 創(chuàng)建nil切片

var slice []int

空切片

空切片表示，在底層數(shù)組包含0個(gè)元素，也沒有分配任何存儲空間。使用空切片來表示空集合，例如，數(shù)組庫查詢返回0個(gè)查詢結(jié)果。

// 使用make創(chuàng)建空切片

slice := make([]int,0)

// 使用字面量創(chuàng)建空切片

slice2 := []int{}

2.2.4.基本操作

package main

import (

"fmt"

"sort"

)

func main() {

// 聲明一個(gè)整型切片

var slice []int

// 使用內(nèi)置的make函數(shù)初始化切片

slice = make([]int, 5) // 分配一個(gè)長度為5的切片，容量也為5

// 使用數(shù)組初始化切片

array := [5]int{1, 2, 3, 4, 5}

slice = array[:5] // 創(chuàng)建一個(gè)切片，包含整個(gè)數(shù)組

// 訪問和修改元素

slice[0] = 10 // 修改索引為0的元素為10

fmt.Println("Modified slice:", slice)

// 追加元素

slice = append(slice, 6)

fmt.Println("Slice after append:", slice)

// 獲取切片長度和容量

length := len(slice)

capacity := cap(slice)

fmt.Println("Length:", length)

fmt.Println("Capacity:", capacity)

// 切片的切片

subSlice := slice[1:4]

fmt.Println("Sub-slice:", subSlice)

// 遍歷切片

fmt.Println("Iterating over slice:")

for index, value := range slice {

fmt.Println(index, value)

}

// 使用for循環(huán)遍歷切片

fmt.Println("Iterating with for loop:")

for index := 0; index < len(slice); index++ {

fmt.Println(index, slice[index])

}

// 清空切片

slice = slice[:0]

fmt.Println("Slice after clearing:", slice)

// 擴(kuò)展切片

slice = slice[:cap(slice)] // 擴(kuò)展切片到其容量

fmt.Println("Slice after expansion:", slice)

// 截?cái)嗲衅?/p>

slice = slice[:4] // 將切片截?cái)嗟?

fmt.Println("Slice after truncation:", slice)

// 復(fù)制切片

copySlice := append([]int(nil), slice...)

fmt.Println("Copy of slice:", copySlice)

// 排序切片

sort.Ints(slice)

fmt.Println("Sorted slice:", slice)

// 刪除元素

slice = append(slice[:1], slice[2:]...)

fmt.Println("Slice after deletion:", slice)

// 反轉(zhuǎn)切片

for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {

slice[i], slice[j] = slice[j], slice[i]

}

fmt.Println("Reversed slice:", slice)

}

2.2.5.切片的切片

這里重點(diǎn)講下對切片進(jìn)行切片。切片之所以被稱為切片，是因?yàn)閯?chuàng)建一個(gè)新的切片就是把底層數(shù)組切出一部分。如下代碼：

// 創(chuàng)建一個(gè)長度與容量都是5的切片

myNum := []int{10,20,30,40,50}

// 創(chuàng)建一個(gè)新切片，長度為2，容量為4

newNum := myNum[1:3]

// 向第二個(gè)切片新增元素

newNum = append(newNum, 60)

fmt.Println(myNum) //輸出： [10 20 30 60 50]

fmt.Println(newNum) //輸出： [20 30 60]

執(zhí)行完代碼之后，我們有兩個(gè)切片，它們共享同一個(gè)底層數(shù)組，但不同的切片看到同一個(gè)數(shù)組的不同部分，如下

第一個(gè)切片myNum能夠看到底層數(shù)組全部5個(gè)元素，而newNum一開始只能看到索引為1和索引為2的元素，在執(zhí)行append之后，可以看到新增的元素60，同時(shí)新增的元素也影響了myNum切片。從程序輸出可以看出，myNum索引為3的元素從40變成60了。

2.2.6.限制再切片的容量

在創(chuàng)建切片的切片時(shí)，還可以指定第三個(gè)參數(shù)，用來控制新切片的容量。該參數(shù)可以更好控制追加操作，為底層數(shù)組提供了一定的保護(hù)。(為了顯示行數(shù)，下面的例子使用截圖而非文本)

對于第三個(gè)參數(shù)的解釋

第9行代碼執(zhí)行 newNum ? := myNum[2:3:4]，這里的4代表的是原切片myNum的索引為4的位置，典型地，對于slice[i:j:k]，示例 [2:3:4]

長度公式為：j - i = 3-2 = 1

容量公式為：k - i = 4-2 = 2

執(zhí)行第12行，向newNum追加一個(gè)元素600，因?yàn)閚ewNum容量為2，沒有超出（此時(shí)newNum長度為2，容量為2），所以共享底層數(shù)組的myNumq切片也多了一個(gè)元素600（見第13行輸出）

然而，執(zhí)行第13行，向newNum繼續(xù)追加一個(gè)元素700，因?yàn)槌鰊ewNum的容量，程序會創(chuàng)建一個(gè)新的底層數(shù)組，這個(gè)數(shù)組會將原來newNum的元素全部復(fù)制過來，新切片的容量為原切片進(jìn)行翻倍。

從上面的例子可以看出，如果在創(chuàng)建切片時(shí)設(shè)置切片的容量和長度一樣，就可以強(qiáng)制讓新切片的第一個(gè)append操作創(chuàng)建新的底層數(shù)組，從而使新切片與原切片徹底分類，這樣，新切片就可以安全進(jìn)行后續(xù)操作了。

2.2.7.在函數(shù)間傳遞切片

在函數(shù)間傳遞切片是以值的方式，由于切片本身屬于引用類型，將切片傳遞給函數(shù)時(shí)，在64位架構(gòu)的機(jī)器上，一個(gè)切片需要8字節(jié)的指針，8字節(jié)的長度以及8字節(jié)的容量，總共需要24字節(jié)。底層的數(shù)組不會被復(fù)制，所以在函數(shù)間傳遞切片非?？焖?。

2.3.映射

映射（map）是一種基于哈希表實(shí)現(xiàn)的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，它允許存儲鍵值對，并提供了快速的查找、插入和刪除操作（相當(dāng)于java的HashMap）。以下是 map 的一些核心特性和基本操作：

無序：map 是無序的，不能通過索引訪問，也沒有固定的長度。動(dòng)態(tài)：map 的大小是動(dòng)態(tài)的，可以隨時(shí)添加或刪除鍵值對。唯一鍵：map 的鍵是唯一的，不允許重復(fù)。非并發(fā)安全：標(biāo)準(zhǔn)的 map 不是并發(fā)安全的，如果需要在多個(gè) goroutine 中共享 map，應(yīng)該使用?sync.Map?或者在操作 map 時(shí)使用互斥鎖。

2.3.1.創(chuàng)建和初始化

使用make和字面量創(chuàng)建映射

// 創(chuàng)建一個(gè)映射，key為string，value為int

dict := make(map[string]int)

// 創(chuàng)建一個(gè)映射，key，value均為string

// 使用兩個(gè)鍵值對初始化

dict2 := map[string]string{"name":"gforgame", "url":"https://github.com/kingston-csj/gforgame"}

關(guān)于鍵的類型

映射的鍵可以是任何值，只要這個(gè)值可以使用==運(yùn)算符做比較。這個(gè)值的類型可以是內(nèi)置的類型，也可以是結(jié)構(gòu)類型。但切片、函數(shù)這些類型由于具有引用語義，因此不能作為映射的鍵。

2.3.2.基本操作

package main

import (

"fmt"

)

func main() {

// 初始化 map

myMap := make(map[string]int)

// 賦值

myMap["apple"] = 1

myMap["banana"] = 2

myMap["cherry"] = 3

// 讀取

value, ok := myMap["apple"]

if ok {

fmt.Println("apple:", value)

} else {

fmt.Println("apple not found")

}

// 刪除

delete(myMap, "banana")

if _, ok := myMap["banana"]; !ok {

fmt.Println("banana has been deleted")

}

// 遍歷

fmt.Println("Iterating over map:")

for key, value := range myMap {

fmt.Println(key, value)

}

// 獲取大小

size := len(myMap)

fmt.Println("Size of map:", size)

// 檢查鍵是否存在

if _, exists := myMap["cherry"]; exists {

fmt.Println("cherry exists in the map")

} else {

fmt.Println("cherry does not exist in the map")

}

// 預(yù)分配空間

myMapPreallocated := make(map[string]int, 5)

myMapPreallocated["orange"] = 5

fmt.Println("Preallocated map size:", len(myMapPreallocated))

// 清空 map

for key := range myMapPreallocated {

delete(myMapPreallocated, key)

}

fmt.Println("Map after clearing:", myMapPreallocated)

}

2.3.3.在函數(shù)間傳遞映射

映射是引用類型，因此在函數(shù)間傳遞映射時(shí)，傳遞的是映射的引用。這意味著，如果在函數(shù)內(nèi)部修改了映射的內(nèi)容，這些修改將會影響到原始的映射。

下面是一個(gè)示例，展示了如何在函數(shù)間傳遞映射，并在函數(shù)內(nèi)部修改映射

package main

import "fmt"

// AddItem 向映射中添加一個(gè)元素

func AddItem(itemMap map[string]int, key string, value int) {

itemMap[key] = value // 添加或更新鍵值對

}

// RemoveItem 從映射中刪除一個(gè)元素

func RemoveItem(itemMap map[string]int, key string) {

delete(itemMap, key) // 刪除鍵值對

}

func main() {

myMap := make(map[string]int)

// 向映射中添加元素

AddItem(myMap, "apple", 1)

AddItem(myMap, "banana", 2)

// 打印映射

fmt.Println("After adding items:")

fmt.Println(myMap) // 輸出： map[apple:1 banana:2]

// 從映射中刪除一個(gè)元素

RemoveItem(myMap, "banana")

// 打印映射

fmt.Println("After removing an item:")

fmt.Println(myMap) // 輸出： map[apple:1]

}

3.第三方數(shù)據(jù)結(jié)構(gòu)

由于官方提供的數(shù)據(jù)結(jié)構(gòu)確實(shí)非常少，因此社區(qū)相關(guān)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)非常多，下面列舉幾個(gè)比較有名的。

go-datastructures??這是一個(gè)集合，包含了許多有用的、性能優(yōu)異的、線程安全的 Go 數(shù)據(jù)結(jié)構(gòu)。例如，增強(qiáng)樹、位數(shù)組、隊(duì)列、斐波那契堆、區(qū)間樹、集合等。gods??Go 數(shù)據(jù)結(jié)構(gòu)庫，包含鏈表、棧、哈希表、樹等。

柚子快報(bào)邀請碼778899分享：Go基本數(shù)據(jù)結(jié)構(gòu)

http://yzkb.51969.com/

文章來源