| 位图检索知识点 | 上一个知识点 下一个知识点 |
| 本节概述 本节知识点 本节总结 |
二、位图检索
要判断某一元素是否在数组中，即集合中的“IN”运算，是在一组记录中检索关键码的一种特殊情况。本书所讨论的所有检索方法都可以完成这个任务。
在关键码值范围有限的情况下，可以采用一种简单的技术，这就是存储一个位数组(bit arrary)，为每一个可能的元素分配一个比特位位置。如果元素确实包含在实际集合中，就把它对应的位设置为1；如果元素不包含在集合中，就把它对应的位设置为0。Pascal语言能够直接支持集合类型，其集合类型就是用一个位数组来实现的。
例如对于字符型集合为（小写字母['a'..'z']），而集合型变量chset = ['a','c','h','i',j','m','n',t','v','w,'y']，那么对应于变量chset的位数组为：
这种表示方法很省空间，而且对于“属于”、“并”、“交”和“差”（“IN”、“+”、“*”和“-”）操作十分方便。集合比数组的操作更加便捷。例如，对于数组的插入和删除，都有大量的数据移动；而集合类型的“并”、“交”和“差”运算只需要在修改相应的比特位标记。要确定某个元素是否在集合中，只需要直接检查对应的位标志。这种表示方法称为位向量( bit vector )或者位图( bitmap )。
如果集合大小在计算机的一个字长范围内，而且高级语言支持按位操作，就可以通过逻辑的位操作而完成集合的并、交、差运算。例如，在C++语言中，集合A和B的并运算就是“A | B”（按位或），集合的交运算就是“A & B”（按位与），集合A与B的差运算可以使用表达式“A &~ B”( ~是非运算的符号)实现。例如，如果要计算数字0到数字15之间奇素数集合，只需要计算表达式
0011010100010100 & 0101010101010101
得到结果“0001010100010100”，表示0到15之间的奇素数集合为{3，5，7，11，13}。