@TOC

ASCII 字符包含判断

最近换工作,暂时离开了世界上最好的语言,成为了一名 golanger (这好象是一个 web 框架的名字),这一次打算养成良好的习惯,那就从写博客开始吧。

文章背景

正在琢磨自己用 go 实现一个脚本语言,写词法分析的时候,需要匹配字符串的功能,既然编译器都自己写了,这也自己写一个吧,去研究了下 go 的实现,发现设计的很巧妙,所以分享一下,美中不足的是只适用于 ascii 码

源码展示

type asciiSet [8]uint32
const RuneSelf = 0x80
// 判断是否包含
func (as *asciiSet)contains(c rune) bool {
 return (as[c>>5] & (1 << uint(c&31))) != 0
}
// 生成 ascii 哈希表
func makeASCIISet(chars string) (as asciiSet, ok bool) {
 for i := 0; i < len(chars); i++ {
 c := chars[i]
 if c >= RuneSelf {
 return as, false
 }
 as[c>>5] |= 1 << uint(c&31)
 }
 return as, true
}

代码解析

type asciiSet [8]uint32

asciiSet 这是一个分了 8 个桶的哈希表(位图),用于存储匹配串包含的字符集合
匹配串输入后,将会被按位存储在 asciiSet。

下面这行代码,会对所有包含 非 asci i字符的串直接返回 false。

if c >= utf8.RuneSelf {
 return as, false
}

下面这行代码可以看作一个哈希算法。

1 << uint(c&31)

会把单个字符对应到一个 32位 的位图上面,

• &31 是由于分桶的设计,将高 3 位作为了桶标记
• 1 << 将 1 左移 0-31 位,用于存储已有的字符

(as[c>>5] & (1 << uint(c&31))) != 0

从字符对应的桶中取出位图,然后查看是否存在

思考

asciiSet 是其中的关键,但是也由于其大小限制加上移位操作,导致只适用于基础ascii,
当然,进行一定修改可以适用于更大的字符集,不过内存使用量会比较大。

本文来自:Segmentfault

感谢作者:爱简单

查看原文:go标准库实现---ASCII 字符包含判断

• 编辑
• 预览