{"action":"created","issue":{"url":"https://api.github.com/repos/aappleby/smhasher/issues/58","repository_url":"https://api.github.com/repos/aappleby/smhasher","labels_url":"https://api.github.com/repos/aappleby/smhasher/issues/58/labels{/name}","comments_url":"https://api.github.com/repos/aappleby/smhasher/issues/58/comments","events_url":"https://api.github.com/repos/aappleby/smhasher/issues/58/events","html_url":"https://github.com/aappleby/smhasher/issues/58","id":312982763,"number":58,"title":"MurmurHash3 collision property","user":{"login":"JuliaX92","id":38256311,"avatar_url":"https://avatars0.githubusercontent.com/u/38256311?v=4","gravatar_id":"","url":"https://api.github.com/users/JuliaX92","html_url":"https://github.com/JuliaX92","followers_url":"https://api.github.com/users/JuliaX92/followers","following_url":"https://api.github.com/users/JuliaX92/following{/other_user}","gists_url":"https://api.github.com/users/JuliaX92/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaX92/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaX92/subscriptions","organizations_url":"https://api.github.com/users/JuliaX92/orgs","repos_url":"https://api.github.com/users/JuliaX92/repos","events_url":"https://api.github.com/users/JuliaX92/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaX92/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2018-04-10T15:46:53Z","updated_at":"2018-04-11T12:09:18Z","closed_at":null,"author_association":"NONE","body":"Hi,\r\n\r\nI have to choose a hash function for a Bloom Filter in my Bachelor's thesis.\r\nAs recommended in some tutorials I used a version of the MurmurHash3.\r\nMy supervisor wants me to find the value of the collision property but I cannot find the place of the documentation.\r\nI have read that it is low but not a real value.\r\nIf someone could help to find the collision property, I'd be very greatful.\r\n\r\nThanks,\r\nJulia"},"comment":{"url":"https://api.github.com/repos/aappleby/smhasher/issues/comments/380429059","html_url":"https://github.com/aappleby/smhasher/issues/58#issuecomment-380429059","issue_url":"https://api.github.com/repos/aappleby/smhasher/issues/58","id":380429059,"user":{"login":"lemire","id":391987,"avatar_url":"https://avatars3.githubusercontent.com/u/391987?v=4","gravatar_id":"","url":"https://api.github.com/users/lemire","html_url":"https://github.com/lemire","followers_url":"https://api.github.com/users/lemire/followers","following_url":"https://api.github.com/users/lemire/following{/other_user}","gists_url":"https://api.github.com/users/lemire/gists{/gist_id}","starred_url":"https://api.github.com/users/lemire/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lemire/subscriptions","organizations_url":"https://api.github.com/users/lemire/orgs","repos_url":"https://api.github.com/users/lemire/repos","events_url":"https://api.github.com/users/lemire/events{/privacy}","received_events_url":"https://api.github.com/users/lemire/received_events","type":"User","site_admin":false},"created_at":"2018-04-11T12:09:18Z","updated_at":"2018-04-11T12:09:18Z","author_association":"NONE","body":"I don't know what the question was... so I am speculating... hoping that it will help clear up the question...\r\n\r\n* Given two text messages, they either always collide, or they do not (assuming that the hash function is not randomized). This might be a trivial observation but I am not sure everyone realizes that. If your text messages are fixed, then you need to have a randomized hash function to be able to talk about probabilities. Then you want to talk about *universality*. There is no established result regarding a randomized MurmurHash's  universality (to my knowledge)\r\n* If we are considering the scenario where we pick text strings at random... and that's usually not how applications are built (e.g., very often the strings are provided to you, possibly by an adversary, we rarely work with random strings)... then if you pick the text messages at random, all that matters is that they randomly end up on any given hash value. That's *regularity*. We can expect good regularity out of MurmurHash, but I am not sure that there are established results.\r\n* Finally, there is the scenario described by @sebres : you have a set of strings and you want to know how many of them collide. Again, what matters is regularity (or evenly are the hash values spread out) but now we care about the characteristics of the set involved."}}
{"actor":{"display_login":"lemire"}}