Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Hash functions represent a chunk of data with fewer bits than the original data, hence there's always a _chance_ of a collision. With cryptographic hashes, the output of the hash function is relatively large in size, making the probability of an accidental hash collision vanishingly small. For example, sha-256 hash algorithm can result in over 115 quattuorvigintillion different values.

The hashing functions used with hash tables typically reduce the hashed value to one of only tens or hundreds of values, making collisions unavoidable. Typically, a hash table will try and manage the number of available slots to be roughly equal to the number of items stored in the hash to achieve performance that is a good balance of lookup time and memory requirements. For an extreme example, In Ruby, hashes of less than a certain size (6, I believe) are just represented internally as a list because the overhead of using an actual hash table is greater than just iterating through every item in the list.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: