payload: {"action":"created","issue":{"url":"https://api.github.com/repos/ptaoussanis/nippy/issues/126","repository_url":"https://api.github.com/repos/ptaoussanis/nippy","labels_url":"https://api.github.com/repos/ptaoussanis/nippy/issues/126/labels{/name}","comments_url":"https://api.github.com/repos/ptaoussanis/nippy/issues/126/comments","events_url":"https://api.github.com/repos/ptaoussanis/nippy/issues/126/events","html_url":"https://github.com/ptaoussanis/nippy/issues/126","id":548085892,"node_id":"MDU6SXNzdWU1NDgwODU4OTI=","number":126,"title":"Odds of Hash Collision for Custom Type Keyword ID's are quite High","user":{"login":"alexanderkiel","id":822457,"node_id":"MDQ6VXNlcjgyMjQ1Nw==","avatar_url":"https://avatars0.githubusercontent.com/u/822457?v=4","gravatar_id":"","url":"https://api.github.com/users/alexanderkiel","html_url":"https://github.com/alexanderkiel","followers_url":"https://api.github.com/users/alexanderkiel/followers","following_url":"https://api.github.com/users/alexanderkiel/following{/other_user}","gists_url":"https://api.github.com/users/alexanderkiel/gists{/gist_id}","starred_url":"https://api.github.com/users/alexanderkiel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexanderkiel/subscriptions","organizations_url":"https://api.github.com/users/alexanderkiel/orgs","repos_url":"https://api.github.com/users/alexanderkiel/repos","events_url":"https://api.github.com/users/alexanderkiel/events{/privacy}","received_events_url":"https://api.github.com/users/alexanderkiel/received_events","type":"User","site_admin":false},"labels":[{"id":303008011,"node_id":"MDU6TGFiZWwzMDMwMDgwMTE=","url":"https://api.github.com/repos/ptaoussanis/nippy/labels/question/usage","name":"question/usage","color":"d4c5f9","default":false,"description":null}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2020-01-10T13:41:03Z","updated_at":"2020-01-10T13:54:20Z","closed_at":null,"author_association":"NONE","body":"You use 16-bit Hashes for custom type keyword ID's. The [equation to calculate hash collisions](https://preshing.com/20110504/hash-collision-probabilities/) is:\r\n\r\n```clojure\r\n(- 1 (Math/exp (* -1 (/ (* k (dec k)) (* 2 n)))))\r\n```\r\n\r\nor simpler, but only valid for small probabilities:\r\n\r\n```clojure\r\n(/ (* k k) (* 2 n))\r\n```\r\n\r\nSo assume one would like to use at least 128 custom types, as it would be possible with numeric ID's, the odds of a hash collision would be 1 out of 10. So in 1/10 of cases were I use roughly 128 random keywords to identify my custom types, I will have a hash collision.\r\n\r\nFor a small number of custom types like 12 the odds are 1 out of 1000. So I assume for most use cases the choice of a 16-bit hash is ok. But if one plans to use a large number of custom types, collisions will be a problem.\r\n\r\nI would suggest to add some hint to the documentation that the hashing system works only for small amounts of custom types. Furthermore I would include collided keywords explicitly in the warning inside `extend-thaw`."},"comment":{"url":"https://api.github.com/repos/ptaoussanis/nippy/issues/comments/573044258","html_url":"https://github.com/ptaoussanis/nippy/issues/126#issuecomment-573044258","issue_url":"https://api.github.com/repos/ptaoussanis/nippy/issues/126","id":573044258,"node_id":"MDEyOklzc3VlQ29tbWVudDU3MzA0NDI1OA==","user":{"login":"ptaoussanis","id":160011,"node_id":"MDQ6VXNlcjE2MDAxMQ==","avatar_url":"https://avatars2.githubusercontent.com/u/160011?v=4","gravatar_id":"","url":"https://api.github.com/users/ptaoussanis","html_url":"https://github.com/ptaoussanis","followers_url":"https://api.github.com/users/ptaoussanis/followers","following_url":"https://api.github.com/users/ptaoussanis/following{/other_user}","gists_url":"https://api.github.com/users/ptaoussanis/gists{/gist_id}","starred_url":"https://api.github.com/users/ptaoussanis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ptaoussanis/subscriptions","organizations_url":"https://api.github.com/users/ptaoussanis/orgs","repos_url":"https://api.github.com/users/ptaoussanis/repos","events_url":"https://api.github.com/users/ptaoussanis/events{/privacy}","received_events_url":"https://api.github.com/users/ptaoussanis/received_events","type":"User","site_admin":false},"created_at":"2020-01-10T13:54:19Z","updated_at":"2020-01-10T13:54:19Z","author_association":"OWNER","body":"Hi Alexander, thanks for pinging!\r\n\r\nThis is an intentional tradeoff since:\r\n\r\n- The common case is folks using only 1 or 2 custom types. I don't think I've ever seen anyone use more than ~8.\r\n- Collisions will be caught at compile-time with a warning.\r\n- In the event of a collision, it's often possible to change the identifier.\r\n- The identifiers are anyway just a convenience; you can always choose to use a byte identifier directly.\r\n\r\nIs your concern theoretical, or have you actually run into a problem on your end?\r\n\r\n> I would suggest to add some hint to the documentation that the hashing system works only for small amounts of custom types. \r\n\r\nWould be happy to look at a PR if you have something in mind 👍 \r\n\r\n> Furthermore I would include collided keywords explicitly in the warning inside extend-thaw.\r\n\r\nI'm not sure I follow? Collisions will already print a warning message, including the specific id.\r\n\r\n\r\nThanks!"}}
other: {"actor":{"display_login":"ptaoussanis"}}