News for hackers. Stuff that matters.
Re:Show HN: Browser extension to read HN comments for any ur... by Ajedi32 on Tuesday February 06, 2018 @11:49AM (#16317462)
Don't hash tables typically store the key itself in the table though? Wouldn't that take up _more_ space per entry than a 160-bit hash? Using a sufficiently collision-resistant hash function allows you to eliminate the need to store URLs entirely, which in theory should reduce the size of the hash table significantly.
Re:Show HN: Browser extension to read HN comments for any ur... by tzs on Tuesday February 06, 2018 @01:26PM (#16318213)
Whether or not you need to store keys depends on how you handle collisions.

For instance, if we had a hash table whose keys were names, and whose values were telephone numbers, we'd probably have to store keys with the phone numbers so that in the case of a collision we could figure out which phone number matches the search key.

If, on the other hand, we had a hash table that stored record numbers of employee records from our employee database, keyed by employee name, then we probably would not need to store keys with the hash table values. If there is a collision, we can just retrieve all of the colliding records from the database. Those records will contain the employee name, and we can use that to figure out which is the right one.

For the HN comment extension we are closer to the second case. The HN story contains the URL, so in the case of a collision we can fetch all the colliding HN stories and see which one is the right one.