go语言hash表

map特性

长度可变；存储的元素是key-value对（键值对），value可变 key无序不重复 不可索引，需要通过key来访问；不支持零值可用，也就是说，必须要用make或字面常量构造；引用类型； 哈希表

哈希算法

哈希Hash算法特征

y = hash(x)，给定一个x一定得到一个y值

x的范围是输入空间，输入可以是任意长度；y的范围是输出空间，输出是固定长度

hash函数一般设计的计算效率很高

由于输入空间（可以理解为取值范围）远远大于输出空间，有可能不同的x经过hash得到同样的y， 这称为碰撞，也称冲突

不同的x计算出的y值应当在输出空间中分布均匀，减少碰撞

不能由y反推出x，hash算法不可逆

x一个微小的变化，哪怕是一个bit位的变化，也将引起结果y巨大的变化

常见算法

SHA（Secure Hash Algorithm）安全散列算法，包含一个系列算法，分别是SHA-1、SHA-224、 SHA-256、SHA-384，和SHA-512。 用于数字签名防篡改。

MD5（Message Digest Algorithm 5）信息摘要算法5，输出是128位。运算速度比SHA-1快；用于用户密码存储，上传、下载文件完整性校验，大的数据的快速比对，例如字段很大，增加一个字段存储该字段的hash值，对比内容是否修改。

package main
import (
 "crypto/sha256"
 "fmt"
)
func main() {
 // https://pkg.go.dev/crypto/sha256#example-New
 h := sha256.New()
 h.Write([]byte("abc")) // 提供字节流
 r := h.Sum(nil)
 s := fmt.Sprintf("%x", r) // 把字节序列d的每个字节以16进制显示
 fmt.Printf("%T %s %d\n", r, s, len(s))
}

 内存模型

map采用哈希表实现。Go的map类型也是引用类型，有一个标头值hmap，指向一个底层的哈希表。

哈希表Hash Table

简单理解公式为 y = hash(x) 开辟一块内存空间，分割出一个个“房间”，这个房间称为bucket桶，按照y值为“房间”编号 使用给出的x计算出对应的y值，可以按照某种关系计算出数据将被存储到的“房间号码”，将数据存入该房间， 即使是hash函数设计的好，数据分布均匀，但是存储的数据很多，超过负载因子，则需要扩容， 否则再加入数据后，冲突太多，引起效率低下

理解的hash函数原理，可以用除留余数法来思考，即hash(x) = key mod p。p是hash表大小，看做房间 个数。

hash(x₀) => Room_k，计算出一个确定的房间号码。

hash冲突

房间有人占了，就重新找个空房间让客人住，这是开放地址法

房间有人占了，就挤在同一个房间内，将值用链表存储在一起，这是链地址法，也称拉链法

Go 语言采用拉链法，但做了一定的优化

创建map

    var m0 map[string]int // 这里只是声明m0，0值不可用
    fmt.Println(m0, len(m0))
    // 下面会panic：assignment to entry in nil map
    m0["who"] = 111 // 由于m0是nil，所以空map不可以使用

// 1 字面量
var m0 = map[string]int{} // 安全，没有一个键值对而已
var m1 = map[string]int{
 "a": 11,
 "b": 22,
 "c": 33, // Go要求这里以逗号结尾
}
// 2 make
m2 := make(map[int]string) // 一个较小的起始空间大小
m2[100] = "abc"
m3 := make(map[int]string, 100) // 分配足够容量来容纳100个元素，长度为0。为了减少扩
容，可以提前给出元素个数

 map的CRUD

查找的时间复杂度为O(1)，由于map的特殊构造，不能使用cap。