5
$\begingroup$

Is there efficient algorithm to encode keys in hash function with provided collisions?

By efficient I mean with low-ish runtime of lookup operation (taking constants into account) and realistic time of finding such function.
Keys are floating point values - I can compare them for equality as they are raw, unprocessed. Equality holds, and there are no round-offs.
If there is better chance for algorithm on integers - I am still interested.
I did not included specific scheme for building perfect hash - it might be the wrong way or different scheme supports such change.

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, 5.5, 24\}, \{7, 20\}\}$ and the set $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, $Y$ contains values that collide with nothing.
$Y$ is about 85-95% of input, $X$ occupies the rest.
If for example $X$ has values 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 hashtable there will be at least 458 buckets (this 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 the input.
Order of the values from input does not matter, $h(x)$ does not need to preserve order, does not need to be monotone.

TLDR; Below are previous attempts, some background etc.


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 (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 real time.
There are constraints on memory, query time, and I have 10^7 elements, which need to be calculated and then augmented with some value.
The data seems quite random to me (and to DieHard statistical tests also).


Solution attempts

So I thougth about hash function, calculate everything in advance, and make queries easy.
The problem is the normal hashtable does not fit very well because of slowdowns on collisions and when it is perfect it is too big, but collisions 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 only 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 list. The solution is working (on smaller inputs, on real-like I got only two results so far, on relaxed collisions, due to search time).
The probability that I will find perfect function randomly or semirandomly in 10^7 elements is too low to consider.
So I thought about some modified solution, like taking several hash functions, adjusting them, finding similarities - everything is doable on very small sets, then time needed to execute drops like avalanche.
There are addidional test I did, like with Pearson hash, the idea is very cool, but the data size is bigger than 10^5, and values are floats, so it complicates a bit.


Workplace settings

The size of the set is about 10^7 elements, hash table with function $h(x)$ is flat array, that does not support collision resolution (from my perspective, the values from sets $X_i$ transform into the same output, so 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.
$\endgroup$
  • 4
    $\begingroup$ This smells like an XY question. Why exactly do you require such a bizarre hash function? $\endgroup$ – vonbrand Feb 15 '16 at 17:50
  • 2
    $\begingroup$ The comment on your bounty, "two functions merged into one are still two functions" is not one I think most computer scientists would agree with. For instance, absolute value isn't two functions just because it can be written as a piecewise function, cosine isn't an infinite number of functions just because it has a Taylor series, and, most relevant here, I believe all (or almost all) perfect hash functions with a range size linear in the size of the domain are built up of two functions, but the literature still calls them single functions. In short, @Yuval Filmus's answer is correct already. $\endgroup$ – jbapple Feb 22 '16 at 14:00
  • 1
    $\begingroup$ EvilJS, how do you know "there is better function that works the same, but in one step"? Are you sure that the two step procedure isn't the best that can be done? What makes you so sure? What evidence of that can you give to the rest of us? $\endgroup$ – jbapple Feb 22 '16 at 17:04
7
+50
$\begingroup$

The easiest way is to construct a static hash table $T$ containing all the collisions, in the following form: for each set of keys $S$ which are supposed to map to the same value, single out some $x \in S$, and put all other $y \in S$ in the table with an entry stating "$x$".

Now take a good hash function $h$, and construct a new one as follows:

  • On input $x$, check whether $x \in T$.
  • If $x \notin T$, return $h(x)$.
  • If $x \in T$, return $h(T[x])$.

If $h$ were a uniformly random function, then this would result in a uniformly random function conditioned on your collisions.

There are some optimizations possible here:

  • The hash function used to access $T$ can be weak.
  • The table $T$ might be too large to fit in the cache, so accessing $T$ might be slow. We can add a Bloom filter that does fit in cache to ameliorate this.
$\endgroup$
  • $\begingroup$ The best answer from the begining, but I counted on some improvements, further hints. Thank you. $\endgroup$ – Evil Feb 29 '16 at 16:35
  • $\begingroup$ Is there a typo there? if x is in T it should return h(x) and otherwise it should return h(T[x]) $\endgroup$ – Masood_mj Jul 11 '18 at 23:16
  • $\begingroup$ @Masood_mj If $x$ isn't in $T$, what is $T[x]$? $\endgroup$ – Yuval Filmus Jul 12 '18 at 4:33
  • $\begingroup$ Sorry for confusion, I get it now. Thanks $\endgroup$ – Masood_mj Jul 12 '18 at 17:25
2
$\begingroup$

Check perfect hash functions, particularly the first reference given in that Wikipedia page. The general idea (in the case of strings) is to select some character positions that combined give no collisions.

$\endgroup$
  • $\begingroup$ @EvilJS, yes, it will take a lot of time to find such a custom-tailored hash function. Just like finding a perfect one isn't cheap, and so should only be used where performance is absolutely critical. $\endgroup$ – vonbrand Feb 15 '16 at 17:49
  • $\begingroup$ It is not cheap but doable - it is crucial to overcome this bottleneck. Random walk to find such degrades in time fastly. I know this process will be slow, but with some scheme (instead if rejections) I will know that I wait for output, and I will get one. $\endgroup$ – Evil Feb 17 '16 at 18:52
  • 1
    $\begingroup$ We do want some collisions, though. $\endgroup$ – Yuval Filmus Feb 22 '16 at 16:00
-1
$\begingroup$

I would try to find a Pearson 256-bit lookup table. My code to generate C code for such a table with your desired properties is at https://github.com/rurban/Perfect-Hash/blob/master/lib/Perfect/Hash/Pearson.pm as described in https://stackoverflow.com/questions/1396697/determining-perfect-hash-lookup-table-for-pearson-hash

char* pearson(char* name, char* lookup)
{
    char index = '\0';
    while(*name)
    {
        index = lookup[index ^ *name];
        name++;
    }
    return index;
}

You can tune the cost function to check for your exact wanted collisions. Pearson tables are usually faster even with a few collisions than highly tuned perfect hash tables without any collision because of the zero constant factors, and the lookup table fits nicely into the cache.

However my code is only in slow perl and I just try some random lookup tables until the overall cost function is minimized and some timeout. It would need quite some CPU time to find it. I would write the search function in C.

$\endgroup$
  • $\begingroup$ Ad Luck: You need to do an exhaustive search over all permutations of 256 entries. Either there exists is a combinations for your wanted collisions or not. $\endgroup$ – rurban Feb 22 '16 at 20:36
  • $\begingroup$ Ad cost: Normal Perfect Hashes (PH) have a too high constant factor: blogs.perl.org/users/rurban/2014/08/… A normal PH table lookup requires 1.5x hash calculations and 2 collision-free lookups in an array. A pearson lookup requires no hash calculation, just n lookups in a table which fits into the cache and 1 lookup with possible collisions in an array. Hashing and esp. the final lookup dominates the cost, a good pearson table with only a few collisions is faster for <100.000 keys than a perfect hash. A tuned static tree search is also faster. $\endgroup$ – rurban Feb 22 '16 at 20:40
  • $\begingroup$ I like your answer as it tells about lookup speed. I have upvoted it, but since the working set is bigger and the main problem (how to find collisions) remains untouched - this is not full yet. I have edited question. Also there is small probability that there is no Pearson hash for given length, un fact probability of such event degrades with number of elements, but still - it might give no answer and there is no fallback plan. And you are perfectly right that Pearson hash has small constant of lookup, but this increases with length, so for big set there are no obvious boosts. $\endgroup$ – Evil Feb 27 '16 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.