How can I implement a dictionary with a NumPy array?

Question

I need to write a huge amount number-number pairs into a NumPy array. Since a lot of these pairs have a second value of 0, I thought of making something akin to a dictionary. The problem is that I've read through the NumPy documentation on structured arrays and it seems like dictionaries built like those on the page can only use strings as keys.

Other than that, I need insertion and searching to have log(N) complexity. I thought of making my own Red-black tree structure using a regular NumPy array as storage, but I'm fairly certain there's an easier way to go about this.

Language is Python 2.7.12.

Answer 1

The most basic form of a dictionary is a structure called a HashMap. Implementing a hashmap relies on turning your key into a value that can be quickly looked up. A pathological example would be using ints as keys: The value for key 1 would go in array[1], the value for key 2 would go in array[2], the Hash Function is simply the identity function. You can easily implement that using a numpy array.

If you want to use other types, it's just a case of writing a good hash function to turn those keys into unique indexes into your array. For example, if you know you've got a (int, int) tuple, and the first value will never be more than 100, you can do 100*key[1] + key[0].

The implementation of your hash function is what will make or break your dictionary replacement.