@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，
当然，进行一定修改可以适用于更大的字符集，不过内存使用量会比较大。

有疑问加站长微信联系（非本文作者）