4 ms·

Am I missing something here? This is how every hash table acts by default in almost every language I've used. If a key already exists in the hash, the value is

Am I missing something here? This is how every hash table acts by default in almost every language I've used. If a key already exists in the hash, the value is overwritten. I think the only exception was in Java and you had to use a specific hash object to get the effect you are stating.

ignoramous 7y ago
No, what BigCache does isn't what hash tables do to resolve conflicts and the JDK Maps absolutely do not overwrite value upon collision of unequal keys. Imagine a naïve hash-function, h(x), that simply mods x by 10. Now, let's insert (key, value) pairs (20, twenti), (3, three), and (30, thirty) into the table in succession. h(20) = 20 mod 10 = 0 (20, twenti) is inserted at empty slot, table[0] h(3) = 3 mod 10 = 3 (3, three) is inserted at empty slot, table[3] h(30) = 30 mod 10 = 0 Conflict. (30, thirty) which is not equal to (20, twenti) will be hashed to the same slot, table[0], as the latter. Historically, hash-tables have resolved these conflicts via open-addressing or linear-chaining. And, let's say we now insert (20, twenty). h(20) = 20 mod 10 = 0 Update. Inserting (20, twenty) at table[0] is not a conflict since the key, 20, of the existing entry at table[0], (20, twenti), and of the incoming entry, (20, twenty), are equal. In BigCache's case, if I'm right, all conflicts are updates.
- merlincorey 7y ago
  Thank you for breaking this down -- since the author compared BigCache to the built in `map`, this collision behavior is precisely what brought on my line of thinking. Of course BigCache is faster than the builtin map -- they are completely different kinds of hash table. As malisp explains in a comment above, BigCache is a "direct mapped cache".
- hinkley 7y ago
  I recall reading a paper, maybe ten years back, about a collision handling algorithm that was far simpler than any I’d seen before. The paper claimed that double hashing avoided unresolvable collisions in most cases without chaining or any of the additional overhead (especially on deletes) of cuckoo hashing or any of the alternatives. Each key can live in two slots, using two different hash algorithms. If it’s not in the first it’ll be in the second. I can’t speak to the quality of their math. And of course a lot of theory for hash tables is based on the quality of the hash. The empirical evidence has often failed to support the theory.
  - ignoramous 7y ago
    Is 2-left hashing what you're taking about: https://xlinux.nist.gov/dads/HTML/twoLeftHashing.html https://xlinux.nist.gov/dads/HTML/twoLeftHashing.html If not, Michael Mitzenmacher is known to research a lot on hashing algorithms, may be you would find it was one of his papers? https://dblp.uni-trier.de/pers/hd/m/Mitzenmacher:Michael https://dblp.uni-trier.de/pers/hd/m/Mitzenmacher:Michael Also see: https://danluu.com/2choices-eviction/ https://danluu.com/2choices-eviction/
    - hinkley 7y ago
      Similar to two choice, but they were using it instead of chaining.

ignoramous 7y ago

No, what BigCache does isn't what hash tables do to resolve conflicts and the JDK Maps absolutely do not overwrite value upon collision of unequal keys. Imagine a naïve hash-function, h(x), that simply mods x by 10. Now, let's insert (key, value) pairs (20, twenti), (3, three), and (30, thirty) into the table in succession. h(20) = 20 mod 10 = 0 (20, twenti) is inserted at empty slot, table[0] h(3) = 3 mod 10 = 3 (3, three) is inserted at empty slot, table[3] h(30) = 30 mod 10 = 0 Conflict. (30, thirty) which is not equal to (20, twenti) will be hashed to the same slot, table[0], as the latter. Historically, hash-tables have resolved these conflicts via open-addressing or linear-chaining. And, let's say we now insert (20, twenty). h(20) = 20 mod 10 = 0 Update. Inserting (20, twenty) at table[0] is not a conflict since the key, 20, of the existing entry at table[0], (20, twenti), and of the incoming entry, (20, twenty), are equal. In BigCache's case, if I'm right, all conflicts are updates.

merlincorey 7y ago
Thank you for breaking this down -- since the author compared BigCache to the built in `map`, this collision behavior is precisely what brought on my line of thinking. Of course BigCache is faster than the builtin map -- they are completely different kinds of hash table. As malisp explains in a comment above, BigCache is a "direct mapped cache".
hinkley 7y ago
I recall reading a paper, maybe ten years back, about a collision handling algorithm that was far simpler than any I’d seen before. The paper claimed that double hashing avoided unresolvable collisions in most cases without chaining or any of the additional overhead (especially on deletes) of cuckoo hashing or any of the alternatives. Each key can live in two slots, using two different hash algorithms. If it’s not in the first it’ll be in the second. I can’t speak to the quality of their math. And of course a lot of theory for hash tables is based on the quality of the hash. The empirical evidence has often failed to support the theory.
- ignoramous 7y ago
  Is 2-left hashing what you're taking about: https://xlinux.nist.gov/dads/HTML/twoLeftHashing.html https://xlinux.nist.gov/dads/HTML/twoLeftHashing.html If not, Michael Mitzenmacher is known to research a lot on hashing algorithms, may be you would find it was one of his papers? https://dblp.uni-trier.de/pers/hd/m/Mitzenmacher:Michael https://dblp.uni-trier.de/pers/hd/m/Mitzenmacher:Michael Also see: https://danluu.com/2choices-eviction/ https://danluu.com/2choices-eviction/
  - hinkley 7y ago
    Similar to two choice, but they were using it instead of chaining.