数据结构-map

数据结构-哈希算法

哈希原理

hash哈希是一种算法

• y = hash(x) 给定一个x一定得到固定的y
• x是输入，x取值范围称为输入空间，x是任意值，x是任意长度（go中字节序列）
• y是输出，y取值范围称为输出空间，但输出内容是固定长度的（字节序列长度固定）
• 输入是无穷个，但是固定字节的输出却能表示的状态是有限个
• 一定存在xm、xn经过hash函数算出的y值一样，把不同x值求得y值一样的情况称为hash冲突，他们碰撞了
• hash算法设计还要兼顾 高效 ，x一个微小的变化，哪怕是一个bit位的变化，也将引起结果y巨大的变化
• hash不可逆，不能从结果反推输入值
• 单向散列算法 不可逆
• 用在KEY的计算上

哈希算法

• MD5（Message Digest Algorithm 5）信息摘要算法5，输出是128位。运算速度叫SHA-1快

  • 用户密码存储
  • 上传、下载文件完整性校验
  • 大的数据的快速比对，例如字段很大，增加一个字段存储该字段的hash值，对比内容开是否修改

• SHA（Secure Hash Algorithm）安全散列算法，包含一个系列算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512。

  • 数字签名防篡改

  package main
  
  import (
  	"crypto/sha256"
  	"fmt"
  )
  
  func main() {
  	h := sha256.New()
  	h.Write([]byte("abc"))// 提供字节流
  	r := h.Sum(nil)
  	s := fmt.Sprintf("%x", r)  // 把字节序列的每个字节以16进制显示
  	fmt.Printf("%T %s %d \n", r, s, len(s))
  }
  []uint8 e4b0cf398b77ac6efb797544d268782dc7d082e59c4d1aff15f3ae661588f0eb 64 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

  映射

  映射Map，也有语言称为字典

• 长度可变

• 存储的元素是key-value对（键值对），value可变

• key无序不重复

• 不可索引，需要通过key来访问

• 不支持零值可用，也就是说，必须要用make或字面常量构造

• 引用类型

• 哈希表

内存模型

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

哈希表

• 存储kv对，一个kv对称为一个元素，键值对entry、item

• len表示元素的个数，即 kv对的个数，cap不能用

• key 不能重复，无序

  • key按照某种先后顺序加入到map中，但是从哈希表中看不出顺序来
  • key是关键的，还有唯一的意思
  • 相同key会 去重

• 引用类型

  • 有一个标头值
  • 有一个指针指向底层的hash表

• 不支持零值可用

哈希表原理 y=hash(x)

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

hash冲突

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

理解：有key hash后的key value 三种

1、如果key相同 则hash后的key一定相同

2、key不相同但是存在hash后的key是相同的，也就是房间号是相同

我们可以理解hash后的key为房间号，hash冲突就是hash后的key是相同的，若hash就的key是相同的可以存放在一个房间里面，在这个房间里面可以放几个key-value对，若是查找这个key-value，先找到这个房间，在这个房间内在查找key

构造

func main() {
	var m1 map[string]int // nil，很危险。map不是零值可用
	fmt.Println(m1, m1 == nil)
	m1["t"] = 200 // panic，不可以
}
//结论：零值不可用，用var a map[int]int 零值是nil但是后面无法增加kv对
1
2
3
4
5
6
7

// 1 字面量
//字面量定义map[string]int{k1:v1} ，花括号表示字面量
func main() {
	var m0 = map[string]int{}  // 安全，没有一个键值对而已
	fmt.Println(m0)
}
map[]

func main() {
	var m1 = map[string]int{
		"a": 11,
		"b": 22,
		"c": 33,
	}
	fmt.Println(m1)

}
map[a:11 b:22 c:33]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//make
func main() {
	m2 := make(map[int]string) // 一个较小的起始空间大小
    //make(map[string]int) // 没有告诉未来容纳多少元素，先开辟较小空间，如果未来kv对较多，可能频繁扩容
	m2[100] = "abc"
	m3 := make(map[int]string, 100) // 分配足够容量来容纳100个元素，长度为0。为了减少扩容，可以提前给出元素个数
	fmt.Println(m2, m3)
}

map[100:abc] map[]

//结论：
make(map[string]int, 100) 表示为100个元素自动生成足够（内部按照算法生成）的空间   make(map[string]int, 100)  告诉未来容纳多少元素，先开辟合适的空间来存储这些kv对，注意一般空间大小别元素个数大一些    
var m0 map[string]int 这不是赋值语句，go语言零值可用，但是这是引用类型，所以是nil
1
2
3
4
5
6
7
8
9
10
11
12
13
14

新增或修改

func main() {
	var m = make(map[string]int)
	m["a"] = 11 // key不存在，则创建新的key和value对
	m["a"] = 22 // key已经存在，则覆盖value
	fmt.Println(m)
}
map[a:22]
1
2
3
4
5
6
7

查找

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

func main() {
	var m = make(map[string]int)
	m["a"] = 11
	m["a"] = 22
	if _, ok := m["b"]; ok {
		fmt.Println("存在")
	} else {
		fmt.Println("不存在")
	}
}
1
2
3
4
5
6
7
8
9
10

key访问map最高效的方式

长度

// 返回kv对的个数
func main() {
	var m = make(map[string]int)
	m["a"] = 11
	m["a"] = 22

	fmt.Println(len(m))
}
1
1
2
3
4
5
6
7
8
9

注意：由于map的特殊构造，不能使用cap。

移除

func main() {
	var m = make(map[string]int)
	m["a"] = 11  
	m["b"] = 22

	fmt.Println(m)
	delete(m, "a")// 存在，删除kv对
	fmt.Println(m)

}

map[a:11 b:22]
map[b:22]
即便不存在删除也不会panic
1
2
3
4
5
6
7
8
9
10
11
12
13
14

遍历

func main() {
	var m = map[string]int{
		"a": 11,
		"b": 22,
		"c": 33,
	}
	for k, v := range m {
		fmt.Println(k, v)
	}
}
a 11
b 22
c 33
1
2
3
4
5
6
7
8
9
10
11
12
13

注意：map的key是无序的，千万不要从遍历结果来推测其内部顺序，因为key在内存中是乱序

排序sort

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

升序

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


func main() {
	b := []string{"xyz", "a", "abc", "Ab", "X"}
	sort.Strings(b)
	fmt.Println(b)
}
[Ab X a abc xyz]    //根据ascill码排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

降序

降序和升序不同 升序在go中已经定义好了 只需要调用 但是降序不行 

func main() {
	b := []string{"xyz", "a", "abc", "Ab", "X"}
	sort.Sort(sort.Reverse(sort.StringSlice(b)))  //Reverse取反
	fmt.Println(b)
}
[xyz abc a X Ab]
1
2
3
4
5
6
7
8

二分查找

前提：必须先排序，并且是升序

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