Looking for best way to create HashTable for lookup data

Projects Programming
1

Hi! I'm working on a project on my Diecimila w/ ATmega168 (with Ethernet shield).

The project, when completed, will do this: Go to NOAA and grab & parse the local weather feed and tell a servo to point to the correct weather condition on a dial. First part is done, now I'm just trying to map out the weather conditions to their corresponding icons on the dial. The dial has 13 icons, but NOAA has 274 possible weather conditions. I'd like to create a dictionary where I can give it a weather condition ("Partly Cloudy") and get back the servo position for the corresponding icon (48 degrees).

I've had very little luck finding something to best achieve this. From Googling I found the HashMap library by AlphaBeta, but I wasn't able to get it to work - I got compile errors when using the posted example.

Does anyone have any suggestions for me?

Thanks much!
-P

2

You can use the function bsearch if you need a binary search or simply search the array linearly.

struct condition_t {
   char* name;
   int position;
} conditions[] = {
"sunny", 0,
"cloudy", 20,
};

   for (int i=0; i!=sizeof(conditions)/sizeof(conditions[0]); ++i)
   {
      condition_t* c  = conditions+i;
   }
3

Hash table may not be the best method as you may get multiple hashes per value as it is not guaranteed to be unique.

Keeping it simple, what is wrong with a linear search of the descriptions with an associated 'icon'. You will need an array of values (strings?) to which you compare the data. For example, you can set up a small struture that has the string and the icon:

struct fred {
char *s;
int icon;
}

fred data[] = { {"Sunny", 0}, {"Rainy", 10}, etc

4

Hi,

The problem with one of the suggested approaches is that it will take well over 2K to hold all the descriptions.

I would look at storing the information in program memory, maybe dedicated blocks of name value pairs for each letter of the alphabet and an separate index to each letters block.

Have a look here for some examples to get you started - PROGMEM - Arduino Reference

Duane B

rcarduino.blogspot.com

5

If you prefer to deal with numbers then there are optimized CRC functions in <util/crc16.h> that you can use on the string. Assuming you don't get any collisions in the 274 possible inputs then you could create a table suitable for using bsearch on.

6

One idea - don't know how good it would be, but it's been niggling at me all night.

Instead of keying on the full phrase, why not parse the string for specific information. Create a bitmap of the important bits.

For example, you could have multiple words for rain, like "Rain" and "Drizzle" etc equating to 0x0001. "Hail" could be 0x0002, "snow" 0x0004. "Sun" could be 0x0010. Then you could have things like "Light" 0x0020, "Heavy" 0x0040, "Intermittant" 0x0080, etc.

Then you can do a nice big case on it:

switch(weather)
{
  case RAIN:
  case HAIL & LIGHT:
    icon = 1;
    break;

  case SUN & INTERMITTANT:
  case CLOUD & PARTIAL:
    icon = 2;
}

Etc.

7

Thanks so much for the help, everyone - I'm going to go with a struct and try to put it in progmem. Thanks again!

8

If you need more room, you could drop a 328P in the Diecimelia and put a bootloader on it, that should work IIRC.

9

marco_c:
Hash table may not be the best method as you may get multiple hashes per value as it is not guaranteed to be unique.

A perfect lead in to Minimal Perfect Hashing...
http://burtleburtle.net/bob/hash/perfect.html

10

A perfect lead in to Minimal Perfect Hashing...

Looks really interesting. Thanks.