According to the man pages on my machine, search.h (containing hcreate and co.) goes back to System V Interface Description, and is described in POSIX 1003.1-2001.

So they should be pretty widely available.