编程中的数据结构是在计算机中组织和存储数据以便有效访问和使用数据的特定方式。
在木工或金属加工中，夹具固定一件工件并引导在其上操作的工具。它有助于产生一致的结果。最简单的夹具可能是直尺。例如，直金属棒可以帮助您沿着直线切割木材。另一个简单的夹具是斜切盒，它可以帮助我们以固定角度切割木材。
数据结构可以被认为是程序员的夹具。就像夹具引导工具进行精确切割或形状一样，编程中的数据结构提供了组织和访问数据的框架。正如夹具指导工具一样，数据结构指导如何存储、访问和操作数据。数据结构帮助我们确保以可预测且高效的方式执行数据操作。
传统的计算机科学课程经常介绍各种数据结构：链表、红黑树等等。然而，在实践中，绝大多数编程问题只需使用数组、标准复合类型 ( struct ) 和偶尔的哈希表即可解决。与木工夹具的类比仍然成立：最流行的木工夹具非常简单，我们甚至经常忘记它们是一个实际的工具。
数组
一些数据结构由于其简单性和效率而特别有用。最简单的数据结构是数组。数组是固定大小的元素集合。例如，在 Go 中，您可以声明一个包含 5 个整数的数组，如下所示：
var myArray [ 5 ] int
通常，数组以连续的方式存储在内存中。因此，如果您需要尽快遍历所有元素，数组是理想的选择：您可以以可预测的方式访问内存，而开销很小。访问数组中的任何给定元素通常只需要获取索引并将其转换为内存地址。它可能只需要一些廉价的操作。
一般来说，数组生成快速代码的部分原因是编译器发现很容易优化函数。例如，在 Go 中，数组访问通常受到绑定检查器的约束：如果数组大小为 5，Go 将阻止访问索引 10 处的数组。但是，编译器通常可以优化此类检查。例如，考虑以下函数，我们对数组中的五个元素求和。它应该编译为高效的代码，几乎没有任何开销（例如，边界检查）。
func Sum(x [5]int) int { sum := 0 for i := 0; i < 5; i++ { sum += x[i] } return sum }
数组可以包含不同的值（包括数组！）。甚至可以将布尔值（真/假）存储在数组中，尽管在这种情况下，每个元素至少需要一个字节。在这种情况下，您可以用位集替换数组。您可以按如下方式在数组上实现位集（以 128 位为例）。
// BitSet represents a fixed-size bitset type BitSet struct { bytes [16]byte } // Set sets the bit at 'index' to 1 func (bs *BitSet) Set(index int) { bs.bytes[index/8] |= 1 << uint(7-(index%8)) } // Clear sets the bit at 'index' to 0 func (bs *BitSet) Clear(index int) { bs.bytes[index/8] &^= 1 << uint(7-(index%8)) } // Get returns the value of the bit at 'index' func (bs *BitSet) Get(index int) bool { return bs.bytes[index/8]&(1<<uint(7-(index%8))) != 0 }
数组的自然扩展是多维数组。尽管Go语言原生支持多维数组，但我们仍然可以使用标准数组从头开始实现它们。通常，我们使用行优先实现。例如，我们可以使用 9 元素数组实现一个简单的 3×3 矩阵。数组的前三个元素代表第一行，接下来的三个元素代表第二行，依此类推。
// Matrix represents a 3x3 matrix type Matrix struct { data [9]float64 } // Set sets the value func (m *Matrix) Set(i, j int, val float64) { if i < 0 || i > 2 || j < 0 || j > 2 { panic("Index out of bounds for a 3x3 matrix") } m.data[i*3+j] = val } // Get returns the value func (m *Matrix) Get(i, j int) float64 { if i < 0 || i > 2 || j < 0 || j > 2 { panic("Index out of bounds for a 3x3 matrix") } return m.data[i*3+j] } // String provides a string representation of the Matrix func (m *Matrix) String() string { var str string for i := 0; i < 3; i++ { for j := 0; j < 3; j++ { str += fmt.Sprintf("%6.2f ", m.Get(i, j)) } str += "\n" } return str }
与许多编程语言一样，Go 允许您创建高效的复合数据结构（ struct ）。特别是，您可以将数组放入这些数据结构中。例如，假设我们想要表示空间中的点，我们可以这样做：
type Point struct { x float64 y float64 }
我们可以将这些点放入一个由十个元素组成的数组中：
var list [10]Point
这种模式通常称为结构数组。我们还可以使用数组结构来表示相同的数据：
type Points struct { x [10]float64 y [10]float64 }
虽然结构数组和数组结构都可以包含相同的信息，但它们具有不同的性能特征。例如，如果您需要对 x 值求和，则数组结构可能会生成更快的代码。
动态数组和切片
稍微复杂一点的数据结构是动态数组。动态数组是可以增大或缩小大小的数组。在 Go 中，它们被实现为切片。它们是 Go 中最基本的数据结构之一。
var mySlice [] int mySlice = append ( mySlice , 1 , 2 , 3 )
您可以通过整数索引访问数组。例如，您可以访问一个大小为 3 且索引为 0、1、2 的数组。每个索引都可以让您访问一个值。因此，数组构成了一个键值数据结构，其中键是索引。
由于切片的大小是动态的，Go提供了一个函数来查询它： len (length)。例如， len(mySlice)可能是 3。
在 Go 中，您可以让多个切片共享同一个底层数组。我们使用运算符[begin:end]从现有切片创建新切片。重要的是，此操作不会复制底层数据。
在以下示例中，第二个切片的长度为 1，并包含第一个切片的第二个元素。
var mySlice []int mySlice = append(mySlice, 1, 2, 3) secondSlice := mySlice[1:2]
Go 提供了一些速记符号。您可以不写mySlice[2:len(mySlice)] ，而是写mySlice[2:] ，而不是写mySlice[0:1] ，您可以写mySlice[:1] 。要创建切片的副本，您可以简单地编写mySlice[:] 。
切片与数组具有许多相同的特征。例如，我们可以编写将切片作为参数的函数，并编译成类似的高效代码，例如我们对切片的前 5 个元素求和的示例：
func Sum(x []int) int { sum := 0 if len(x) < 5 { return -1 } for i := 0; i < 5; i++ { sum += x[i] } return sum }
事实上，动态数组（即切片）通常被实现为数组的薄包装器。切片指向数组内的一个区域。当我们缩小或扩展切片指向的区域时，底层数组可能保持不变。
通常，底层数组的存储容量大于切片的长度。您可以使用cap （容量）函数查询底层数组的大小。拥有超出所需的容量似乎很浪费。但是，考虑这样的情况：我们定期向给定切片添加元素，并且底层数组的大小设置为与切片的长度完全匹配。在这种情况下，每次添加（追加）到切片可能需要分配一个新数组并复制元素。仅计算元素的副本，我们发现需要1 + 2 + 3 + 4 + … + n − 1 = ( n −1) n /2 个副本才能用n 个值填充切片。相反，我们通常使用指数步长来增加底层数组的大小。例如，每当容量不足时，我们可以将内存分配到2的下一个幂：如果需要7个元素，则分配16个元素的容量；如果需要600个元素，则分配1024个元素，依此类推。我们可以验证，通过这样的策略，如果我们需要重复向切片添加一个元素，我们永远不需要超过2 n 个副本来创建具有n 个值的切片： 2 n远小于( n −1) n /2当n很大时。默认情况下，Go 在缩小切片时不会恢复多余的容量（例如， s = s[:newlength] ）。但是，您可以使用扩展语法s[low:high:max]告诉 Go 将底层数组的大小减小到max-low 。例如， s = s[::len(s)]将创建切片的副本，同时将底层容量调整为len(s) 。
以下程序将向切片添加元素，并在每次增量时打印切片的容量（底层数组的大小）和长度。在程序的最后，我们表明我们可以在调整或不调整容量的情况下缩小切片。
package main import "fmt" func main() { var mySlice []int for i := 0; i < 100; i++ { mySlice = append(mySlice, 1) fmt.Println(cap(mySlice), " : ", len(mySlice)) } mySlice = mySlice[:10] fmt.Println(cap(mySlice), " : ", len(mySlice)) mySlice = mySlice[:10:10] fmt.Println(cap(mySlice), " : ", len(mySlice)) }
以下是可能的输出：
1 : 1 2 : 2 4 : 3 4 : 4 8 : 5 8 : 6 8 : 7 8 : 8 16 : 9 ... 128 : 99 128 : 100 128 : 10 10 : 10 9 : 2
有时，将数据按排序顺序存储在数组中会很方便。然后，即使数组很大，我们也可以将数组用作有效的集合数据结构。当搜索一个值时，我们可以使用二分搜索。该算法相对简单：给定我们要查找的值，我们首先将其与中间的值（即中值）进行比较。如果我们要搜索的值大于中值，则在数组的后半部分搜索，否则在数组的前半部分搜索。我们递归地重复除法，直到找到我们正在寻找的值，或者我们确定找不到该值。我们需要大约log 2 ( N )次迭代来完成对大小为N的数组的搜索，并且对数函数增长非常缓慢（例如， log 2 ( 10 6 ) ≈ 20 ）。
// Search searches for a number in a sorted array // If the number is found, it returns the index of the number and true // If the number is not found, it returns -1 and false func Search(n int, array []int) (int, bool) { low, high := 0, len(array)-1 for low <= high { mid := (low + high) / 2 if array[mid] == n { return mid, true } else if array[mid] < n { low = mid + 1 } else { high = mid - 1 } } return -1, false }
有时我们只希望能够访问最小值或最大值。例如，假设您有一个需要处理的请求流，并且您总是希望选择下一个等待时间最长的请求。您可以重复扫描数组，或重复排序。但是，如果您不断地从数组中添加和删除数据，则可能会变得昂贵。相反，我们可以根据二叉堆对数组中的值进行排序。堆的根存储在索引 0 处，它是最小值或最大值，具体取决于您需要的堆类型。所以我们要么有最大堆，要么有最小堆。在数组中，值被组织为树。对于索引i处的任何节点，其左子节点位于2 * i + 1处，右子节点位于2 * i + 2处。在数组的末尾，某些节点可能只有左子节点，而其他节点可能没有子节点。如果我们有一个最大堆，则每个节点必须不小于其子节点。如果我们有一个最小堆，则每个节点不得大于其子节点。插入和删除等操作是通过操作数组中的元素来执行的，同时维护堆属性。要插入新值，请将新元素放置在数组的末尾。如果数组不为空，它就会成为现有节点的子节点：如果将其放在索引i处，则可以将父节点的索引计算为整数( i −1)/2 。然后将其与其父节点进行排列以保留堆属性（例如，如果我们有一个最大堆，则每个节点必须不小于其子节点）。然后，您可能需要再次检查父级，依此类推，直到到达堆的顶部。以下函数使用 max-heap 属性根据此算法修改切片。
func Insert(heap *[]int, value int) { // Append the new value to the end of the heap *heap = append(*heap, value) heapSize := len(*heap) // Start with the last element's index i := heapSize - 1 // Heapify-up (sift up) to maintain the max-heap property for i > 0 { parent := (i - 1) / 2 // If the value inserted is greater than its parent, swap them if (*heap)[i] > (*heap)[parent] { // Swap the elements (*heap)[i], (*heap)[parent] = (*heap)[parent], (*heap)[i] // Move up to the parent's index i = parent } else { // If we didn't swap, we've reached the correct position break } } }
删除顶部元素时，将其替换为最后一个元素，然后通过将其与较大（或更小）的子元素交换（如果它违反了堆属性）来向下传播该元素。对于最大堆，我们可以按如下方式实现：
// RemoveTop removes the top element of the max-heap func RemoveTop(heap *[]int) int { if len(*heap) == 0 { return 0 // or an appropriate zero value/error handling } // Store the root value to return later top := (*heap)[0] // Replace the root with the last element heapSize := len(*heap) (*heap)[0] = (*heap)[heapSize-1] *heap = (*heap)[:heapSize-1] // Start heapifying down from the root i := 0 for { // Calculate indices of children leftChild := 2*i + 1 rightChild := 2*i + 2 largest := i // Check left child if leftChild < len(*heap) && (*heap)[leftChild] > (*heap)[largest] { largest = leftChild } // Check right child if rightChild < len(*heap) && (*heap)[rightChild] > (*heap)[largest] { largest = rightChild } if largest != i { (*heap)[i], (*heap)[largest] = (*heap)[largest], (*heap)[i] i = largest } else { // If largest is the root, we are done break } } return top }
因此，只需两个相对简单的函数，我们就可以维护一个二叉堆。这些函数最多需要⌈log 2 N ⌉比较，其中N是数组中元素的数量。有趣的是，二叉堆提供了一种合理的算法来对数组进行排序，有时称为堆排序：将所有元素插入二叉堆中，然后重复删除顶部值。结果是O ( N log N )算法。
就像我们可以在数组上实现位集一样，我们可以在动态数组上实现动态位集。方法大致相同，但数组被切片替换。重要的是，我们需要检查是否需要扩展位集。当需要时，我们通过分配更大的数组并复制现有数据来增加位集。请注意，我们选择将切片增大所需数量的两倍：这可以防止用户可能逐一访问位（0、1、…）的退化情况，从而导致重复复制和分配。
// BitSet represents a dynamically growing bitset type BitSet struct { bytes []byte } // ensureCapacity makes sure we have enough bytes to access the specified index func (bs *BitSet) ensureCapacity(index int) { requiredBytes := (index + 1 + 7) / 8 if len(bs.bytes) < requiredBytes { // Grow the slice if necessary newBytes := make([]byte, requiredBytes*2) copy(newBytes, bs.bytes) bs.bytes = newBytes } } // Set sets the bit at 'index' to 1 func (bs *BitSet) Set(index int) { bs.ensureCapacity(index) bs.bytes[index/8] |= 1 << uint(7-(index%8)) } // Clear sets the bit at 'index' to 0 func (bs *BitSet) Clear(index int) { bs.ensureCapacity(index) bs.bytes[index/8] &^= 1 << uint(7-(index%8)) } // Get returns the value of the bit at 'index' func (bs *BitSet) Get(index int) bool { bs.ensureCapacity(index) return bs.bytes[index/8]&(1<<uint(7-(index%8))) != 0 }
哈希表和映射
您通常需要一个数据结构，您可以在其中使用非连续整数（例如 10、1000、100000）或其他类型的值（例如字符串）访问值。例如，也许您想要一张从姓名到电话号码的地图。
最有用的数据结构之一是哈希表。哈希表建立在数组之上，但它们不使用连续的整数值作为索引，而是可以采用几乎任何类型的值（例如字符串）作为键。
哈希表的基本技巧是使用哈希函数将任意键映射到整数值。整数值用作数组内的索引。通常选择数组的大小与不同键的数量相当。因此，哈希表是数组的概括，但您可以用哈希函数替换简单访问。哈希函数接受一个键并将其转换为哈希表数组的索引。
我们通常希望哈希函数将键均匀地分布在数组中以尽量减少冲突。当两个键映射到数组内的相同索引时，我们必须解决这个问题。一种可能性是创建更大的数组。但这会导致阵列在实践中增长过快。因此我们必须有效地处理碰撞。有两种广泛的策略。一种可能性是能够在数组的每个元素中存储多个键值对。它通常被称为桶方法。另一种可能性是将冲突的键值对存储在其他地方：例如，您可以将其存储到数组中的下一个可用槽。
许多哈希表实现都具有不同的属性。 Go 提供了一个内置的映射类型来实现哈希表。例如，要创建从字符串到整数的映射，我们可以按如下方式进行：
myMap := make ( map [ string ] int ) myMap [ "key" ] = 10
Go 使用存储桶方法：数组中的每个元素可以存储多个值。 Go 的 Map 实现中的每个存储桶都包含多个键值对。每个存储桶的确切数量可能会有所不同，但它旨在有效地处理少量条目。例如，我们可以将这种类型的数据结构与切片一起使用：
type bucket struct { keys [] string // Keys values [] int // Values }
当两个键散列到相同的索引时，它们被放置在同一个桶中。
查找键时，我们计算键的哈希值，使用哈希值找到正确的存储桶，检查存储桶中的每个条目是否有匹配的键。只要桶足够小，性能就可以接受。
我们经常计算哈希表中存储的键的数量，并将其除以数组的大小。结果称为负载因子。当与底层数组的大小相比，键的数量过多时，数组就会增长，并重建哈希表。这通常会减少桶的平均大小。同样，如果剩下的键太少，我们可以减小数组的大小。
让我们考虑一个完整的例子：
package main import ( "errors" "fmt" ) type Bucket struct { keys [] string values [] int } func ( b * Bucket ) Add ( key string , value int ) { b . keys = append ( b . keys , key ) b . values = append ( b . values , value ) } func ( b * Bucket ) Find ( key string ) ( int , error ) { for i := 0 ; i < len ( b . keys ); i ++ { if key == b . keys [ i ] { return b . values [ i ], nil } } return 0 , errors . New ( "Not found" ) } type HashTable struct { array [] Bucket } func NewHashTable ( size int ) * HashTable { return & HashTable { make ([] Bucket , size ), } } func ( ht * HashTable ) hash ( key string ) int { // A very simple hash function hash := 0 for i := 0 ; i < len ( key ); i ++ { hash += 31 * int ( key [ i ]) } return hash % len ( ht . array ) } func ( ht * HashTable ) Get ( key string ) ( int , error ) { return ht . array [ ht . hash ( key )]. Find ( key ) } func ( ht * HashTable ) Set ( key string , value int ) error { _ , e := ht . Get ( key ) if e == nil { return errors . New ( "Key already present" ) } ht . array [ ht . hash ( key )]. Add ( key , value ) return nil } func main () { ht := NewHashTable ( 10 ) ht . Set ( "apple" , 1 ) ht . Set ( "banana" , 3 ) fmt . Println ( ht . Get ( "apple" )) // Should print 1 }
我们的例子被简化了。然而，它说明了哈希表如何工作的基本原理。
我们描述的使用存储桶的方法实现起来相对简单，但由于将存储桶维护为单独的动态数组的开销，它可能并不总是提供最佳性能。相反，我们可以考虑一种变体，即数组中的每个槽都有一个键值。这种替代模型有时称为开放寻址。当两个键哈希到同一个槽时，我们可以将其中一个键值对移动到另一个可用槽，或者增加底层数组的大小。在查询时，我们首先根据键的哈希值搜索键值。如果找到另一个键值，我们将访问下一个槽，直到找到我们正在寻找的值，或者找到一个空槽。只要我们保持底层数组足够大，以便相当大一部分槽是空的，性能就可以接受。
以下代码说明了开放寻址背后的主要思想，但底层数组不会随着添加更多值而增长。要添加此功能，我们应该跟踪添加的键的数量，并根据需要增长数组。作为指示可用插槽的哨兵，我们使用空键。在实践中，我们需要添加额外的检查，以确保用户不会尝试添加带有空字符串的键，并适当地处理这种情况。
type Item struct { key string value int } type HashTable struct { items []Item emptyValue Item } func NewHashTable(size int) *HashTable { ht := &HashTable{ items: make([]Item, size), emptyValue: Item{key: "", value: -1}, } // Initialize all slots with emptyValue for i := 0; i < size; i++ { ht.items[i] = ht.emptyValue } return ht } func hash(key string) int { // A very simple hash function hash := 0 for i := 0; i < len(key); i++ { hash += 31 * int(key[i]) } return hash } // Put adds a key-value pair to the hash table func (ht *HashTable) Put(key string, value int) { hashValue := hash(key) % len(ht.items) for { if ht.items[hashValue] == ht.emptyValue { ht.items[hashValue] = Item{key: key, value: value} return } if ht.items[hashValue].key == key { ht.items[hashValue].value = value return } // Linear probing to find next available slot hashValue = (hashValue + 1) % len(ht.items) } } // Get retrieves a value from the hash table by key func (ht *HashTable) Get(key string) (int, bool) { hashValue := hash(key) % len(ht.items) for i := 0; i < len(ht.items); i++ { if ht.items[hashValue].key == key { return ht.items[hashValue].value, true } if ht.items[hashValue] == ht.emptyValue { return -1, false // key not found } hashValue = (hashValue + 1) % len(ht.items) } return -1, false // key not found after full cycle }
在某些情况下，有许多替代方案甚至可能比开放寻址更快，例如布谷鸟散列。在实践中，程序员很少实现自己的哈希表，但他们应该意识到有不同的实现具有各种优点。
仅具有键的哈希表可用于实现集合数据结构。也就是说，我们并不总是需要有价值观。值得考虑的一个直接变化是允许将键映射到多个不同的值。这种变体有时称为多重贴图。
结论
尽管计算机科学中有无数的数据结构，但通过数组和一些简单的函数可以实现很多功能。在组织数据时，您应该首先尝试使用数组。在某些情况下，如果您有集合或映射，则可能需要哈希表。它应该涵盖绝大多数数据结构。
为了说明这个想法，请考虑 JSON。 JSON（JavaScript 对象表示法）是一种标准的基于文本的数据交换格式，通常用于在线交换数据。它具有原始值（字符串、数字、布尔值、空值）和复合类型（数组和对象）。对象是从字符串到原始值或其他复合类型（数组和对象）的映射。我们将对象表示为大括号{}内以逗号分隔的键值对，并使用冒号作为键和值之间的分隔符。我们对数组使用方括号[] ，用逗号分隔值。考虑以下代表员工列表的示例。
{ "employees":[ { "name":"Richard", "salary":56000, "function":"CEO" }, { "name":"Lisa", "salary":55000, "function":"accountant" } ] }
根据经验，尽管 JSON 很简单，但它足以表示大多数数据。一个关键的见解是，通过将数组和映射与一些数字和字符串的标准类型相结合，您可以解决大多数问题。
在某些情况下，专门的数据结构可以提供卓越的性能。但您应该注意，当底层数据结构更简单时，优化代码通常更容易。
原文： https://lemire.me/blog/2024/12/08/data-structures-as-jigs-for-programmers-go-edition/