We have a database that locates records using a 'hash & step' method (linear probing). This has the typical problem of collisions causing speed issues when the record array is full. Hence, for speed, the array needs to be sized to ~ 2x the number of records. This is pretty inefficient when it comes to resources (each record being 512 bytes, typical arrays being 4000 records - ok its not that bad, but we have a couple of these arrays our 2MB app loads a 1MB database and has a 30-40 MB footprint!!).

Does anyone know of any fast search methods that could be alternatives? I was reading about quadratic probing instead of linear, but you'd still have to keep the 'null space' up...