3 ms·
I am curious, I recently wrote a naive hashmap for C. I am curious about iterating in insert and sort order. Is it possible for a hash function to maintain a s
by samsquire 3y ago
I am curious, I recently wrote a naive hashmap for C. I am curious about iterating in insert and sort order.
Is it possible for a hash function to maintain a sort relationship to it's input and output?
- hdhfjkrkrme 3y agoIf you iterate a python dictionary it will return the keys in insert order. For sort order you need to sort separately.
- blyzz 3y agoSupporting insertion order is straightforward (but has some trade-offs) - you store the values in a backing array or linked list, and the hash table array stores pointers to the values. You could do something similar with a sorted data structure backing the hashmap to get sorted order (a b-tree or something similar). You could have the hash function preserve order at the cost of it being a very bad hash function. If you had n buckets, then the first 1/n elements in the keyspace would map to bucket 0, then next 1/n elements map to bucket 1, etc.