tag:blogger.com,1999:blog-1994130783874175266.post4561992295793100334..comments2024-03-29T12:50:41.386+01:00Comments on bitsquid: development blog: Simple perfect murmur hashingNiklashttp://www.blogger.com/profile/10055379994557504977noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-1994130783874175266.post-79109024485030149072015-07-30T11:34:40.509+02:002015-07-30T11:34:40.509+02:00Yes, most often we use the IDs for indexing. As yo...Yes, most often we use the IDs for indexing. As you say, we still have to deal with collision in the smaller set of bits, but the data structures become a lot smaller and simpler when you don't have to store a lot of arbitrary sized strings.<br /><br />But actually, we don't use perfect hashing any more... we just hash into a large enough keyspace that collisions are so unlikely that we don't have to worry about them.Niklashttps://www.blogger.com/profile/10055379994557504977noreply@blogger.comtag:blogger.com,1999:blog-1994130783874175266.post-1406298951669933312015-07-23T14:31:31.207+02:002015-07-23T14:31:31.207+02:00Nice blog, I really enjoy reading your articles !
...Nice blog, I really enjoy reading your articles !<br /><br />Unfortunately I am not sure to understand the purpose of those 32 bits resource IDs ...<br />It speeds up comparisons for sure but do you really often compare resources in your game ? Have you practical examples in mind ?<br /><br />Do you plan to use those IDs for indexing ? In that case, either you need a 4 billion entry table or you use a smaller set of bits from the key. By doing the last option, you loose the benefits of perfect hashing and collisions come back. Even if it deals faster with collisions (complete hash as key), I admit.<br /><br />Otherwise, if comparisons are the only purpose of those IDs, iLych solution (above reply) may work too since we generate them at preprocessing stage. We do not need to store a map, we just want to give a unique ID to each resource and forget all about the rest (e.g. using alphanumeric or timestamp order as mapping rule). Then adding hash to resource data. Or maybe you only need the seed and processes hashes at runtime ?<br /><br />Sorry for bothering you with so much questions but I have the feeling it could help me in the future.Tasty T.https://www.blogger.com/profile/10393374863687473517noreply@blogger.comtag:blogger.com,1999:blog-1994130783874175266.post-58147918100220679122012-07-23T21:35:34.826+02:002012-07-23T21:35:34.826+02:00In that case you would have to store the "map...In that case you would have to store the "map" somehow. How would you do that? In a hash table? Then you are using a non-perfect hashing scheme to get to your perfect hashing scheme, which means you have removed all advantages of it.Niklashttps://www.blogger.com/profile/10055379994557504977noreply@blogger.comtag:blogger.com,1999:blog-1994130783874175266.post-29701607463143872712012-07-20T11:10:53.901+02:002012-07-20T11:10:53.901+02:00What if I just get all keys and map them to number...What if I just get all keys and map them to numbers from 0 to N one by one with increment? Would it cause problems?iLychhttps://www.blogger.com/profile/13747822433520945534noreply@blogger.comtag:blogger.com,1999:blog-1994130783874175266.post-4210842704340055242010-09-10T11:05:15.858+02:002010-09-10T11:05:15.858+02:00Yes, you would have to know the set of all possibl...Yes, you would have to know the set of all possible key values in the preprocessing stage.Niklashttps://www.blogger.com/profile/10055379994557504977noreply@blogger.comtag:blogger.com,1999:blog-1994130783874175266.post-9590171688680685822010-09-10T10:51:03.438+02:002010-09-10T10:51:03.438+02:00Sorry for being late in the discussion but it mean...Sorry for being late in the discussion but it means IDs are computed in a preprocessing stage?gpakoszhttps://www.blogger.com/profile/13526493214607805757noreply@blogger.com