一、map的基本语法

• 声明 map

  • 使用 make 函数创建一个 map:

    go

    m := make(map[string]int)
    

  • 使用字面量的方式创建 map:

    go

    m := map[string]int{"apple": 1, "banana": 2, "cherry": 3}
    

• 插入/修改元素

  • 使用下标语法插入或修改元素:

    go

    m["apple"] = 1
    m["banana"] = 2
    

• 删除元素

  • 使用 delete 函数删除元素:

    go

    delete(m, "apple")
    

• 查找元素

  • 使用下标语法查找元素,并使用两个返回值判断元素是否存在:

    go

    value, ok := m["banana"]
    if ok {
        fmt.Println("Value:", value)
    } else {
        fmt.Println("Key does not exist")
    }
    

• 遍历 map

  • 使用 for range 循环遍历 map:

    go

    for key, value := range m {
        fmt.Printf("%s: %d\n", key, value)
    }
    

• 判断 map 是否为空

  • 使用 len 函数检查 map 的长度是否为 0:

    go

    if len(m) == 0 {
        fmt.Println("Map is empty")
    }
    

• 初始化带有预分配容量的 map

  • 在创建 map 时,可以指定初始容量,以避免后续的扩容操作:

    go

    复制

    m := make(map[string]int, 10)
    

• 使用 nil 值表示未初始化的 map

• 未初始化的 map 值为 nil，可以用于表示缺失的数据:

  • var m map[string]int
    if m == nil {
        fmt.Println("Map is nil")
    }

 二、map排序

1.使用切片排序

• 首先将 map 的键值对转换为切片,然后对切片进行排序。
• 这种方式适用于需要对整个 map 进行排序的场景。

package main

import (
    "fmt"
    "sort"
)

func main() {
    m := map[string]int{"apple": 2, "banana": 1, "cherry": 3}

    // 将 map 转换为切片
    pairs := make([]keyValue, 0, len(m))
    for k, v := range m {
        pairs = append(pairs, keyValue{k, v})
    }

    // 对切片进行排序
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i].key < pairs[j].key
    })

    // 输出排序后的结果
    for _, p := range pairs {
        fmt.Printf("%s: %d\n", p.key, p.value)
    }
}

type keyValue struct {
    key   string
    value int
}

2.使用 sort.StringSlice 排序

• 如果 map 的键都是字符串类型,可以直接使用 sort.StringSlice 进行排序。
• 这种方式适用于只需要对 map 的键进行排序的场景。

package main

import (
    "fmt"
    "sort"
)

func main() {
    m := map[string]int{"apple": 2, "banana": 1, "cherry": 3}

    // 将 map 的键转换为 sort.StringSlice
    keys := sort.StringSlice(make([]string, 0, len(m)))
    for k := range m {
        keys = append(keys, k)
    }

    // 对键进行排序
    sort.Sort(keys)

    // 输出排序后的结果
    for _, k := range keys {
        fmt.Printf("%s: %d\n", k, m[k])
    }
}

3.map底层实现

1、结构

Go 语言中 map 的底层实现使用了哈希表(hash table)结构。具体来说,Go 语言中的 map 由以下几个部分组成:

1. 哈希表:

   • map 的底层是一个哈希表(hash table)。哈希表由一组 bucket 组成,每个 bucket 存储键值对。

   • 当插入一个新的键值对时,会根据键的哈希值来确定该键值对应的 bucket 索引。

2. 哈希函数:

   • Go 运行时使用一个特殊的哈希函数来计算键的哈希值。这个哈希函数具有良好的分布性,可以将键均匀地散列到不同的 bucket 中。

3. 增长机制:

   • 当 map 中的键值对数量超过某个阈值时,map 就会自动扩容,增加 bucket 的数量。

   • 扩容时,Go 运行时会重新计算所有键值对的哈希值,并将它们分配到新的 bucket 中。

4. 冲突解决:

   • 由于哈希函数可能会产生哈希值冲突,即不同的键可能会映射到同一个 bucket 中。

   • Go 的 map 实现使用了开放寻址法(open addressing)来解决冲突,即当发生冲突时,会尝试找到下一个可用的 bucket 来存储该键值对。

5. 元数据:

   • 除了哈希表本身,map 还有一些辅助的元数据,如 map 的长度、已使用的 bucket 数量等信息。

   • 这些元数据用于管理 map 的状态,并优化 map 的操作。

 2.扩容机制

