0

I'm in the process of implementing a programming language on top of LLVM. For my polymorphic system, I'm looking for suggestions for a ultra-fast dictionary. I am not concerned with insert time, as these maps are only written to a dozen times or so. But I'm looking for super fast lookup.

I did some research on the open addressing dict implementation in Python, and it seems pretty fast (a few shifts and bitmasks in the best case). However, I want to do my research. Does anyone know of a super fast dictionary/hashmap implementation?

In this case my data will most likely be pointers as keys and pointers as values. Or if it works out better, I could probably get by with integers as keys. Any papers or discussions on the subject would be great.

Improve this question
2
  • Is your key space controlled enough that you can use Perfect Hashing? That's usually fastest and simplest, provided you can concoct the hash function. (However, that is in general hard or impossible; it requires knowledge of the key space.)
    – Donal Fellows
    Mar 26, 2013 at 11:53
  • In the case of using pointers as keys, no. However in the case of integers being keys, I could end up with a sparse array of 1000 items. E.g. there are 1000 different types in the loaded program, but method foo is only implemented on 3 of them. So there may only be entries for keys 42, 550 and 99.
    – Timothy Baldridge
    Mar 26, 2013 at 13:27

1 Answer 1

Reset to default
2

You could take a quick look at "Cuckoo hashing" - if it works, you are guaranteed constant lookup time (in contrast to most hashing schemes, such as open addressing). Of course, it is not without its own problems, but it might be worth looking into, considering your insert/lookup preferences.

Article on wiki: http://en.wikipedia.org/wiki/Cuckoo_hashing

And though you might have considered it, Linear Probing also have its share of advantages - in contrast to OA you scan memory sequentially, which is of course a lot faster than the random access of OA (but of course, other factors influence this as well).

Finally, there exist schemes to create perfect hash tables - these are typically very slow to construct, but guarantee constant time lookups.

I won't link to any papers or articles, but search google for: cuckoo hashing, linear probing, perfect hashing

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.