3

Is there a class of hash functions that meets the following specs:

  • Upper and lower bound can be specified
  • Uniqueness is guaranteed as long as the input is between the upper and lower bounds
  • Amount of entropy is controllable, or at least high and evenly distributed

An example of a low entropy hash function that produces unique results, and allows the upper bound to be specified is

int hash(int x,int upperBound) {
    return x - (upperBound * (x \ upperBound));
}

This would produce a number between [0, upperBound), resetting back to 0 when the number can be divided by upperBound.

So lets say our upper bound is 20^3, that gives us 46656 numbers I believe. Feeding a number between 0 and 46655 should produce a unique result. Any number over will produce a collision. Providing the same number should always give the same result. Being able to control entropy would be a plus, but if it's evenly distributed and high then that will work fine too.

The end goal is to turn the number into an alpha numeric representation which can quickly be looked at to determine if it has been changed since the last time a number was requested. I should not receive the same number until all numbers have been used.

  • input? there shouldn't be input for an RNG – ratchet freak Dec 22 '14 at 20:09
  • True. This smells more like a hashing function or something... I need an algorithm that can be "continued". IE, specifying the iteration count. This would be the input. Updated the post. – Justin Dec 22 '14 at 20:14
  • 1
    If you want a quick and dirty solution, you can just generate such a mapping table by using a relatively simple method to generate a random permutation, check for uniqueness, then resolve any collisions. Save the resulting table and the f(x) mapping so defined by the table pretty well solves your request (with entropy determined by your generation function and collision resolution). Is there some feature this sort of approach doesn't solve for you? I think otherwise the problem is just getting a known/studied function that maps ints (or small ints) to X alphanums. One can be made to work... – BrianH Dec 22 '14 at 21:59
  • Just to be specific, given the Pigeonhole Principle if your inputs (in your case 1000 max inputs) is less than or equal to the outputs (46655 as you stated) a functional mapping of the inputs to the outputs can be defined such that it is a collision free hash function. As a matter of practicality, though, if that's all you need then it's just easier to define the mapping using some random permutations, save the mapping, and call it good. If you need more it is possible, just I think not a "popular" algorithm available for quick use. – BrianH Dec 22 '14 at 22:04
  • Thanks. I could do a brute force approach, and store the mappings, but I'm interested in the maths behind the answer too. I'm more interested in how to mathematically make all the pigeons fill up all containers without sharing first ;). The encoding of a number to a character code has been solved, it's the number generation without collision that is the part i'm stuck on. Maybe this question should be moved to mathematics.stackexchange.com ? – Justin Dec 22 '14 at 22:06
2

OK, so I feel I've done enough research to at least begin to move things in a helpful direction.

The term for what you are looking for generally is a "perfect hash function", with the addition that you want some potentially manageable degree of randomness.

In general the state of the art is that you use an algorithmic method that generates a mapping, and then save that final mapping. There are lots of interesting ways to go about this (and more), but the problem comes down to the fact that the probability of a collision with any random method is likely going to guarantee a collision before you exhaust your input space. I'll provide an example of this now, in C# code (copy/paste-able code, I believe):

  System.Text.StringBuilder Sb = new System.Text.StringBuilder();

  System.Collections.Generic.HashSet<string> results = new System.Collections.Generic.HashSet<string>();

  using (System.Security.Cryptography.SHA512 hash = System.Security.Cryptography.SHA512Managed.Create() ) {
    System.Text.Encoding enc = System.Text.Encoding.UTF8;

    for (int input = 0; input < 10000; input++) {
      Byte[] result = hash.ComputeHash(enc.GetBytes(input.ToString()));

      foreach (Byte b in result) {
        Sb.Append(b.ToString("x2"));
      }

      results.Add(Sb.ToString().Substring(Sb.Length - 3));
    }

  }

What I'm doing is giving an input value of 0-9999, converting it to a SHA512 hash, and then only taking the last 3 alphanumeric digits. You can then compare the size of the HashSet to the inputs to determine just how many duplicates you have.

The result: with 10000 inputs you only get 3735 unique results. Ouch - that's a lot of collisions! If you change your request to mapping to 4 digits (change the above final line of code to Sb.Length - 4), you get 9303 - not bad! If you allow 5 digits of output you get 9955 - still with the collisions, and we've massively extended our allowable output and only allow 10000 inputs!

So if you used such a method you need to restrict your maximum inputs considerably and likely increase the size of the output too.

If you didn't care so much about randomness, you could use (x + 18) % 46656, as in replacing the last line with this:

results.Add(((input + 18) % 46656).ToString());

This results in zero collisions and runs a lot faster, too. The output is not at all random, of course, especially if you move up in sequence.

Now, with some hand-tuning I did manage to come up with this little doozy:

results.Add(((input * (40001) + 11) % 46656).ToString());

So take the input, multiply it by 40001, add 11, then "wrap-around" it to your maximum input. On 0-46656 as input it generates no collisions, and yet it jumps all over the place - f(1)->400012, while f(2)->33357. If you skip using the first few inputs (0-2) the function that generates these numbers is even more opaque, and as this is non-linear it is not easy to find the function that generates this set. Multiply by an odd number and you can use this as a kind of "seed" to your function - prime numbers might be an even better choice! Small numbers result in less jumpiness, while multiplying by the same number you are taking the mod of is...well, always 0. I suspect somewhere in the middle/high side is ideal.

Then parse the integer output into your desired string format, and tadah, Bob's your uncle!

Now if you want something more random with measurable entropy and that takes a very long time to reverse-engineer...well, that's going to be harder to arrange by far.

I hope this is at least helpful on getting you closer to where you want to go.

  • "On 0-46656 as input it generates no collisions, and yet it jumps all over the place". Awesome, this defiantly sounds like what I am looking for. Do you happen to have any reading material on adding more "jumpiness"? I know there has to be some operations which can be used and don't produce collision (ie, XOR combined with some bit shuffling perhaps?) Entropy might of been a bad word to use, it's fine if the result is able to be reverse engineered, just should appear to be jumpy. Thanks again for taking the time to research =). – Justin Dec 23 '14 at 18:14
  • I'll check out that book you linked too, seems like a interesting read and would have some good ideas =). Again, the hash doesn't have to be perfect, just should be perfect for a specified range of values. – Justin Dec 23 '14 at 18:27
  • @Justin The big trick is "injective function" and "surjective function" (Google for plenty of good info - I just had "math for information sciences" class myself). The trick for jumpiness is consider your outputs a circle. You need to "spin the wheel" but not just land directly on the opposite side. Multiplying by an odd (or usually even better, prime number) is a handy trick I learned in an algorithms class when we talked about hashing which may have been in the textbook, and for jumpiness you just "spin the wheel" a few times (by observation). It's like a much more thorough Caesar cipher. – BrianH Dec 23 '14 at 18:35
  • @Justin I should note that that as this really is hashing, it is not symmetric - you can't take the hashed output and find what input was used without a brute-force (try all the numbers) approach. Of course since it's a simple function with restrained inputs/outputs you can actually do that extremely quickly on a modern computer...so I guess that isn't a big deal after all! But the more complex the function and the larger range of inputs/outputs, the worse it gets. – BrianH Dec 23 '14 at 18:37

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.