在 Go 语言中,当 map 需要扩容时,是通过增加 bucket 的数量来实现扩容,而不是增加单个 bucket 的容量。

具体来说:

1. 初始 bucket 数量:

   • 当创建一个新的 map 时,它的初始 bucket 数量通常是 8。

2. 扩容时 bucket 数量的变化:

   • 当 map 中的键值对数量超过某个阈值时,map 就会进行扩容操作。

   • 在扩容时,map 的 bucket 数量通常会增加到原来的 2 倍。

3. 单个 bucket 容量的固定性:

   • Go 语言中,每个 bucket 的容量是固定的,默认为 8 个键值对。

   • 这个 bucket 容量是不可以由开发者直接修改的。

 四、什么是哈希冲突（哈希碰撞）

现在一般都认为这两种一个概念，其实哈希冲突和哈希碰撞并不是完全相同的概念

1. 哈希冲突 (Hash Collision):

   • 哈希冲突是指两个不同的输入数据经过哈希函数计算后得到相同的哈希值。
   • 这种情况在任何哈希表实现中都可能发生,因为哈希函数的输出空间通常小于输入空间,所以会存在哈希值重复的可能性。

2. 哈希碰撞 (Hash Clash):

   • 哈希碰撞是指在哈希表中,两个不同的键经过哈希函数计算后得到相同的索引位置。
   • 这种情况会导致哈希表中存储的键值对发生冲突,需要采取某种冲突解决策略来处理。

总的来说:

• 哈希冲突是哈希函数本身的特性,是无法完全避免的。
• 哈希碰撞则是由于哈希表的有限容量,导致不同的键被映射到同一个索引位置。

五、解决哈希碰撞方法

 1.链地址法

原理:为每个哈希表槽位维护一个链表(通常是单链表或双链表)。当发生哈希碰撞时,将冲突的键值对存储在对应槽位的链表中。

• 优点:
  • 能有效解决哈希碰撞问题,即使发生大量碰撞也不会影响查找效率。
  • 实现简单,并且链表的动态扩展能力使得哈希表能够自适应数据的增长。
• 缺点:
  • 需要额外的存储空间来维护链表结构。
  • 在链表较长的情况下,查找效率会下降。

 2.开放地址法

原理:当发生哈希碰撞时,在哈希表中寻找下一个可用的槽位来存储键值对。常见的开放地址法有:

•     线性探测法:每次探测下一个槽位,直到找到可用的槽位。
• 二次探测法：每次探测的位置为 (hash(key) + i^2) % table_size，其中 i 是探测次数。
• 双重散列法：使用两个不同的哈希函数进行探测。

优点:

• 不需要额外的存储空间来维护链表。
• 当负载因子较低时,查找效率很高。

缺点:

• 当负载因子较高时,可能会出现"聚簇"(clustering)现象,导致查找效率下降。
• 需要进行多次探测才能找到可用的槽位,查找效率会受到影响。

 3.调整哈希函数

原理：选择一个更好的哈希函数,使其能够将输入更均匀地分散到输出空间中,减少哈希碰撞的概率。

• 常见的高质量哈希函数包括 FNV-1a、MurmurHash3 和 xxHash 等。

优点：

• 可以有效减少哈希碰撞的发生,提高哈希表的性能。
• 不需要额外的存储空间或复杂的数据结构。

缺点：

• 需要对哈希函数的特性有深入的了解,才能选择合适的函数。
• 即使使用优秀的哈希函数,也无法完全避免哈希碰撞的发生。

 4.增大哈希表容量

原理：增大哈希表的大小,以降低负载因子(load factor)，从而减少哈希碰撞的概率。

• 负载因子 = 哈希表中元素数量 / 哈希表大小
• 优点：
• 可以有效减少哈希碰撞的发生,提高哈希表的性能。

缺点：

• 需要重新分配和rehash所有的键值对,耗时较长。
• 如果增大哈希表容量之后,数据分布仍然不均匀,碰撞问题仍然存在。

 5.使用其他数据结构

原理：对于某些特定的应用场景,可以考虑使用其他数据结构来代替哈希表,例如红黑树、跳表等。

优点：

• 可以解决哈希碰撞问题,并提供其他功能,如有序性、区间查询等。

缺点：

• 实现可能较为复杂,性能特性也与哈希表有所不同。
• 不适合所有场景,需要根据具体需求进行权衡。