「这是我参与2022首次更文挑战的第8天，活动详情查看：2022首次更文挑战」

生命不息，学习不止

题外话

大年初三啦，大家有没有去看春节档的，话说《这个杀手不太冷静》还挺好看的，但是，今天春节档的电影票怎么这么贵，怎么回事，我的钱是大风刮来的嘛，良心不会痛的嘛！

废话不多说，上货

LeetcCode-3

无重复字符的最长子串

题目如下：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

还是这道题，因为还有知识点呢

go实现算法

func lengthOfLongestSubstring(s string) int {
	strmap := make(map[byte]int)

	count := 0
	for i, j := 0, 0; j < len(s); j++ {
		if val, ok := strmap[s[j]]; ok {
			i = max(val, i)
		}
		count = max(count, j-i+1)
		strmap[s[j]] = j + 1   //添加元素
	}
	return count
}

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}

小问题回顾

小问题:什么是负载因子？负载因子有什么作用？扩容机制是怎样的？

前两回基本已经讲清了map底层结构的核心定义和存储结构，那今天就来说说map的扩容机制

Map的hash冲突

说到map的扩容，就一定会提到map的hash冲突处理，其实上两回多多少少都已经提到了hash冲突，

map的hash冲突是指当两个或两个以上的key经过hash计算，被分配到同一个bucket。

每个bucket的容量是8个键值对，所以当多个相同key扔进同一个bucket中时，bucket容量不够时，go就会采用链接地址的方式，也就是* overflow指向下一个bucket，用类似链表的方式将bucket连接起来。

具体结构类似如下。

Map的负载因子

提到扩容，出了hash冲突，还有另外一个不可缺少的的机制，负载因子。

java中的map也有个负载因子，默认是0.75，只要hash桶的容量到达负载因子* hash的最大容量，就会触发扩容。

go的map中虽然没有显式的定义，但是却有类似的公式代码，如下

这样看可能不太明白，毕竟没有上下文，那我就直接说一下

负载因子 = 键数量/bucket数量

举个例子哈，若有bucket有8个，键值对也有8个，则这个哈希表的负载因子就是 1

负载因子代表的是hash表的一个冲突情况，对于负载因子来说，

负载因子过小，说明空间利用率低
负载因子过大，说明冲突严重，存取效率低

只有负载因子在一个合适的范围，才能保证整个map效率是较高的

go中的机制就是当负载因子达到6.5时，就会触发rehash

Map的扩容机制

map的扩容是中渐进式扩容方式，会根据不同的场景有所变换，一般触发扩容分为两种情况

负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
overflow数量 > 2^15时，也即overflow数量超过32768时。

第一种方式一般会触发增量扩容，就是新建一个长度为原bucket二倍的新bucket，然后旧bucket数据搬迁到新的bucket。

为了防止已经存储了大量数据，搬运造成延迟，Go采用逐步搬迁策略，即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。

第二种方式一般触发的就是等量扩容了，例如在极端场景下，不断的增删map中的数据，而键值对正好集中在一小部分的bucket，这样会造成overflow的bucket数量增多，但负载因子又不高，从而无法执行增量搬迁的情况

等量扩容不会产生新的bucket，而是类似触发rehash一样，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。

你以为结束了

小问题:又要搞一个新的题了，惊不惊喜，意不意外，就这个吧 21. 合并两个有序链表

下一篇就讲，敬请期待

大家看完发现有什么错误，写在下面吧！跟我黑虎阿福比划比划！