GPERF：自动构建高效完美哈希函数的C++工具

179 浏览量更新于2024-08-25 收藏 128KB PDF 举报

GPERF是一种专为生成完美哈希函数设计的免费开源工具，由Douglas C. Schmidt开发，其电子邮件地址为schmidt@cs.wustl.edu，网页链接为http://www.cs.wustl.edu/~schmidt/。该工具隶属于华盛顿大学计算机科学系，位于圣路易斯63130。GPERF的主要作用是简化构建高效静态搜索集（一种抽象数据类型，包含初始化、插入和检索操作）的工作，这类应用常见于系统软件中，如编译器、解释器的保留字、汇编指令、壳命令以及CORBA IDL编译器中的关键词。静态搜索集的核心在于关键字识别，这些关键字只在创建时插入一次，通常在编译阶段完成。GPERF作为一个完美的哈希函数生成器，它的核心功能是自动从用户提供的关键词列表中构造出一个既能确保快速查找又能节省空间的哈希函数。相比于手动编写，GPERF的出现减少了重复劳动，使得开发人员能够专注于其他核心业务逻辑。完美哈希函数是一种特殊的哈希函数，它具备以下特性： 1. **冲突解决**：对于任何输入，哈希函数都应返回唯一的输出，即不存在哈希冲突，这使得查找、插入和删除操作的时间复杂度达到常数级别。 2. **空间效率**：由于没有冲突，可以避免额外的数据结构来处理冲突，从而节省存储空间。 3. **预计算**：在构建时，所有的哈希表和冲突处理已经完成，无需在运行时进行动态调整。 GPERF的工作流程涉及以下几个步骤： 1. 用户提供一个包含关键词的文本文件，这些词按特定格式排列。 2. GPERF解析这个输入文件，分析关键字，并确定合适的哈希函数模板。 3. 通过一系列算法，如除留余数法或拉链法，自动生成优化过的哈希函数实现。 4. 生成的代码可以被直接集成到目标项目中，作为关键字查找的高效工具。 GPERF是编程工具箱中一个实用且高效的组件，特别适合在需要频繁查找关键字的场景下使用，如编程语言解析、编译器优化等。它的出现极大地提高了开发者的工作效率，降低了构建高效搜索集的复杂性。

An optional user-supplied struct declaration may be

placed at the end of the declaration section, just before the %%

separator. This feature enables “typed attribute” initialization.

For example, in Figure 1 struct months is deﬁned to have

four ﬁelds that correspond to the initializer values given for the

month names and their respective associated values, e.g.:

struct months {

char *name;

int number;

int days;

int leap_days;

};

Lines containing keywords and associated attributes appear

in the keywords and optional attributes section of the keyﬁle.

The ﬁrst ﬁeld of each line always contains the keyword itself,

left-justiﬁed against the ﬁrst column and without surround-

ing quotation marks. Additional attribute ﬁelds can follow

the keyword. Attributes are separated from the keyword and

from each other by ﬁeld separators, and they continue up to the

“end-of-line marker,” which is the newline character (’\n’) by

default.

Attribute ﬁeld values are used to initialize components of

the user-supplied struct appearing at the end of the decla-

ration section, e.g.:

january, 1, 31, 31

february, 2, 28, 29

march, 3, 31, 31

...

As with lex and yacc, it is legal to omit the initial dec-

laration section entirely. In this case, the keyﬁle begins with

the ﬁrst non-comment line (lines beginning with a "#" char-

acter are treated as comments and ignored). This format style

is useful for building keyword set recognizers that possess no

associated attributes. For example, a perfect hash function for

frequently occurring English words can efﬁciently ﬁlter out

uninformative words, such as “the,” “as,” and “this,” from con-

sideration in a key-word-in-context indexing application [5].

Again, as with lex and yacc, all text in the optional third

auxiliary code section is included verbatim into the generated

output ﬁle, starting immediately after the ﬁnal %% and extend-

ing to the end of the keyﬁle. It is the user’s responsibility to

ensure that the inserted code is valid C or C++. In the Fig-

ure 1 example, this auxiliary code provides a test driver that is

conditionally included if the DEBUG symbol is enabled when

compiling the generated C or C++ code.

4 Design and Implementation Strate-

gies

Many articles describe perfect hashing [10, 7, 11, 12] and min-

imal perfect hashing algorithms [8, 13, 6, 14, 15]. Few articles,

however, describe the design and implementation of a general-

purpose perfect hashing generator tool in detail. This section

describes the data structures, algorithms, output format, and

reusable components in gperf.

gperf is written in



4,000 lines of C++ source code. C++

was chosen as the implementation language since it supports

data abstraction better than C, while maintaining C’s efﬁciency

and expressiveness [16].

gperf’s three main phases for generating a perfect or near-

perfect hash function are shown in Figure 2: Figure 6 illus-

trates gperf’s overall program structure. and described be-

january

february

...

december

KEYFILE

Asso_Values

Key_List

GPERF

int hash

(const char *str,

unsigned int len)

{

// ...

/C++ CODE

Figure 2: gperf’s Processing Phases

low:

1. Process command-line options, read keywords and at-

tributes (the input format is described in Section 3), and

initialize internal objects (described in Section 4.1).

2. Perform a non-backtracking, heuristically guided search

for a perfect hash function(described in Section 4.2.1 and

Section 4.2.2).

3. Generate formatted C or C++ code according to the

command-lineoptions (output format is described in Sec-

tion 4.3).

The following section outlines gperf’s perfect hash func-

tion generation algorithms and internal objects, examines its

generated source code output, describes several reusable class

components, and discusses the program’s current limitations

and future enhancements.

4.1 Internal Objects

gperf’s implementation centers around two internal objects:

the keyword signatures list (Key List)andtheassociated

values array (asso values), both of which are described

below.

4.1.1 The Keyword Signatures List

Every user-speciﬁed keyword and its attributes are read from

the keyﬁle and stored in a node on a linked list, called

Key List. gperf only considers a subset of each key-

words’ characters while it searches for a perfect hash function.

The subset is called the “keyword signature,” or keysig.

剩余12页未读，继续阅读

weixin_38677306

粉丝: 4
资源: 916

GPERF：自动构建高效完美哈希函数的C++工具

gperf-3.0.3.tar.gz

gperf-3.1-5.el8.x86_64.rpm

gperf-3.04

gperf-suggestion

gperf-3.0.1-7.2.2.x86_64

gperf-3.0.2-3.0.3.patch.gz库文件

gperf-3.0.4-8.el7.x86_64.rpm

gperf-2.7.2.tar.gz

gperf-3.0.3-9.1.el6.x86-64 包含gperf、libevent、gearmand、php、gearman

gperf-sample:使用makefile的gperf用法的简单示例

最新资源