在 Swift 中使用 cmph

cmph 的全称是 C Minimal Perfect Hashing Library ,是一个很著名的用 C 写成的最小完美哈希库,什么是完美哈希?

完美哈希

这里我们不讲原理,你只需要知道传统的哈希有冲突,我们需要靠各种算法来处理冲突就可以了,对于哈希,总是需要一个表,这个表里预留了很多位置,然后计算出来的值就是这些位置的坐标,你可以把对应的数据放到坐标里。

但这时候有一个问题,如果这个预先的表不够大,或者说你的算法不够好,就会发生所谓的聚集,某一片区域值总是冲突,而某一片区域的值则是空的,所以,你的表长度总是要大于 key 的数量来容纳这些空余。

但如果你的算法足够牛逼,那么你就能做到让表的长度n最少能够等于key的数量!

当这种情况达成,那么我们就称这个哈希函数为最小完美哈希函数

cmph

那么这种东西真的存在吗?当然。cmph 就是一个,当然想要使用 cmph 还是有一点前提的,比如你的 key 得是不重复的,key 的数量得是固定的静态的。

比如说我的隐马尔可夫模型中的转移矩阵,就满足这么一个需求。

不过,cmph 是用 C 语言实现的,我们需要把 C 桥接到 Swift 中。

桥接

和桥接 oc 差不多, 你把下载好的cmph目录中的 src 目录里的源文件都拖到 Swift 项目中即可(记得选择拷贝而不是引用),如果是第一次拖入其他语言的内容,Xcode 会自动提示你创建桥接文件,然后你的项目中会有一个叫做 xxx-Bridging-Header.h 的文件,其中的xxx就是你的项目名字。

在里边写 #include "cmph.h" 就好了,这样你就把 cmph 的函数暴露给了 Swift。

整理项目

直接导入的 cmph 源代码不能直接在 Swift 项目里使用,如果你空项目编译,会遇到“多个 main 函数”的错误,去 cmph 源文件中,删除 main.c  bm_numbers.c  bm_bumbers.h 现在再编译试试,如果还报错,那么就删除那个包含 main 函数的源码即可,我们只用函数。

编译

cmph 其实是库和工具套装——这也是为什么源码里包含了 main 函数,我们进入下载的 cmph 目录里,执行如下命令进行编译:

这下你就可以在终端执行命令 cmph 了:

创建哈希表

使用工具创建哈希表而不是代码,因为它需要key是静态的,所以要事先准备key的文本列表,要求是纯文本文档,一行一个 key 即可,最大千万也妥妥的。

编码是utf8

根据命令提示,我们直接在目录里执行 cmph -g keys.txt 即可,如果你想要指定算法(具体的算法种类和特性可以见官网)比如我的数据库肯定是用在外存的,就用专门对外存做优化的 brz 算法,那么命令就变成了这样 cmph -g -a brz keys.txt 。

执行完毕后会在当前目录下生成 keys.txt.mph ,为了方便,我把它改为 keys.mph 。

验证

要看到对应的结果,我们可以再来一个文本文件,格式与 key 的列表的格式相同,里边写入你想要查询的 key,比如我命名为 keysq.txt ,这时候我们用 debug 模式输出查询结果:

获得结果

现在,我们可以用同样的方法把所有的 key 查一遍,就能得到每一个 key 对应的坐标了!

获得了结果,我们就可以根据位置来生成一个对应的文件,我用自己的编码方式编译了一个之际的二进制数据库,但位置根据 cmph 的坐标来对应,这样数据和位置就可以做到一一对应了,查询的速度是o(1).

在 Swift 中查询

现在,我们可以把生成的 mph 文件导入 Swift 项目备用了——当然还有对应次序的数据库文件以便查找。

在 Swift 中使用 C 的函数,还是挺有难度的。

首先你要有一个类型为不可表达指针类型的变量来存哈希表对象:

在初始化器里,我们来用 c 函数加载哈希表:

这样哈希表就加载成功了。

假定我们要查的值是一个 UInt32  的数字编码,那么我们需要先把它转为 cmph 函数所接受的 char*  指针,那么可以借助 NSString  来实现:

虽然 Swift 开发者文档中说 Swift 的 String 自动映射了 NSString 的方法,但显然,它并没有。

这样id变量就是一个Int类型的坐标了,返回值的类型 Swift 编译器自动帮你映射了。

总结

cmph 的原理很复杂,但这并不影响我们使用它。值得一提的是,它使用 LGPL 授权,也就是说你可以自由地使用它。

使用 Swift 可以完美地桥接 C 语言,但由于 Swift 本身并不鼓励开发者这么做导致一堆“unsafe”看着有种惊心动魄的感觉。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注