Embedded C programming Tutorial , Keil C ide , microsoftware.gr
Keil CRC and CAN BUS codes.
1. Shift led left
2.It's time for DAVE! <7/6/13>
3.Capture/Compare unit 6
6.Analog converter
7.Memory manipulation routines
8. Recursion
9.Understanding interrupt priorities using CAPCOM2 module
10. POINTERS TO FUNCTION <4/7/13>,<4/28/13>
11.Memory models, memory types
12. The heap , part 1
13. The heap , part 2
14. The heap , part 3
15. Structure example
16. Nested structures, Array of structures.
17. Passing array of structures to function using pointers.<1/5/13>
18. Self Referential Structures
20. Linked list example
21. Circular linked list
22. Union example
23. Enumeration example
24. Watchdog timer example
25. Void pointer example <7/4/13>
26. The sieve of Eratosthenes
27. The stack
28. Union and bitfields as flags example. <6/23/13>
29. Look up table example. <8/11/13>
30. Seven segment display multiplexing -four digits with dot- example
31. LCD character display example - JHD162A
32. Hash table introduction example <8/27/14>
33. Array of Linked Lists example
34. Array of Linked lists-more functions included.
35. Hash table construction,searching and printing.
36. Fininte state machines- a first approach.
37. Finite state machines- two events example.
38. SPI port and an AT25128 serial eeprom hardware.
40. Definite Integral Calculator for Scientists, Engineers...
41 .Hamming distance of a CRC polynomial
42. Linux play starting.
43. Galois GF(2^4) Finite Field
44. Construct your own time triggered real time operating system.
32. Hash table introduction example <8/27/14>

This article is a Hash table example.

Having an array r[] , you know that: r=&r[0] , r+1=&r[1], r+2=&r[2] ...and so on. The pointers r, r+1, r+2... are called the indexes of the elements of the array and *r=r[0], *(r+1)=r[1],  *(r+2)=r[2] and so on.

The problem:" Having an array, index the elements of the array in accordance to a specified correspondence".

An example:  Given the array r={30,31,32,33,62}  we will  index the elements of the array in accordance to the remainder of the division of the elements by 30.

We have:
Element        remainder       index          result  

30              30%30=0        r+0           *(r+0)=30      correct!

31              31%30=1        r+1           *(r+1)=31      correct!

32              32%30=2        r+2           *(r+2)=32      correct!

33              33%30=3        r+3           *(r+3)=33      correct!

62              62%30=2        r+2           *(r+2)=62 ???   false!!!

The element of the array play the rolle of a key. We insert the key to a function, called
Hash function that produces the index of the element.
The process is called Hashing , the Hash keys are not needed to be exclusively the elements of the array but may be any data type refered to the elements of the array (a float, a string, a structure etc). The collection of the produced indexes is called a Hash table.

Now back: As you see we have two different keys 32 and 62 that produce throught our Hash function the same index , r+2. The phenomenon is called a collision.

To avoid collision we prefer to index not a simple array but an array of arrays or an array of Linked lists (An array of linked lists is preferable because we can add new nodes at a linked list "on the fly" inserting at these new nodes the elements of the array that produce collisions).

So indexing this array of arrays:  int *(a[10])[2]={{30},{31},{32,62},{33}} and using the same as above Hash (function? No!) criterion :

unsigned int  Hash_function (unsigned int key)
                                                          return (key%30)

we can find (with what Hash function?)  the indexes : a[0] , a[1], a[2] , a[2]+1 , a[3]    .

Indeed, *a[0]=30 , *a[1]=31 , *a[2]=32 ,  *(a[2]+1)=62  , *a[3]=33  avoiding collisions.

So have a look a t the        result       and study about the     C code    to understand.

Given the array  int a[4]={33,32,31,30}; index the elements of the array in accordance to the remainder of the division of the elements by 30.

Our Hash function is the:
 int * Hash_function (int r)
 int* p ;
 printf("the element divided by 30 and having remainder %u has index a+%u  and is the %u\n\n",r,3-r,*p);
 return p;


Our keys are the integers r, the remainders of the divisions of the elements  by 30.
we have:

key=0   index  a+3
key=1   index  a+2
key=2   index  a+1
key=3   index  a+0

The C code                 Result at Hyperterminal

Further reading :