Is there efficient algorithm to encode keys in hash function with provided collisions?
Is there efficient algorithm to encode keys in hash function with provided collisions?
ByBy efficient I mean with lowestlow-ish runtime of lookup operation (taking constants into account) and deterministicrealistic time of finding such function.
Let $h(x)$ be hash function (the one to be found)
$X$ be set of sets of float values that $\forall x \in X_i, h(x) = c_i$
$\forall X_i, |X_i| \in [2, 20]$
Let $Y$ be set of float values that there are no collisions (it does not collide with any $X_i$)
For example, I have set $x = {1, 4, 5.5, 7, 20, 24}$$X = \{\{1, 5.5, 24\}, \{7, 20\}\}$ and during the buildingset (static table) I would like to put$Y = \{4, 25, 31.2, ...\}$
$h(1) = h(5.5) = h(24) = c_0$
$h(7) = h(20) = c_1$
$h(4) = c_2$
$h(25) = c_3$
$h(31.2) = c_4$
$c_i = c_j \iff i = j$
$X$ set containts colliding tuples, ${1, 5.5, 24}$ to have the same bucket$Y$ contains values that collide with nothing.
$Y$ is about 85-95% of input, ${7, 20}$ to be in another bucket$X$ occupies the rest.
The entries can be treated as unique
If for example (multiple$X$ has values will be stored as one)in tuples of multiplicities {3, 5, 2, 2, 20, 14, 3}, this are 49 values, but 7 distinct buckets and Y has 451 elements, these are 451 distinct buckets.
In the hash shouldhashtable there will be perfectat least 458 buckets (apart of collisionsthis is perfect, and preffered), but might be a bit bigger up to 1%.
All possible inputs are given, $h(x)$ will never execute for value that was not in advance)the input.
Order of the values from input does not matter, function$h(x)$ does not need to preserve order, does not need to be monotone.
This is about creating one hash function. ###TLDR; Below are previous attempts, some background etc.###
The most important part###Background###
In the initial phase I gather data from the device, this phase ends when for given settings I have collected all possible outputs.
This data is collected as floating point numbers. I calculate outputs based on what I get and create mapping of all values to calculated results efficient(this are not continous functions, not piecewise, distinct values with collisions, which are giving the same results).
The callibration phase gives me value to add to calculated results from initial phase.
In the main part I gather data from device, this time with feedback where I need recalculated values in terms of lookupreal time.
There are constraints on memory, query time, and less importantI have 10^7 elements, but still crucialwhich need to be calculated and then augmented with some point - creating such function should have low runtimevalue.
The data seems quite random to me (not exponential, smaller is better, but this is secondary concernand to DieHard statistical tests also).
This part###Solution attempts###
So I thougth about hash function, calculate everything in advance, and make queries easy.
The problem is to show settingsthe normal hashtable does not fit very well because of slowdowns on collisions and when it is perfect it is too big, but itcollisions if happen on data that gives the same results - fits quite well.
There are a lots of perfect hashing techniques, or methods of collision resolution, but I could not find any materials about picking collisions on my own (this is twice perfect solution, not the partonly I get rid of collisions but also data redundancy vanishes).
So I took CMPH library, and added rejections to collisions to reject if collision is not on the questionlist. The solution is working (how to embedon smaller inputs, on real-like I got only two results so far, on relaxed collisions into hash function, due to search time).
The working setprobability that I will have at least $10^7$find perfect function randomly or semirandomly in 10^7 elements is too low to consider.
So I thought about some modified solution, and bucket saturation will be in range [1like taking several hash functions, adjusting them, finding similarities -20] everything is doable on very small sets, then time needed to execute drops like avalanche.
The tableThere are addidional test I did, like with Pearson hash, the idea is static so allvery cool, but the data size is bigger than 10^5, and values are known in advancefloats, so it complicates a bit.
This solution###Workplace settings###
The size of the set is about 10^7 elements, hash table with double hashingfunction $h(x)$ is not the oneflat array, that I asked aboutdoes not support collision resolution (is not efficientfrom my perspective, and separates problem to two subproblems without the core questionvalues from sets $X_i$ transform into the same output, but of course gives working solutionso are mapped into one element).
###Easier, discarded solutions###
- The most obvious attempt is to create minimal perfect static hash function from all elements. This solution is discarded because of memory constraints - it does not fit into memory in one piece, redundancy of data.
- Each set $X_i$ gets own perfect hash function, and upon query I try $Y$ set as the most probable, and then every set $X_i$ via own hash function until I find the value. (I thought that Yuval Filmus answer is very similar to that approach), which might look a bit like Bloom filter, but the values queried via $h(x)$ are always in the table, and maintaining about 10^6 values more hashes is too slow.
###Disaster solutions###
- Trees - Many sorts of trees - too slow, way too slow.
- Mixture of hash and tree, Bloomtree(??). I never hoped that it would work but checked it anyway. Of course too slow.
