HTML rendering created 2025-09-06 byMichael Kerrisk, author ofThe Linux Programming Interface. For details of in-depthLinux/UNIX system programming training courses that I teach, lookhere. Hosting byjambit GmbH. |  |
NAME |LIBRARY |SYNOPSIS |DESCRIPTION |RETURN VALUE |ERRORS |ATTRIBUTES |STANDARDS |HISTORY |NOTES |BUGS |EXAMPLES |SEE ALSO |COLOPHON | |
hsearch(3) Library Functions Manualhsearch(3)hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - hash table management
Standard C library (libc,-lc)
#include <search.h>int hcreate(size_tnel);void hdestroy(void);ENTRY *hsearch(ENTRYitem, ACTIONaction);#define _GNU_SOURCE/* See feature_test_macros(7) */#include <search.h>int hcreate_r(size_tnel, struct hsearch_data *htab);void hdestroy_r(struct hsearch_data *htab);int hsearch_r(ENTRYitem, ACTIONaction, ENTRY **retval,struct hsearch_data *htab);
The three functionshcreate(),hsearch(), andhdestroy() allow the caller to create and manage a hash search table containing entries consisting of a key (a string) and associated data. Using these functions, only one hash table can be used at a time. The three functionshcreate_r(),hsearch_r(),hdestroy_r() are reentrant versions that allow a program to use more than one hash search table at the same time. The last argument,htab, points to a structure that describes the table on which the function is to operate. The programmer should treat this structure as opaque (i.e., do not attempt to directly access or modify the fields in this structure). First a hash table must be created usinghcreate(). The argumentnel specifies the maximum number of entries in the table. (This maximum cannot be changed later, so choose it wisely.) The implementation may adjust this value upward to improve the performance of the resulting hash table. Thehcreate_r() function performs the same task ashcreate(), but for the table described by the structure*htab. The structure pointed to byhtab must be zeroed before the first call tohcreate_r(). The functionhdestroy() frees the memory occupied by the hash table that was created byhcreate(). After callinghdestroy(), a new hash table can be created usinghcreate(). Thehdestroy_r() function performs the analogous task for a hash table described by*htab, which was previously created usinghcreate_r(). Thehsearch() function searches the hash table for an item with the same key asitem (where "the same" is determined usingstrcmp(3)), and if successful returns a pointer to it. The argumentitem is of typeENTRY, which is defined in<search.h> as follows: typedef struct entry { char *key; void *data; } ENTRY; The fieldkey points to a null-terminated string which is the search key. The fielddata points to data that is associated with that key. The argumentaction determines whathsearch() does after an unsuccessful search. This argument must either have the valueENTER, meaning insert a copy ofitem (and return a pointer to the new hash table entry as the function result), or the valueFIND, meaning that NULL should be returned. (Ifaction isFIND, thendata is ignored.) Thehsearch_r() function is likehsearch() but operates on the hash table described by*htab. Thehsearch_r() function differs fromhsearch() in that a pointer to the found item is returned in*retval, rather than as the function result.hcreate() andhcreate_r() return nonzero on success. They return 0 on error, witherrno set to indicate the error. On success,hsearch() returns a pointer to an entry in the hash table.hsearch() returns NULL on error, that is, ifaction isENTERand the hash table is full, oraction isFINDanditem cannot be found in the hash table.hsearch_r() returns nonzero on success, and 0 on error. In the event of an error, these two functions seterrno to indicate the error.
hcreate_r() andhdestroy_r() can fail for the following reasons:EINVALhtab is NULL.hsearch() andhsearch_r() can fail for the following reasons:ENOMEMaction wasENTER,key was not found in the table, and there was no room in the table to add a new entry.ESRCHaction wasFIND, andkey was not found in the table. POSIX.1 specifies only theENOMEMerror.
For an explanation of the terms used in this section, seeattributes(7). ┌───────────────────────┬───────────────┬────────────────────────┐ │Interface│Attribute│Value│ ├───────────────────────┼───────────────┼────────────────────────┤ │hcreate(),hsearch(), │ Thread safety │ MT-Unsafe race:hsearch │ │hdestroy() │ │ │ ├───────────────────────┼───────────────┼────────────────────────┤ │hcreate_r(), │ Thread safety │ MT-Safe race:htab │ │hsearch_r(), │ │ │ │hdestroy_r() │ │ │ └───────────────────────┴───────────────┴────────────────────────┘
hcreate()hsearch()hdestroy() POSIX.1-2008.hcreate_r()hsearch_r()hdestroy_r() GNU.
hcreate()hsearch()hdestroy() SVr4, POSIX.1-2001.hcreate_r()hsearch_r()hdestroy_r() GNU.
Hash table implementations are usually more efficient when the table contains enough free space to minimize collisions. Typically, this means thatnel should be at least 25% larger than the maximum number of elements that the caller expects to store in the table. Thehdestroy() andhdestroy_r() functions do not free the buffers pointed to by thekey anddata elements of the hash table entries. (It can't do this because it doesn't know whether these buffers were allocated dynamically.) If these buffers need to be freed (perhaps because the program is repeatedly creating and destroying hash tables, rather than creating a single table whose lifetime matches that of the program), then the program must maintain bookkeeping data structures that allow it to free them.
SVr4 and POSIX.1-2001 specify thataction is significant only for unsuccessful searches, so that anENTERshould not do anything for a successful search. In libc and glibc (before glibc 2.3), the implementation violates the specification, updating thedata for the givenkey in this case. Individual hash table entries can be added, but not deleted.
The following program inserts 24 items into a hash table, then prints some of them. #include <search.h> #include <stdio.h> #include <stdlib.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; ENTRY *ep; hcreate(30); for (size_t 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 (size_t 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); }bsearch(3),lsearch(3),malloc(3),tsearch(3)
This page is part of theman-pages (Linux kernel and C library user-space interface documentation) project. Information about the project can be found at ⟨https://www.kernel.org/doc/man-pages/⟩. If you have a bug report for this manual page, see ⟨https://git.kernel.org/pub/scm/docs/man-pages/man-pages.git/tree/CONTRIBUTING⟩. This page was obtained from the tarball man-pages-6.15.tar.gz fetched from ⟨https://mirrors.edge.kernel.org/pub/linux/docs/man-pages/⟩ on 2025-08-11. If you discover any rendering problems in this HTML version of the page, or you believe there is a better or more up- to-date source for the page, or you have corrections or improvements to the information in this COLOPHON (which isnot part of the original manual page), send a mail to man-pages@man7.orgLinux man-pages 6.15 2025-05-17hsearch(3)Pages that refer to this page:bsearch(3), lsearch(3), tsearch(3)
HTML rendering created 2025-09-06 byMichael Kerrisk, author ofThe Linux Programming Interface. For details of in-depthLinux/UNIX system programming training courses that I teach, lookhere. Hosting byjambit GmbH. | |