3 ms·

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 col

• tzs 9y ago
  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.