AVR Freaks

The 1000 inputs must be unique. The challenge is deciding where in the 1000 entry table the entry should be. ie, How does one map a 10byte (80bit) value to a 10bit address space?

For this to happen, some form of reduction must be done. If you can generate a function that will generate 1000 unique values [in the range of 0-999] for the 1000 10-byte arrays, then you're all set and there is no worry. But chances are that finding such a function will be extremely difficult.

Furthermore, I'm not convinced that there will only be 1000 unique inputs, only that at any given time only 1000 out of the 2^80 possible combinations needs to be computed on.

consider this simple example:
we have 1000 objects [ie players in a game, guests to a wedding etc]. Each object is identified with a 10byte handle (username, nickname, given name).

Now we need to somehow track some information about each of these objects.

Firstly, We could do our searches by brute force in O(n) time (assuming an unordered list), by scanning through each entry in the table until a match is found. Here insertions happen in O(1) time, but deletions could be costly, as the entries need to be re-grouped. Alternatively deletions could happen ion O(1) time, but then insertions require a search of up-to O(n) time to find an empty slot.

We could maintain an ordered list, thus allowing for improved searching O(log(n)) time. But the cost of insertion and deletion is heavy.

Or we can do it in approx O(1) time [for all operations] by using a hash, where the calculation based on the handle gives us the index of the entry in the table. If the identified location is not the correct entry, a secondary index step is used. Typically the correct entry is found very quickly, unless the table is very full, and the hash function generates a lot of collisions. Hash tables do work best when sparsely populated. So you will be giving up memory requirements for speed.

well given that you have a 2^80 space mapped into a 2^10 space your chance of collision is extremely high. To put it another way, you have only 1 in 2^70 chance of not colliding.

we might be able to improve your odds a bit. What is the nature of the key? is it a true 8-bit/byte key, or is it encoded somehow (say ascii, bin-hex, base64 etc) If it's encoded we can decode it down to it's true size, reducing the size of the space you are mapping from.

If it is a true 8/bit per byte data stream, then your hashing might as well be a simple XOR of the bytes together, in 16bit pairs. As that result will be just as distributed as any other algorithm. The only difference being that a single bit in the input, will only change the output by a single bit. Whereas a true hash would alter many bits on the output for any single bit change on the input.

Also while your odds of not colliding are 1 in 2^70, the odds of being assigned 2 colliding keys is also about the same. Assuming a true random distribution.

forget the calculus, this is all about statistics and probability.

and I should have said that the odds of not being assigned 2 colliding keys is abut the same.

Also my math was a bit screwed up. Stepping back
your odds of getting a unique 16-bit hash from the 10byte key, is 1 in 2^64 [2^80 / 2^16 = 2^(80-16)]

The odds of getting a collision in your table using a 16bit unique key, in a 1000 entry table is about 1 in 65.

That part wasn't a mistake, only the way I broke it down was.

The 2^10 is the 1000 (1024) size of the table. Combining the two probabilities gives the 1 in 2^70 I stated before.

yes collisions are unavoidable, it's just how often do they occur. In this case there's a 2^70 chance that a collision will occur, given any two keys, due to the small table space, and the huge key space.

I agree with the EOR solution (I suggested it earlier) I also agree with coding it out on a PC for testing.

Perhaps if we knew more about the actual end application we could offer some alternative solutions to solve the problem.

I think you'll find that my math works out. I used 1024 instead of 1000 to keep the calculations simpler As then everything is based on powers of two.

The input is 2^80
the output is 2^10
In the middle we have a 2^16 stage, but it can be ignored in an end-end calculation. (as the 6 bits lost going to the last stage, need to be added onto the result of first stage, to find the end-end probability)

65536! is easily computed by adding all the logarithms from 1 to 65536, base 10. The result is 287193.712898, so taking the exponential results in 5.162949E+287193.

Further:

x = 65536!/((65536-1000)!*65536^1000)

logx = log(65536!) - log((65536-1000)!*65536^1000)

= log(65536!) - log((65536-1000)!) - log(65536^1000)

= log(65536!) - log((65536-1000)!) - 1000*log(65536)

= 287193.712898 - 282380.560015 - 4816.480

= -3.327117

So x = 4.708505e-004 and 1-x = 0.999529