FNV-1, Murmur2, and DJB2 are examples of non-cryptographic hashing functions used in actual applications (see Which hashing algorithm is best for uniqueness and speed?). These are all similar in that they have an inner loop that computes the result by using simple operations such as XOR or bit shifting.

Perhaps these algorithms are truly the best available; I don't know. But Pearson Hashing, in particular, seems to be rarely considered. Yet it is the algorithm that would seem to be the best, given no domain information about the keys, because it was designed to spread out (randomize) the range well for any domain.

This means (for character string keys) that whether the keys are single letters (a small domain) or strings of length 128 (a much larger domain), the result (the hashed value) is guaranteed to be spread out well (distributed randomly over the range of the function). The reason that such a good random distribution is desired is that such a distribution would be expected to reduce the number of collisions for random selections of keys (again, assuming no special characteristics of the key (domain) distribution).

Pearson hashing accomplishes this by using a 256-entry array that contains a random permutation having a single cycle. To clarify what I mean, here is a four-entry array specifying such a permutation of the value list [0, 1, 2, 3]:

0:  2
1:  3
2:  1
3:  0

Pearson hashing scans the key string. For each byte (it's okay for a character to span multiple bytes), it XORs the byte into a running sum hash, then looks hash up in its 256-byte permutation array. This lookup result is the next running sum. Since the array contains 256 entries, it will handle any byte. To scale up to a larger range, such as a 16 or 32 bit range, the inner loop is performed more than once. Since the algorithm uses one XOR and one simple array lookup for each byte of the range, it is probably the fastest algorithm possible, particularly if implemented in assembly language. And the size of the Pearson hashing function should be small, not much more than the 256 bytes used by its array. Except in very tiny embedded applications, I can't imagine 256 bytes of memory being an objection to the use of Pearson hashing.

Some examples of Pearson function implementations are given at https://gist.github.com/imdario/4758192 .

I would be very interested to see an analysis of Pearson hashing as compared to other more commonly-used algorithms, such as the three listed above, with input sets such as an English dictionary. I would expect it to do very well.

  • 1
    What's the question? Sum it up. – RubberDuck Jun 11 '16 at 15:51
  • The question was stated clearly: "I would be very interested to see an analysis of Pearson hashing as compared to other more commonly-used algorithms..." It is not a yes or no question. It requires the kind of programming that was done in Question 49550. I post this as a question in case someone can answer it more easily than I can. – David Spector Jun 11 '16 at 16:06
  • 1
    That's not a question. It's a request for a scholarly article to be written here. – RubberDuck Jun 11 '16 at 16:07
  • Was Question 49550 "scholarly"? Good answers were already written here. What is wrong with "scholarly"? Education is the basis of all practical work in software engineering, which is the topic of this Forum. – David Spector Jun 11 '16 at 16:11
  • This isn't a forum @DavidSpector. It's a question and answer site. Your post had the potential to be an excellent question, but you need to narrow it down and ask an answerable question. Good questions have answers. – RubberDuck Jun 11 '16 at 17:14

I don't have a practical comparison between Pearson hashing and the other common suggestions, but I can highlight some assumptions you're making that aren't necessarily true and which might explain why it isn't as popular as you seem to expect:

  • You state that having good distribution of small keys throughout the entire range is just as important as good distribution of larger keys, but this is not necessarily true. In practical applications, small keys are rare, and cannot occur with any non-trivial frequency in large data sets simply because there are only a small number of possible small keys. We only care about optional performance for large data sets, as small data sets can be processed quickly enough in any case.

  • You assert that performance will be good due to the simplicity of the algorithm, but it doesn't really seem that simple to me. For a 32-bit hash (which is the smallest that's really useful) it requires 8 operations per byte. Compare this to Murmur's 6 operations per 4-byte word, and it is clearly not going to be competitive. Even a single byte output at 2 operations per byte is unlikely to be as fast as Murmur.

  • 1. Pearson Hashing is just as good for any size keys, and any key distributions. Its performance is worth testing for very large key sets. 2. Collision avoidance must be compared with execution time for actual key sets that will occur at runtime. There is no other way to choose an algorithm that is likely to be best in practice. One application may need collision avoidance, another may need fast execution time. – David Spector Jun 23 '16 at 13:16
  • You misunderstand my point. All of the popular hash algorithms have these characteristics for large keys; I sincerely doubt you'll see noticeably better results than Murmur's (for example) because if you look at the randomization statistics for that hash you will find that it is, by any reasonable measure, almost entirely "random". There really isn't much that can be gained. And as for trading execution time for "collision avoidance", note that collisions are inevitable in any case and you must therefore provide a backup mechanism. As long as your backup mechanism is not ... – Jules Jun 24 '16 at 22:12
  • ... orders of magnitude slower, the low frequency of collisions with any reasonable hashing algorithm in comparison with the total number of times hashing is required means that even if you do manage to improve the number of collisions radically (say by halving the number) in any reasonable application the cost of hashing is going to be much higher than the cost of occasionally resolving a collision. With an algorithm that's around 5-6 times slower, you are highly unlikely to find an application where it is worth the cost. – Jules Jun 24 '16 at 22:16
  • Good points, but we won't know for sure until we have actual large-scale statistical testing, similar to what was accomplished for the more popular algorithms. I'm not being unreasonable in calling for inclusion of Pearson Hashing. Arguments against testing reasonable and unique algorithms are at root arguments in favor of ignorance. Let's not do that. – David Spector Jun 25 '16 at 23:30
  • David: It sounds like you're not asking a question so much as pushing for an algorithm you personally like. If you want to test it, feel free to test it and post the results. No one is going to stop you. – Jody Lee Bruchon Jul 21 '16 at 10:56

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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