5,336
edits
(Created page with "Hashing is a tool to compactly store sparse data (i.e. maps and sets). On average, hashing generally achieves constant-time lookup but can degrade to linear time depending on the data nad the algorithm details. There are two common problems with hashing * Collisions * Cache coherency ==Collision resolution== There are several methods to resolve collisions when implementing hashmaps. Below are some common solutions. Note that in scenarios where performance is of upmost...") |
|||
Line 23: | Line 23: | ||
===Perfect Hashing=== | ===Perfect Hashing=== | ||
{{main | Wikipedia: Perfect hash function}} | |||
==Locality-sensitive Hashing== | ==Locality-sensitive Hashing== |