练习1 — map 遍历顺序验证

建一个 8 元素的 map，range 5 次，每次打印前 3 个 key → 观察随机性

加分：跑 10000 次统计每个 key"当第一"的频率，验证均匀分布

练习2 — string ↔ []byte 拷贝验证

用 unsafe 读底层 Data 指针，验证 []byte(s) 和 string(b) 都会拷贝

加分：用 unsafe 实现零拷贝转换（但别改！会 panic）

可选：strings.Builder vs += 拼接 10000 次的性能对比



```go
package main

import (
	"fmt"
	"strconv"
	"strings"
	"time"
	"unsafe"
)

func main() {
	string2bytes()
}

// map 遍历顺序验证-1
func mapsort() {
	m := make(map[string]int)
	for i := 0; i < 8; i++ {
		key := fmt.Sprintf("key%d", i)
		value := 0
		m[key] = value
	}
	for j := 0; j < 5; j++ {
		fmt.Println("-----------------")
		sign := 0
		for key, value := range m {
			fmt.Printf("key :%s ==> value: %d\n", key, value)
			sign++
			if sign == 3 {
				break
			}
		}
		fmt.Println("-----------------")
	}
	fmt.Println("=====================")
	for j := 0; j < 10000; j++ {
		sign := 0
		for key, value := range m {
			m[key] = value + 1
			sign++
			if sign == 1 {
				break
			}
		}
	}
	fmt.Println("item 2 result:")
	for key, value := range m {
		fmt.Printf("key :%s ==> value: %d\n", key, value)
	}
}

// string ↔ []byte 拷贝验证
func string2bytes() {
	s := "hello world!"

	b := []byte(s)

	strData := unsafe.StringData(s)

	sliceData := unsafe.SliceData(b)
	fmt.Println("===[]byte and string 1===")
	fmt.Printf("source string address: %p\n", strData)
	fmt.Printf("[]byte address: %p\n", sliceData)
	fmt.Printf("same: %v\n", strData == sliceData)

	fmt.Println("===[]byte and string 2===")
	b2 := []byte("qqqwwweee")
	str2 := string(b2)

	strData2 := unsafe.StringData(str2)
	sliceData2 := unsafe.SliceData(b2)
	fmt.Printf("source string address: %p\n", strData2)
	fmt.Printf("[]byte address: %p\n", sliceData2)
	fmt.Printf("same: %v\n", strData2 == sliceData2)

	fmt.Println("o copy skip")

	fmt.Println("===================")
	starttime := time.Now()
	result := ""
	for i := 0; i < 10000; i++ {
		result = result + strconv.Itoa(i)
	}
	fmt.Println(result)
	elapsedtime := time.Since(starttime)
	fmt.Printf("use time: %v\n", elapsedtime)
	fmt.Println("===================")
	var buff strings.Builder
	starttime2 := time.Now()
	for i := 0; i < 10000; i++ {
		buff.WriteString(fmt.Sprintf("%d", i))
	}
	fmt.Println(buff.String())
	elapsedtime2 := time.Since(starttime2)
	fmt.Printf("use time: %v\n", elapsedtime2)
}

func getMapB() {
	//新版本已经是swiss table没有B字段
}

map和string的学习

使用正则和net包将ip段中的IP提取出来



```go
package main

import (
	"fmt"
	"net"
	"regexp"
	"strconv"
	"strings"
)

func main() {
	input := []string{"192.168.75.[10-244]", "192.168.75.[5-55]", "192.168.75.111", "192.168.75.[140-10]", "192.168.75.133-192.168.75.11", "192.168.75.133-192.168.75.355"}
	for _, iprange := range input {
		fmt.Printf("Deal iprange: %s\n", iprange)
		r, e := IPRangeParser(iprange)
		if e != nil {
			fmt.Println(e.Error())
		}
		for _, ip := range r {
			fmt.Println(ip.To4().String())
		}
	}

}

func IPRangeParser(iprange string) ([]net.IP, error) {
	//常用的ip范围指定方式：
	// 192.168.10.[1-100] 1-100范围
	// 192.168.10.1-192.168.10.100 1-100范围
	// 192.168.10.100 单个ip
	// 处理第一种解析：
	if strings.Contains(iprange, "[") || strings.Contains(iprange, "]") {
		//使用正则解析：
		pattern := `^(\d{1,3}\.\d{1,3}\.\d{1,3})\.\[(\d+)-(\d+)\]$`
		re := regexp.MustCompile(pattern)
		matchs := re.FindStringSubmatch(iprange)
		if len(matchs) != 4 {
			return nil, fmt.Errorf("Eroor:Not OK IP Range Format:%s", iprange)
		}
		prefix := matchs[1]
		if net.ParseIP(prefix+".0") == nil {
			return nil, fmt.Errorf("Eroor:Not OK IP Range Format:%s", iprange)
		}
		start, err := strconv.Atoi(matchs[2])
		if err != nil {
			return nil, fmt.Errorf("Eroor:Not OK IP Start:%s", iprange)
		}
		end, err := strconv.Atoi(matchs[3])
		if err != nil {
			return nil, fmt.Errorf("Eroor:Not OK IP End:%s", iprange)
		}
		if start < 0 || start > 255 || end < 0 || end > 255 || start > end {
			return nil, fmt.Errorf("Eroor:Not OK IP Range:%s", iprange)
		}
		startip := net.ParseIP(fmt.Sprintf("%s.%d", prefix, start)).To4()
		endip := net.ParseIP(fmt.Sprintf("%s.%d", prefix, end)).To4()
		return GenerateIPs(startip, endip)
	} else if strings.Contains(iprange, "-") {
		pattern := `^(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})\s*-\s*(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})$`
		re := regexp.MustCompile(pattern)
		matchs := re.FindStringSubmatch(iprange)
		if len(matchs) != 3 {
			return nil, fmt.Errorf("Eroor:Not OK IP Range Format:%s", iprange)
		}
		startip := net.ParseIP(matchs[1]).To4()
		endip := net.ParseIP(matchs[2]).To4()
		if startip == nil || endip == nil {
			return nil, fmt.Errorf("Eroor:Not OK IP Range Format:%s", iprange)
		}
		return GenerateIPs(startip, endip)
	} else {
		ip := net.ParseIP(iprange)
		if ip == nil {
			return nil, fmt.Errorf("Eroor:Not OK IP Range Format:%s", iprange)
		}
		var ips []net.IP
		ips = append(ips, ip)
		return ips, nil
	}
}
func GenerateIPs(start, end net.IP) ([]net.IP, error) {
	startUint32 := ipToUint32(start)
	endUint32 := ipToUint32(end)

	if startUint32 > endUint32 {
		return nil, fmt.Errorf("Start %s is bigger then End %s\n", start, end)
	}
	var ips []net.IP
	for i := startUint32; i < endUint32+1; i++ {
		ip := uint32ToIP(i)
		ips = append(ips, ip)
	}
	return ips, nil
}

