search——id映射

假设某系统只有‘六万‘用户，不会增加也不会减少，那么用户ID[0,59999)完全可以使用长度是六万的数组，对其建立索引，若用户注册则在对应下标的元素处置1，即桶排序的思想，达到增删查都是O(1)的时间复杂度的效果var userIds [6_0000]uint8

若用户的ID由3位长度之内的 阿拉伯数字+26个小写字母组成的，那么可以将字符串类型，转换为int类型。将用户ID看做36进制的数(0~35)，"abc"这个ID表示成十进制的数为 a*36^2 + b*36^1 + c*36^0,为了压缩范围，将 0,1,2...9,a,b,c...z 编号为0,1,2...10,11,12...35。如此操作后，原“abc"这个id可以表示成十进制的 10*36^2 + 11*36 + 12。即使这3位数是“最大的36进制数”，‘zzz’, 那么可以用十进制的 35*36^2 + 35*36 + 35 + 1 个空间来存储他们。这也是一种Hash的雏形。

const l = 35*36*36 + 35*36 + 35 + 1 //46655 + 1
var userIds [l]uint8

func stringToInt(id string) (res int) {
	if len(id) > 3 {
		panic("id length > 3")
	}

	for i := 0; i < len(id); i++ {
		if !(id[i] >= '0' && id[i] <= '9' || id[i] >= 'a' && id[i] <= 'z') {
			panic("invalid number")
		}
	}

	for i := len(id) - 1; i >= 0; i-- {
		if id[i] >= '0' && id[i] <= '9' {
			res += int(id[i]-'0') * int(math.Pow(36, float64(i)))
		} else {
			res += int(id[i]-87) * int(math.Pow(36, float64(i)))
		}
	}
	return res
}

func insert(id string) {
	userIds[stringToInt(id)] = 1
}

func delete(id string) {
	userIds[stringToInt(id)] = 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32