-1
$\begingroup$

I have a a data set with 2598960 elements of of unsigned integers of (at most) 52-bit length. The data set has a property that exactly 5 bits set.

This is only 1 data sets – I have similar data sets of integers with exactly 6, 7 and 9 bits set.

Given this peculiar property of the data set, is there a way I can create a minimum perfect hash function other than the method proposed here, which I rejected as lookup requires 2 hashes and dealing with negative hash results by using an if statement?

I am not looking for a ranking/unranking solution. As that is dependent on the fact that all ranks be present, I am looking for a more general solution that can take advantage of the fact that only k bits are set.

Additionally if a non hashing solution is proposed, Performance should be similar to a hash table i.e. O(1)

$\endgroup$
  • 1
    $\begingroup$ Can you include the method you don't like, and explain what you don't like about it, and what would you prefer to see instead? Also, can you explain what you mean by perfect hash function? $\endgroup$ – Yuval Filmus May 31 '18 at 13:33
  • $\begingroup$ Do you mean 5 bits set per integer? What's wrong with a solution that requires 2 hashes and an if statement? Neither of those sounds like a serious problem. Almost all code will use if statements, and using 2 hashes doesn't sound like a problem. $\endgroup$ – D.W. May 31 '18 at 15:21
  • $\begingroup$ It's easy to enumerate the $52 \choose 5$ possibilities -- that is, map each possible value to its index in the enumeration -- but I don't believe you can do that without examining every bit, which I suspect wouldn't satisfy your unstated requirements. $\endgroup$ – rici May 31 '18 at 15:23
  • $\begingroup$ Are all of the integers distinct? If so, there are only ${52 \choose 5} = 2598960$ possible integers, so that means that your dataset contains every possible integer, and it's possible to store it in 0 bits. $\endgroup$ – D.W. May 31 '18 at 15:23
  • $\begingroup$ I’d be curious if you can beat just using the numbers unchanged as the hash code. $\endgroup$ – gnasher729 May 31 '18 at 16:46
2
$\begingroup$

The problem is trivial. You don't need a data structure to store this data set. There are only ${52 \choose 5}=2598960$ possible 52-bit integers with 5 bits set. You say that your data set contains 2598960 distinct 52-bit integers with 5 bits set. That means that every possible 52-bit integer with 5 bits set appears exactly once in your data set. Therefore, rather than using a fancy data structure to store the data set, don't store anything.

You can test whether a given integer is in the data set by simply testing whether it has 5 bits set or not. You can also enumerate all elements in the data set by enumerating all 52-bit integers with 5 bits set, which is straightforward to do. You don't need a hash function, or a data structure, or indeed to store anything at all.

Since this answer is trivial, I suspect you must actually be wondering about something else, but I can't quite understand what, from what you have written.

Perhaps you are wondering how to convert a 52-bit integer with 5 bits set into a number in the range 0..2598959, or vice versa. If so, look into ranking and unranking algorithms: see, e.g., https://oeis.org/wiki/Ranking_and_unranking_functions, https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/, https://en.wikipedia.org/wiki/Combinatorial_number_system. That's exactly what they do, and there are elegant and efficient algorithms for solving this problem. Then, you could store those numbers in sorted order, or store them with a bitvector (with $i$th bit in the bitvector indicates whether the number $i$ is present, i.e., whether the 52-bit integer with rank $i$ is present in your dataset).

In summary, let me outline the possible solutions and the extent to which they meet the stated requirements:

  • Use the FNV algorithm for perfect hashing. You have already rejected this as too slow.

  • Don't store any data structure. Just remember that every 52-bit integer with 5 bits set is in the dataset, and any time you want to enumerate the data set or test for presence in the dataset, reconstruct the data. This requires no storage and is very fast, and meets all of your stated requirements. However, it is not a general solution. It is specific to the fact that you stated your dataset contains exactly 2598960 distinct integers. If your dataset had anything less -- for example, a dataset with 1000000 52-bit integers with 5 bits set -- then this would not be possible. So this is very specific to the particular numbers in your post, and is not at all general.

  • Use ranking/unranking to convert each 52-bit integer into a short number, then store the resulting numbers using any standard data structure for sets (e.g., a sorted array or a bitvector). This is a general solution that should meet all of the stated requirements, including minimal space and fast lookup. It is not perfect hashing, and it is not the same as the FNV hash.

$\endgroup$
  • $\begingroup$ as mentioned I am aware of this. I am currently using a lexicographical ranking algorithm (which is basically the same thing) my question was.. is there a hashing function which is more efficient? because I will first have to find the 5 of 52 set bit to use combinatorial number system. i don't want to use the IF statement at all as for my system it is too expensive $\endgroup$ – Siddharth Chabra May 31 '18 at 23:08
  • $\begingroup$ @SiddharthChabra, I don't see anywhere in the question where you mentioned that you are aware of this. I'm confused. If you are already aware that you don't need a data structure, why are you asking for a data structure? Also, the FNV hash is not the same as anything I mention in my answer. It's not the same as ranking/unranking, and actually has nothing to do with ranking/unranking, so I can't make any sense of your comment. I suspect I must not understand what your real question is. $\endgroup$ – D.W. May 31 '18 at 23:46
  • $\begingroup$ The link posted is an algorithm which uses the FNV algorithm to determine minimal perfect hash. I am looking for another way, which does not require double hashing, to create a minimum perfect hash for my data set (the data set is a bunch of keys i have values associated with them as well), Combinatorial number system is what I am using and trying to improve on, hence I am asking if there is a better hash function available $\endgroup$ – Siddharth Chabra Jun 1 '18 at 14:12
  • $\begingroup$ @SiddharthChabra, as I've mentioned multiple times, don't explain here in a comment. Instead, edit the question. I think my answer does address that. The first half of my answer describes another way; you don't need any data structure. The second half describes a third way: ranking/unranking. Ranking/unranking has nothing to do with the FNV algorithm and does not use any hashtables. Combinatorial number systems are a form of ranking/unranking but they're not mentioned anywhere in your question (the only place they are mentioned is your comment) and they have nothing to do with FNV. $\endgroup$ – D.W. Jun 1 '18 at 18:30
1
$\begingroup$

If all you know about the dataset is that it is a subset of the binary representations of the 5-combinations of 52, then there are 2598960 different possible potential values and the only way to avoid a collision is to assign each element to a distinct integer in a set of 2598960 different integers. That's isomorphic to a ranking algorithm, and provides for a hash of less than 22 bits.

Undoubtedly, if your dataset only contains a small subset of that universe, a smaller hash would be useful. Any perfect hash algorithm will work unmodified. You could run the perfect hash algorithm on the 22-bit rank rather than the 52-bit representation, but the possible gains are probably not sufficient to overcome the cost of computing the rank. And that is the best use you can make of your knowledge about the domain restriction.

I don't know anything about you application environment but it is quite possible that you could achieve better performance with a simpler hash function and an efficient hash table implementation. For example, for fixed datasets, cuckoo hashtables can guarantee that only two locations need to be examined in a find operation. To compute the two locations, two different hash functions are used but since the hash computations are completely independent, the two computations can be performed in parallel. That might be an improvement over the FNV algorithm. The cost of this guarantee is a maximum load factor of 0.5, which is a lot worse than the FNV algorithm, but might still be bearable for small datasets.

$\endgroup$

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.