// ipToUint32 将IPv4地址转换为uint32（网络字节序）
func ipToUint32(ip net.IP) uint32 {
	ip = ip.To4()
	if ip == nil {
		return 0
	}
	return uint32(ip[0])<<24 | uint32(ip[1])<<16 | uint32(ip[2])<<8 | uint32(ip[3])
}

// uint32ToIP 将uint32转换为net.IP
func uint32ToIP(i uint32) net.IP {
	return net.IPv4(byte(i>>24), byte(i>>16), byte(i>>8), byte(i))
}

ip段分割操作

# 传统hash表

传统hash表是将key的hash值与value的数组下标对应实现，也就是将key的hash值经过某种运算得到一个整数值，这个值就是value列表的下标，就是key对应的value值



下面描述几个常用的概念：

- hash函数：用于将key转换为hash值得函数
- 冲突：即使很少得可能，但是不同的key可能得到相同的hash值，这时就冲突了
- 负载因子：表中元素的个数和桶中容量的对比：a = len(桶)/cap(桶)

## 解决冲突的方式

- 开放地址法或者线性探测法：即从冲突的位置往后探测，找到一个空闲的位置将冲突的元素放入；那么在查找的过程中，比如一个数hash值对应的位置是之前冲突的位置，比较key的值，key值不等，那么就按照之前插入的办法往后找，直到找到或者确认没有
- 链式寻址法：也就是在冲突的位置插入一个单链表，将所有冲突的hash值存入这个链表中
- 再hash法：用另外的hash算法来计算
- 建立公共移除区：凡是冲突的元素就放入移除区

## 为什么会发生冲突

打个比方：md5计算，就是无论多大的数据传入，出来的都是128位长度，即32位的16进制字符串，128位可以代表的个数是2^128-1个？，理想情况下如果我使用2^128个数插入，是不是就一定会导致冲突。当然和具体的算法也有关系，好的算法，可以尽量避免冲突。

# swiss table

部分概念说明：

- group：一个 Group 就是 8 个槽位（slots）的存储单元
- slot：插槽，用于存储单个key-value的
- 控制字节：group的前部分，一个slot的控制字节是7位，加上状态位就是8位，有多少个slot有多少个控制字节，如果有8个slot，那么就有8个控制字节



插入流程：

1 计算key的64位hash值，并分为H1：高57位，H2：低7位

2 找到起始group id，并且依照顺序检查group，看是否key在此group中，起始group id是`startIdx = H1 & (numGroups - 1)   // numGroups 是 2 的幂`；numGroups就是group的数量，如果在起始group没有，那么往后找`idx_i = (startIdx + (i + i*i) / 2) % numGroups,   i = 0,1,2,…`，i=0时就是startIdx

3 如何知道key在group中呢？就是通过匹配控制字节；先把H2首位填充0复制扩展7份，那么就是8个H2共8字节，与控制字节进行XOR异或计算，这样只要和H2匹配上的都是0x00,这里还没排除排除控制位的干扰：异或的结果做与计算：`xor & 0x7F7F7F7F7F7F7F7F`，这样就只保留低7位的计算结果，这样全为0的字节就是与H2匹配的slot了，那么如果提取全为0的部分：

```go
result = masked + 0x7F7F7F7F7F7F7F7F
// 上面的操作后，全为0的部分，最高位还是0 ，只要是非0 的部分，最高位是1
result = ^result                    // 取反，匹配的字节最高位变成 1
result = result & 0x8080808080808080  // 只保留最高位
```

4 将最高位提取出来：

```go
最后一步，将 result 的各个字节最高位提取出来，压缩成一个 8 位整数：
bits = (result >> 7) & 0x010101010101010         // 每个字节最高位移到最低位
bits = bits * 0x0101010101010101            // 乘法将所有字节的最低位移到最高字节
bits = bits >> 56                           // 取出最高字节（即8个位）
这样一个字节中，1的位置就是对应匹配的了
```

传统hash表和Swiss Table的区别

md转html   https://gitee.com/duzy2023/md2html   
ed2k下载工具     
地理解析工具

传统hash表

压缩前缀树（Radix Tree）实现与解析