Histogram Hash

I have the impression that hashing as it is usually practiced requires storing both a hash data structure and the original data.

It occurred to me that it would be possible to use histograms to transform a sorted list of data items into a structure that was smaller than the original data, but also supported hashing, so that you would only need the hash data, You could then remove the original data, and re-create it from the hash data if required.

If this hasn't already been done, then here it is. If it has already been done, perhaps this code could still be of help to someone.

I have two programs. One processes a list of 32 bit integers, and the other does a list of variable length strings containing only the letters allowed in C symbols.

Here is the annotated output of the program creating a hash table for 50 million 32 bit integers. Source code for that program is at:

http://mcky.net/bin/hsh/hsh.tar.gz

http://mcky.net/bin/hsh/hsh.zip

The code was developed on a Linux 64 bit system.

Note that data compression could be improved if we only want to know if the accessed data was in the original data set, but we don't care about where it was located.

The hash data is smaller than the original data. It would not be possible to just replace the original data with the hash data while bulding the hash data, but it probably woudn't be necessary to go with a completely double buffered solution. Some extra storage would be needed, but not two times the size of the data.

Here are the collated results for several runs of the integer code