First I wanted to say thanks for creating this new implementation of borghash in this new dedicated repo!

After reading through some of the code I had a few ideas how the memory consumption could be reduced further. Maybe some of this is already implemented and I missed it, but some of it should be new:

1:
The reallocs in _resize_kv could probably be optimized. That way the peak memory consumption could be reduced which I think would be especially nice for systems facing memory pressure (or maybe even worse address space pressure as for example on 32bit systems). The most compatible idea would probably be the following:

Allocate the memory using mmap. Either by using /dev/zero as described here or by mapping the actual stored file on the disk as described here (probably more complicated/error-prone). Depending on how much address space is available, you could just reserve all the space you could ever need (UINT32_MAX * self.ksize * sizeof(uint8_t)). This would get rid of the need for the resize/realloc completely. In case you do not have that much address space available (for example on 32bit systems), you could do something else to replace realloc: still use mmap, but copy from the old to the new table in blocks. Copy 10MB from the old table to the new table and munmap it in the old table.
I just realize there are some tests. Maybe I could implement this myself! I like having the hash table in a separate repo so this should be a lot easier/less scary than before!

2:
Do I understand correctly that, together with the changes from borgstore, borghash will only need to be used when writing to the repo? I imagine the objects/chunks on disk can be found just by their ID which will be used for anything that is stored on disk. That way when just reading the repo, borghash would not need to be used/loaded at all.
Otherwise there still could be some readonly optimizations:

• implement a readonly mode that only loads what is needed. So maybe the hashtable is unneeded or only the values are needed but the keys are not?
• only allocate exactly what is needed and do not keep any additional room for growth.

3:
Some more thoughts on borgstore, that are only relevant if the IDs from borghash are used to locate the objects/chunks on disk:
3.1 The borgstore documentation mentions that a random distribution of the keys is assumed, which would not be useful for this use case. This assumption is now outdated, right?
3.2 I like using custom chunker params for smaller chunk sizes on my repos. Benchmarks for my use cases showed a smaller repo size that way (Although later I realized that this increases memory consumption...). For that reason I dislike the change that each chunk gets its own file.
I'd rather prefer if for example 256 chunks/objects would be stored in a single file. This would reduce file system overhead as well as random I/O when writing and especially reading. Even more so if the files would not be stored in the order they were created (which could also be caused by copying them over to a new file system). Combining these writes into one file for multiple chunks should be a lot easier when having consecutive IDs. Although this would obviously make deletion more complicated. If my assumptions that files are stored by their consecutive IDs, I will create an issue with more detailed ideas over at the borgstore repo.

Thanks for reading all of this :-)