Hash function

[Ioannis]

Hi!

I am looking for something like or exactly that. A hash function.

There are many (about 3000) groups of data (3 bytes long) that will be stored in EEPROM and would like to search very fast. If serially search a PIC with 8MHz clock would do about 8 seconds. Since the system is going to operate a parking bar, this time is too long.

So, a hash function may help store and retrieve the group of data almost immediatly.

Do anyone have any infos about it?

Regards,
Ioannis

[Darrel Taylor]

If the data in the EEPROM is sorted ?? You can use a Half-Split method.

Start in the middle, if the value is Less than the one you're looking for go halfway between that point and the End of data, then check again. If it's now greater then ... goto halfway between that point any the previous point you checked.

With 3000 records, it will take a maximum of 12 iterations to find the correct match or know if there isn't one.

If they're not sorted, then that idea's buggered.
<br>

[Ioannis]

Thanks Darrel. I understand what you are saying and this was my first idea too. But the group of data will be stored while the system is functioning in time and not at once. So when you are storing new data the old ones should be sorted again everytime. And everytime this is going to be slower. Calculations showed about 3 minutes for 2000 items so, no thanks!

A simple idea is to multiply the 3 bytes data together and do a mod(3000) then, but does produce conflicts.

I am doing a google search on the Hash Functions topic but all I have found up to this moment are big monsters in C that require at least 32-bit variables and Pentium processors!

Ioannis

[Darrel Taylor]

You wouldn't actually have to sort everything again when a new item is added.

Using the same Half-split idea, you can quickly find the point where the new record should be inserted. Then just move everything after it, down one location. Not sure how long the move would take though.

That way the lookup will be quick.

Just a thought.
<br>

[Ioannis]

Hmm, lets see. Worst case senario. If I have 2000 records of 3 bytes each, that would be 6000 bytes location in EEPROM. When a new key have to be stored and happens to be the first, then 6000 bytes have to be moved down 3 positions. 6000 x 10msec = 60 seconds!

Not taking into account the delays of the if-thens of the program. Within that time 2 or 3 drivers would require to leave the parking and go home for lunch too. Imagine their hurry while parking bar refuses to open!

Ioannis

[Darrel Taylor]

Hmm, lets see. Best case scenario.

You're using zero write time SPI FRAM, and the SSP module to communicate with it at 1Mbit/sec.

There are 3000 records of 3 bytes each. you have to transmit 2 address bytes to read or write and each byte is 8 bits. that's a total of 120,000 bits to shift out at 1Mbit/sec.

That's 0.12 seconds.
But of course you have to read each byte first before you can write it back in a new location, so we'll double that for 0.24 seconds.

Now add in the processing time on the PIC side, (not much when you're just reading and writing it back out again).

Should be able to do it in a half a second or so. My optimistic estimate.
<br>

[Ioannis]

I like very much optimist people!!!

Yes, this idea is good. I'll try to compute the processing time and use the page write functions of the EEPROMS.

OK. I'll be back!

Ioannis

[Darrel Taylor]

So here's what I got ...

4 Mhz OSC, 1 Mhz SPI Clk with SSP module, Ramtron FM25640 8K FRAM, 16F88
Moving 2,730 records of 3 bytes each. (close to 3,000, but all I got is 8K)

650 milliseconds

Rats, missed it by 0.15 sec. (I said .5 sec previously)

But, not a problem ...
8 Mhz OSC, 2 Mhz SPI Clk with SSP module

350 mS.

OR, ....
20 Mhz OSC, 5 Mhz SPI Clk

150 mS

Dang these FRAM's are fast. Doesn't miss a beat at 5 Mhz.

Never really had a chance to try them at high speed.

Cool!
<br>

[Ioannis]

Wow, that SPI chips are really very fast! Impressed!

Good work Darrel! Thanks!

Already ordered samples. I have handy the I2C ones but they cannot compare to the SPI!

Ioannis