Arduino Hash Table/Dictionary

Question

I am trying to get a Hash Table or Dictionary to work on the Arduino Mega 2560. My goal is to have something like

dictionary[ENGLISH]["ACCOUNT"] = "Account";
dictionary[ENGLISH]["DATE_AND_TIME"] = "Date and Time";
dictionary[ENGLISH]["IDLE"] = "Idle";
dictionary[ENGLISH]["Language"] = "Languge"
dictionary[ENGLISH]["MAIN_MENU"] = "Main Menu";
dictionary[ENGLISH]["PRESCRIPTION"] = "Prescription";
dictionary[ENGLISH]["SETTINGS"] = "Settings";
dictionary[ENGLISH]["SOUND"] = "Sound";

where ENGLISH is essentially a constant 0, and I will have SPANISH and FRENCH as well (1 and 2 respectively). That is, an array of 3 dictionary elements.

On a first Google search, I found a link to a library that models the C++ STL, but it is not working on Arduino 1.0.3 for me at all. I was wondering if anybody had an alternative for using maps/hash tables in arduino for me, or a fix to get the library mentioned working.

For some context of my situation, I am modeling a menu system via a touchscreen on the Arduino, it has to accept 3 languages (for the buttons). The chosen language is found in a location in EEPROM and I'll keep it in the variable 'lang', when I need to print something to the screen, I'll do something like:

    screen.print(dictionary[lang]["SOUND"], CENTER, 23);

and depending on the 'lang' the user has chosen, it will print accordingly, ideally.

Solution 1

I think a hash table may be unnecessary here, and there are good reasons to avoid it on this platform anyway.

Why a hash table may be unnecessary

Usually in such situations there is no need for a string key, since the key is visible only inside your code, and the key is not interacted with from outside your program. Thus, the usual solution is to have a (pseudo) integer key, in the form of #define which is handled by the preprocessor and not your program:

#define kWORDIDX_LANGUAGE   1
#define kWORDIDX_SOUND      2
#define kWORDIDX_MAINMENU   3
#define kWORDIDX_SPAGHETTI  4
...
dictionary[ENGLISH][kWORDIDX_SOUND] = "Sound";
...

You can then access your dictionary entries like this Sreen.print(dictionary[lang][kWORDIDX_SOUND], CENTER, 23); or something similar.

The advantages of this approach are:

• You are saving memory space: no string keys are used
• You are saving processing time: while hash table access is technically O(1), there are still constant factors involved to compute the hash. Array access is faster.
• You code is less prone to errors: if you misspell your key using string accesses (which are a form of magic numbers anyway) you'll get a hash table miss. If you misspell one of the #defined keys, you get a compile error, which is what you want

Why you don't want a hash table on an Arduino

Arduino is a memory-constrained platform: it has very limited memory. The problem with using a real hash map is as follows:

• Strings take up more memory space that ints (usually). Using #define keys, which are converted by the compiler to integer literals, you are using 1, 2, or 4 bytes per key (depending on your compiler settings), whereas each string key requires strlen(s) + 1 memory space to store. This space is actually used twice: once in Flash (that is where variables are initialized from) and once in SRAM.
• The hash map data structure itself takes up more memory: there is the overhead of either empty entries in the hash map (in open addressing scheme) or of the linked list (in the separate chaining scheme). Since your data is read-only you don't need that overhead, since the hash table will not be added to.
• One trick people use to save on memory in Arduinos is storing read-only data (such as strings) in program memory only (and not SRAM) using the PROGMEM keyword. If you build your dictionary using a hash map, this route will not be available to you. On the other hand, given a #define-type indexing scheme as above, it will be very easy to store all your language strings as PROGMEM strings.

Solution 2

You can also use a data structure to define a dictionary:

typedef struct { 
  uint8_t lang;
  char* sound;
  char* value;
} langDictionary;

Then you can define an array of the structure with the values to be used:

const langDictionary myDictionaryArr[] {
    {0, "ENGLISH", "Settings"},
    {1, "SPANISH", "Ajustes"},
    {2, "FRENCH", "Paramètres"}
};

And finally you can use the array to search the properties:

void setup() {
  Serial.begin(115200);
  for(uint8_t i = 0; i < sizeof(myDictionaryArr)/sizeof(langDictionary); ++i) {
      Serial.println(myDictionaryArr[i].value); //Prints the values: "Settings", "Ajustes" and "Paramètres"
  }
}

Solution 3

while i perfectly agree with the previous answers, the arduino playground has as "HashMap Library for Arduino".

Comments

[Robert Cardona]

Very well written! Can you go into more detail about how I can use PROGMEM for the method you outlined above? I've used it before for storing sprites when drawing onto the screen, but nothing like this. Thanks!

[angelatlarge]

Probably best to take a look at the "Arrays of Strings" section here: that has a complete example of PROGMEM table of PROGMEM strings. It's just that instead of strcpy_P(buffer, (char*)pgm_read_word(&(string_table[i]))); (or similar) you'd use strcpy_P(buffer, (char*)pgm_read_word(&(string_table[kMY_DEFINED_INDEX]))); (or similar). If that doesn't help maybe post another question here: it seems like it is a bit of a different topic. What do you think?

[angelatlarge]

Excellent! Glad to hear it.

[Ciasto piekarz]

using HashMap Library gives error missingWProgram.h missing.

[jitter]

@Ciastopiekarz, this is unrelated to using a library in general - please include the mentioned file in your code.

[Ciasto piekarz]

if I use HashMap.h in the code: I get the compilation error: ~/Arduino/libraries/HashMap/HashMap.h:33:22: fatal error: WProgram.h: No such file or directory #include <WProgram.h> ^ compilation terminated.

[jitter]

alright, try either removing the include statement or changing the filename to Arduino.h.

[Regis May]

And why I do want a hash table: If data is passed to an Arduino and you need to parse and store it on the Arduino in a flexible way, some kind of string-string-dictionary (= a hash map) would be perfect for that job. While I generally do agree very well with your statements please have in mind that you will not be able to avoid all kinds of use cases.

[jitter]

@clankill3r can you please be more specific?

[BigMan73]

The playground has a note: Hint: This is NOT a real hashmap, it's a key-value-map. Searching in this "HashMap" is done via simple iteration over all entries, not via hashed-key. A "hashmap" that performs look ups in O(N), full scanning the data, is NOT a hashmap but a sugar coated array

[doublejosh]

I found that you cannot overload this Arduino hashmap to use a custom struct, it only stores ints :(

[Georgi Peev]

That is a good trick, when you want to simulate dictionary, where the key is the Array's Index.