名称

hcreate，hdestroy，hsearch，hcreate_r，hdestroy_r，hsearch_r-哈希表管理

说明

三种函数hcreate()，hsearch()和hdestroy()允许调用者创建和管理一个哈希搜索表，该表包含由键(字符串)和相关数据组成的条目。使用这些功能，一次只能使用一个哈希表。

三个函数hcreate_r()，hsearch_r()和hdestroy_r()是可重入版本，允许程序同时使用多个哈希搜索表。最后一个参数htab指向描述该函数将在其上运行的表的结构。程序员应将此结构视为不透明(即不要尝试直接访问或修改此结构中的字段)。

首先，必须使用hcreate()创建一个哈希表。参数nel指定表中的最大条目数。 (此最大值不能在以后更改，因此请明智地选择。)实现可以向上调整此值以提高所得哈希表的性能。

hcreate_r()函数执行与hcreate()相同的任务，但对于由* htab结构描述的表。在第一次调用hcreate_r()之前，必须将htab指向的结构清零。

函数hdestroy()释放由hcreate()创建的哈希表占用的内存。调用hdestroy()之后，可以使用hcreate()创建一个新的哈希表。 hdestroy_r()函数对* htab描述的哈希表执行类似的任务，该哈希表先前是使用hcreate_r()创建的。

hsearch()函数在哈希表中搜索与该项目具有相同键(使用strcmp(3)确定"相同")的项目，如果成功，则返回指向该项目的指针。

参数项的类型为ENTRY，其定义如下：

typedef struct entry {
    char *key;
    void *data;
} ENTRY;

字段关键字指向一个以空值结尾的字符串，它是搜索关键字。字段数据指向与该键关联的数据。

参数操作确定搜索不成功后hsearch()的操作。此参数必须具有值ENTER(表示插入项的副本(并返回指向新哈希表条目的指针作为函数结果))或值FIND(表示应返回NULL)。 (如果操作为FIND，则将忽略数据。)

hsearch_r()函数类似于hsearch()，但对* htab描述的哈希表起作用。 hsearch_r()函数与hsearch()的不同之处在于，在* retval中而不是函数结果中返回指向找到的项的指针。

Linux程序员手册 第3部分
更新日期： 2020-06-09

属性

有关本节中使用的术语的说明，请参见attribute(7)。

示例

下面的程序将24个项目插入哈希表，然后打印其中的一些。

#include <stdio.h>
#include <stdlib.h>
#include <search.h>

static char *data[] = { "alpha", "bravo", "charlie", "delta",
     "echo", "foxtrot", "golf", "hotel", "india", "juliet",
     "kilo", "lima", "mike", "november", "oscar", "papa",
     "quebec", "romeo", "sierra", "tango", "uniform",
     "victor", "whisky", "x-ray", "yankee", "zulu"
};

int
main(void)
{
    ENTRY e, *ep;
    int i;

    hcreate(30);

    for (i = 0; i < 24; i++) {
        e.key = data[i];
        /* data is just an integer, instead of a
           pointer to something */
        e.data = (void *) i;
        ep = hsearch(e, ENTER);
        /* there should be no failures */
        if (ep == NULL) {
            fprintf(stderr, "entry failed\n");
            exit(EXIT_FAILURE);
        }
    }

    for (i = 22; i < 26; i++) {
        /* print two entries from the table, and
           show that two are not in the table */
        e.key = data[i];
        ep = hsearch(e, FIND);
        printf("%9.9s -> %9.9s:%d\n", e.key,
               ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);
    }
    hdestroy();
    exit(EXIT_SUCCESS);
}

出版信息

这个页面是Linux手册页项目5.08版的一部分。有关项目的说明、有关报告错误的信息以及此页面的最新版本，请访问https://www.kernel.org/doc/man-pages/。

遵循规范

函数hcreate()，hsearch()和hdestroy()来自SVr4，并在POSIX.1-2001和POSIX.1-2008中进行了描述。

函数hcreate_r()，hsearch_r()和hdestroy_r()是GNU扩展。

备注

当表包含足够的可用空间以最小化冲突时，哈希表的实现通常会更高效。通常，这意味着nel应至少比调用者希望在表中存储的最大元素数大25％。

hdestroy()和hdestroy_r()函数不会释放哈希表条目的键和数据元素所指向的缓冲区。 (它无法执行此操作，因为它不知道是否动态分配了这些缓冲区。)是否需要释放这些缓冲区(可能是因为程序反复创建和销毁哈希表，而不是创建其寿命匹配的单个表)程序)，则该程序必须维护允许其释放它们的簿记数据结构。

另外参见

bsearch(3)，lsearch(3)，malloc(3)，tsearch(3)

BUGS

SVr4和POSIX.1-2001指定该操作仅对不成功的搜索有意义，因此ENTER不应对成功的搜索执行任何操作。在libc和glibc(2.3版之前)中，实现违反规范，在这种情况下，将更新给定键的数据。

可以添加单个哈希表条目，但不能删除。

错误说明

hcreate_r()和hdestroy_r()可能由于以下原因而失败：

EINVAL

htab为NULL。

hsearch()和hsearch_r()可能由于以下原因而失败：

ENOMEM

操作是ENTER，在表中找不到键，并且表中没有空间添加新条目。

ESRCH

操作是FIND，并且在表中找不到键。

POSIX.1仅指定ENOMEM错误。

返回值

hcreate()和hcreate_r()成功返回非零值。错误时返回0，并设置errno以指示错误原因。

成功后，hsearch()将返回一个指向哈希表中条目的指针。如果出现错误，则hsearch()返回NULL，即操作为ENTER且哈希表已满，或者操作为FIND且在哈希表中找不到项目。 hsearch_r()成功返回非零，错误返回0。在发生错误的情况下，这两个函数将errno设置为指示错误原因。

语法

#include <search.h>

int hcreate(size_t nel);

ENTRY *hsearch(ENTRY item, ACTION action);

void hdestroy(void);

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <search.h>

int hcreate_r(size_t nel, struct hsearch_data *htab);

int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
              struct hsearch_data *htab);

void hdestroy_r(struct hsearch_data *htab);