Forum Discussion
Deterministic Unique IDs
- In your example the strings are unique. Is this true in your real scenario?
- If not unique, please verify whether or not duplicate rows should have matching unique ID values.
- If unique, why do you need a unique ID column?
- The Pigeonhole Principle is not really part of a hash algorithm. It's a mathematical theorem that states that if you have more than N items to put into N containers, at least one container will contain multiple items (i.e. a hash collision). You are likely to get hash collisions long before you approach the number of possible hash outputs. It's just that if you go over, you're mathematically guaranteed to have them.
- It looks like the HASH function outputs values in the range of about ±9.2 x 1018. This is roughly the size of a 64-bit signed integer assuming it uses that full range.
- Check out the probability of random collisions table on Wikipedia to get an idea of how likely a collision is. For example, assuming any hash output has equal probability, and the HASH function has an output on the order of 64 bits, then you can have up to around half a billion input values with a <1% probability of having a random hash collision. Or use this tool
- In your example the strings are unique. Is this true in your real scenario?
- In your example the strings are unique. Is this true in your real scenario?
- If not unique, please verify whether or not duplicate rows should have matching unique ID values.
- If unique, why do you need a unique ID column?
- The Pigeonhole Principle is not really part of a hash algorithm. It's a mathematical theorem that states that if you have more than N items to put into N containers, at least one container will contain multiple items (i.e. a hash collision). You are likely to get hash collisions long before you approach the number of possible hash outputs. It's just that if you go over, you're mathematically guaranteed to have them.
- It looks like the HASH function outputs values in the range of about ±9.2 x 1018. This is roughly the size of a 64-bit signed integer assuming it uses that full range.
- Check out the probability of random collisions table on Wikipedia to get an idea of how likely a collision is. For example, assuming any hash output has equal probability, and the HASH function has an output on the order of 64 bits, then you can have up to around half a billion input values with a <1% probability of having a random hash collision. Or use this tool
AlexisOlson Thanks for this and apologies for the delayed reponse.
To sumarize,
Assuming DAX HASH is 64 bit , probability is directly proportional to k (lower k lower probability, higher k higher probability)
I probably have ~2500 string to run through HASH, so I should be good. I wonder why MS has no literature around it.
Thanks for enlighting me on pigeonhole principle but it is least of my problem as DAX HASH does not follow it.
In your example the strings are unique. Is this true in your real scenario? - yes, this table is generated internally through SUMMARIZEDCOLUMNS from the filter context
If unique, why do you need a unique ID column? - I need to use it for a tiebreaker in RANKX
Assuming DAX HASH is 64 bit , probability is directly proportional to k (lower k lower probability, higher k higher probability)
Take a look at the Wiki article again. Probability is proportional to k² rather than k.
If all you need is a tiebreaker and values are unique, you can use the string itself rather than a hash.
Assuming your string column is [Name], tryADDCOLUMNS ( base, "rank", RANK ( base, ORDERBY ( [Value], ASC, [Name], ASC ) ) )With RANK, you can easily add multiple ORDERBY conditions and they don't need to be numeric.
That's right. But just in case, I need to utilize any derived on-the-fly values as below, they can't be accommodated in RANK.
RANKX is (probably) all weather from the original/derived value perspective(hence HASH). Else RANK is pretty good
var cte_1 = addcolumns(cte_0, "derived", some_dax_callback_that_generate_string)I don't follow. You can use derived columns in the ORDERBY subfunction of RANK.
If you want to use RANKX, then I'd recommend uniquely ranking the strings (alphabetically) in your CTE instead of hashing them and then using that rank instead of the hash as your tiebreaker.