Uthash – C macros for hash tables and more

Re:Uthash – C macros for hash tables and more by marginalia_nu on Saturday March 26, 2022 @07:59AM (#30811091)

I'm using it for the lexicon in my search engine.

I basically need a mapping from arbitrary short strings to unique integer identifiers, with a cardinality in the billions. Too much to keep in memory, most db solutions keel over as well.

[ Parent | on HN ]

Re:Uthash – C macros for hash tables and more by rurban on Saturday March 26, 2022 @01:02PM (#30813458)

for this I would use CHM, ordered minimal perfect hashes with external mmap'ed keys. still constant lookup, just the position needs to be stored in the value also.

[ Parent | on HN ]

Re:Uthash – C macros for hash tables and more by marginalia_nu on Saturday March 26, 2022 @03:35PM (#30814664)

Problem is I don't know the items beforehand, instead I need to build the hash as I encounter new pages. I don't know any way of reconcile that with a minimal perfect hash.

[ Parent | on HN ]

Re:Uthash – C macros for hash tables and more by rurban on Saturday March 26, 2022 @04:07PM (#30814922)

ok, with trillions keys creating a CHM MPH is risky, and needs a few secs. then your external hash is good enough.

[ Parent | on HN ]