哈希表

映射

映射Map，也称为字典

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

哈希表

map是go中的实现
存储kv对，一个kv对，称为一个元素，键值对称为entry、item
len表示元素的个数，即kv对的个数
key不能重复且无序
- key按照某种先后顺序加入到map中，但是从哈希表中看不出顺序来
- key是关键的，唯一的
- 相同的key会去重
- 无序：
  - 在顺序表中，x、y，用顺序表认为x是y的前驱，y是x的后继
  - 在hash table中，x、y如果是key，那么x、y没有前后依存关系，是独立且唯一的key，在内存中位置不确定
不是线性表，是无序的，不能索引
是引用类型
- 有一个标头值
- 有一个指针指向低层的hash表
不支持零值可用
高效的，利用key，用空间换时间

哈希表原理

内存是线性编制的，容器都要划分格子（存储单元），每个存储单元占用的字节数相同

hash(key) => 存储单元房间号，每个通过一个简单的固定步数计算的公式就可以定位存储的内存地址，但是有可能出现hash冲突。

开地址法解决hash冲突：将冲突的kv对分配其他地址
拉链法解决hash冲突：在对应冲突的地址空间中，使用链表，将kv对存储到链表中，尾部追加
查询：
- 使用key查询，hash(key)算出内存地址，步骤是固定的四则运算，时间复杂度O(1)
- map应该使用key来查询才是最有效率的
问题：
- 1、如果冲突多了会怎么样
  - 冲突多了，每个对应的内存空间中都存放着多个kv对，x多y少，超过负载因子(0.65)，就需要扩容y
  - 不管什么容器，最好在使用之前，能估算出大概的数据规模

Map组成

header：指针指向底层的哈希表
构造：
- 零值不可用，用var a map[string]int 定义，零值是nil，但是后面无法增加kv对
- 可以使用字面量定义 map [string]int{k1:v1} ，花括号表示字面量
- make(map[string]int) 没有告诉未来容纳多少元素，先开辟较小空间，如果未来kv对较多，可能频繁扩容
- make(map[string]int,100) 表示为100个元素自动生成足够（内部按照算法生成）的空间

哈希算法

哈希hash算法特征

y=hash(x) ，给定一个x一定得到一个固定的y值
x的范围是输入空间，输入可以是任意长度
y的范围是输出空间，输出是固定长度
hash函数一般设计的计算效率很高
由于输入空间（可以理解为取值范围）远远大于输出空间，有可能不同的x经过hash得到同样的y，这称为碰撞，也称为冲突，解决冲突的方法为1、开地址法，2、拉链法
不同的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 Algorithm5）信息摘要算法，输出是128位。运算速度很快
- 用户密码存储
- 上传、下载文件完整性验证
- 大的数据的快速比对，例如字段很大，增加一个字段存储该字段的hash值，比对内容是否被修改

package main

import (
	"crypto/md5"
	"crypto/sha256"
	"fmt"
)

func main() {

m := md5.New() // 128位 /8 =  16字节
m.Write([]byte("123456"))
r := m.Sum(nil)
fmt.Printf("%x  len = %d\n", r, len(r))
// 输出，16个字节，e1位一个字节，8位
e10adc3949ba59abbe56e057f20f883e  len = 16

m2 := sha256.New() // 256位/8 = 32字节
m2.Write([]byte("123456"))
r2 := m2.Sum(nil)
fmt.Printf("%x  len=%d\n", r2, len(r2))
// 输出
8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92  len=32
}

内存模型

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

哈希表Hash Table

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

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

hash(Xo) => Roomk 计算出一个确定的房间号码。

hash冲突：

房间有人占了，就重新找一个空房间让客人住，这是开地址法
房间有人占了，就挤在同一个房间内，将值用链表存储在一起，这是链地址法，也称拉链法，Go语言采用，但做了一定的优化

构造

var m1 map[string]int // nil，很危险。map不是零值可用
fmt.Println(m1, m1 == nil)
m1["t"] = 200 // panic，不可以

// 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。为了减少扩容，可以提前给出元素个数

新增或修改

var m = make(map[string]int,200)
m["a"] = 123 // key不存在，则创建新的kv对
m["b"] = 456
m["a"] = 333 // key已经存在，则覆盖value

查找

使用map一般需要使用key来查找，时间复杂度为O(1)

fmt.Println(m["a"])
fmt.Println(m["a"]) // 存在返回22
fmt.Println(m["b"]) // 不存在返回零值0，这样不能判断"b"这个key存在否，需要解析返回值
if _, ok := m["b"]; !ok {
    fmt.Println("不存在", v) }
// 输出
false 0

key访问map是最高效的方式

长度

len(m) // 返回kv对的长度

注意：map不能使用cap

移除

delete(m, "a") // 存在，删除kv对
delete(m, "b") // 不存在，删除操作也不会panic

遍历

package main // 同一个包内可见
import (
	"fmt"
)

// 导入包或第三方包

func main() { // main函数叫做入口函数，go约定main函数必须在main包中定义
	var m = map[string]int{
		"a": 11,
		"b": 22,
		"c": 33}
	for k, v := range m {
		fmt.Println(k, v)
	}
}

注意：map的key是无序的，不用从遍历的结果来推测其内部顺序

排序

Go的标准库提供了sort库，用来给线性数据结构排序、二分查找

// 切片排序
// 针对int、string有快捷方法Ints、Strings
a := []int{-1, 23, 5, 9, 7}
// sort.Sort(sort.IntSlice(a)) // sort.IntSlice(a)强制类型转换以施加接口方法
sort.Ints(a)   // 就地修改原切片的底层数组
fmt.Println(a) // 默认升序
b := []string{"xyz", "a", "abc", "Ab", "X"}
sort.Strings(b)
fmt.Println(b)
// 降序
sort.Sort(sort.Reverse(sort.IntSlice(a)))
fmt.Println(a)

// 二分查找
a := []int{-1, 23, 5, 9, 7}
sort.Ints(a)
// 二分查找，必须是升序
// 二分查找的前提是 有序
i := sort.SearchInts(a, 7)
fmt.Println(i)

思考：什么是相同的key？hash值相同则key一定相同吗？冲突的key有什么异同？

有冲突的key就是相同的key吗？也就是说，如果2个key计算的hash值相同就是同一个key吗？key计算的hash值相同只能说明hash冲突，如果key也相等，才能说明是用一个key。同一个key计算的hash值一定一样，但是hash冲突不一定是同一个key