UC3M

Grado en Ing. Telemática/Sist. Audiovisuales/Sist. de Comunicaciones

Arquitectura de Sistemas

Septiembre 2017 - Enero 2018

7.9.7. After_class: Modificar una tabla-hash de cadenas
Anterior 7.9. Actividades  Siguiente

7.9.7. After_class: Modificar una tabla-hash de cadenas

Recursos

  • Conocimientos sobre estructuras de datos dinámicas.

Plan de trabajo

Al laboratorio de I+D de SAUCEM S. L. ha llegado el siguiente fichero correspondiente a una tabla-hash: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#ifndef HASH_TABLE_WITH_STRINGS_H__ 
#define HASH_TABLE_WITH_STRINGS_H__


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct list_data
{
    char *data_string;
    char *key_string;
    struct list_data *next;
};

typedef struct list_data list_t;

struct hash_table_data 
{
    int size;           /* the size of the table */
    list_t **table;     /* the table elements    */
    int elements;       /*the number of elements   */
};

typedef struct hash_table_data  hash_table_t;

/**
 *  It creates a new (string) hash table.
 **/
 
hash_table_t *hash_table_create(int size);

/**
 *  Hash function
 **/
unsigned int hash(hash_table_t *hashtable, char *key_string);

/**
 *  It removes an element from the table
 **/
int hash_table_remove_data_string(hash_table_t *hashtable, char *key_string);

/**
 * It returns an element of the table. NULL if it is not found
 */

char* hash_table_lookup_data_string(hash_table_t *hashtable, char *key_string);

/**
 *It adds a new tuple in the hash table ((unique)key_string, data_string)
 */ 
int hash_table_add_data_string(hash_table_t *hashtable, char *key_string, char *data_string);

/**
 * Removing the hash table
 */
int hash_table_free(hash_table_t ** ptr_hashtable);

/**
 * Printing out all information (debuging)
 */ 
int hash_table_print(hash_table_t* hashtable);

/**
 *Resizing the table
 */
int hash_table_resize(hash_table_t* hashtable, int size);

#endif

Se corresponde con el código de una tabla-hash optimizada para cadenas de texto. La idea básica en una estructura de esta naturaleza es que consiste en una tabla (array) de listas, que permite acceso rápido a pares clave valor. Esto permite realizar búsquedas de forma mucho más eficiente que con otro tipo de estructuras, introduciendo una función de hash (que asocia elementos a una tabla inicial). Dicha función permite llegar al elemento que se quiere acceder de forma más sencilla.

Dispone de la siguiente implementación, fichero .c, correspondiente al anterior fichero .h: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
//
//gcc -Wall *.c -o data_string_hash_table
//valgrind ./data_string_hash_table
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash_table_with_strings.h"



/*create */
hash_table_t *hash_table_create(int size)
{
    int i;
    hash_table_t *new_table=NULL;    
    if (size<1)
    {
      return NULL;
    }
    /*space for the table */
    if ((new_table = calloc(1,sizeof(hash_table_t))) == NULL) 
    {
        return NULL;
    }        
    if ((new_table->table = calloc(1,sizeof(list_t*) * size)) == NULL) 
    {      
        free(new_table);
        return NULL;
    }
    /* Inicialization of the internal table */  
    for(i=0; i<size; i++) 
    {
      new_table->table[i] = NULL;
    }
    new_table->size = size;
    return new_table;
}

/*hash function to select the position of the array */ 
unsigned int hash(hash_table_t *hashtable, char *key_string)
 {
    if(hashtable==NULL)
    { 
      return 0;
    }
    if(key_string==NULL)
    { 
      return 0;
    }           
   unsigned int hashval=0;    
        
    for(; *key_string != '\0'; key_string++) 
    {
      hashval = *key_string + (hashval << 5) - hashval;    
    }
    return hashval % hashtable->size;
 }

 
/*Internal lookup_  */ 
list_t *hash_table_lookup_data_string_(hash_table_t *hashtable, char *key_string)
{
    if(hashtable==NULL)
    { 
      return NULL;
    }
    if(key_string==NULL)
    { 
      return NULL;
    }      
      
    list_t *list;
    unsigned int hashval = hash(hashtable, key_string);
    for(list = hashtable->table[hashval]; list != NULL; list = list->next) 
    {
        if (strcmp(key_string, list->key_string) == 0) 
	{
	  return list;
	}
    }
    return NULL;
}

/*remove  */ 
int hash_table_remove_data_string(hash_table_t *hashtable, char *key_string)
{
    if(hashtable==NULL)
    { 
      return -1;
    }
    if(key_string==NULL)
    { 
      return -2;
    }      
    
    list_t *list;
    list_t *prev;
    unsigned int hashval = hash(hashtable, key_string);
    
    for(list = hashtable->table[hashval], prev=NULL; list != NULL; prev=list, list = list->next) 
    {
        if (strcmp(key_string, list->data_string) == 0) 
	{
	  if(prev==NULL){
	    hashtable->table[hashval]=list->next;	    
	  }else{
	    prev->next=list->next;	  
	  } 
	 free(list->data_string);
	 free(list->key_string);
	 free(list);
	 hashtable->elements--;
	 return 0;
	}
    }
    return -1;
}


/* lookup */
char* hash_table_lookup_data_string(hash_table_t *hashtable, char *key_string)
{      
  list_t* ptr=hash_table_lookup_data_string_(hashtable,key_string);
  
  if(ptr==NULL)
  {
    return NULL;
    
  }
  else
  {  
    return ptr->data_string;  
  }
}

/* Adding element */ 
int hash_table_add_data_string(hash_table_t *hashtable, char *key_string, char *data_string)
{
    if(hashtable==NULL)
    { 
      return -1;
    }
    if(key_string==NULL)
    { 
      return -2;
    }      
    if(data_string==NULL)
    { 
      return -3;
    }   
    list_t *new_list=NULL;
    list_t *current_list=NULL;
    unsigned int hashval = hash(hashtable, key_string);
    if ((new_list = malloc(sizeof(list_t))) == NULL) 
    {     
      return -1;
    }
    current_list = hash_table_lookup_data_string_(hashtable, key_string);
    if (current_list != NULL)
    {
      return -2;
    }
    /* Insert into list by the head */
    new_list->key_string = strdup(key_string);
    new_list->data_string = strdup(data_string);
    new_list->next = hashtable->table[hashval];
    hashtable->table[hashval] = new_list;
    hashtable->elements++;
    return 0;
}

/* Removing */ 
int hash_table_free(hash_table_t ** ptr_hashtable)
{   /*Safety issues*/
    if(ptr_hashtable == NULL)
    {
      return -1;
      
    }
    hash_table_t* hashtable=NULL;
    hashtable= (*ptr_hashtable);
    if (hashtable == NULL) 
    { 
      return -2;
    }
    int i=0;
    list_t *list;
    list_t *temp;    
    for(i=0; i<hashtable->size; i++) 
    {
        list = hashtable->table[i];
        while(list!=NULL) {
            temp = list;
            list = list->next;
            free(temp->data_string);
	    free(temp->key_string);
            free(temp);
	    hashtable->elements--;
        }
    }
    /* Free the table itself */
    free(hashtable->table);
    free(hashtable);
    (*ptr_hashtable)=NULL;
    return 0;
}

/* Printing out the table */ 
int hash_table_print(hash_table_t* hashtable)
{
   if(hashtable==NULL)
    { 
      return -1;
    }
    
    int aux_printing=0;
    int i=0;
    list_t *list=NULL;

    if (hashtable == NULL) 
      { 
	return 0;
      }
    
    for(i=0; i<hashtable->size; i++)  
      {
        list = hashtable->table[i];
        while(list!=NULL) 
	{
            printf("\n[%d][%d](key,value):\t \%20s : \%20s",i, (aux_printing++),
		   list->key_string,list->data_string);	   
            list = list->next;
        }
      }    
  return 0 ;    
}

/*resize*/
int hash_table_resize(hash_table_t* hashtable, int size)
{
  if(hashtable==NULL)
  {
    return -1;
  }
  if(size<0)
  {
    return -2;
  }  
  //Creating and isolated 
  hash_table_t* ht2=hash_table_create(size);
  int i=0;
  list_t *list;
  list_t *temp;    
  for(i=0; i<hashtable->size; i++) 
    {
        list = hashtable->table[i];
        while(list!=NULL) 
	{
            temp = list;
            list = list->next;
	    hash_table_add_data_string(ht2,temp->key_string,temp->data_string);
            free(temp->data_string);
	    free(temp->key_string);
	    free(temp);		    
	}
    }
  free(hashtable->table);  
  (*hashtable)=(*ht2);
  free(ht2);
  return 0;
}


int main()
{
  printf("\n ***Checking the code \n");
  printf("\n ***Creating hash table with 1 queue \n");
  hash_table_t* h1 =hash_table_create(1);
  printf("\n ***Adding 4 elements \n");
  hash_table_add_data_string(h1,"uno","1");
  hash_table_add_data_string(h1,"one","1");
  hash_table_add_data_string(h1,"two","2");
  hash_table_add_data_string(h1,"two","22"); //It should fail
  hash_table_add_data_string(h1,"three","3");
  hash_table_add_data_string(h1,"four", "4");
  
  hash_table_remove_data_string(h1,"uno");
  char* element_two=NULL;
  element_two=hash_table_lookup_data_string(h1,"two");
  if (element_two!=NULL)
  {
    printf ("\n *** Element \"two\" is: %s", element_two);
  }
  
  
  printf("\n***Dumping the queue \n");
  hash_table_print(h1);
  printf("\n***Resizing the table to 4 queues \n");    
  hash_table_resize(h1,4);
  printf("\n***Dumping the queue \n");
  hash_table_print(h1);  
  printf("\n***Releasing the hashtable \n");
  hash_table_free(&h1);
  return 0; 
}

Haciendo uso de ambos ficheros, le piden que:

  1. Se baje el código, lo analice y lo pruebe hasta entenderlo. Intente almacenar muchos elementos. ¿Por qué existe una función de resize? ¿Qué ventaja puede aportar?

  2. Intente modificar el código para que la tabla interna de la tabla hash se redimensione automáticamente. Al equipo de SAUCEM le parece bien que cuando la tabla tenga una ocupación mayor del 0.75 se duplique su tamaño y cuando sea menor del 0.25 se reduzca a la mitad.

  3. También le piden que use el código inicial para implementar una aplicación de logística que contenga elementos correspondientes a un carro de la compra. Por cada elemento deberá de guardar la cantidad de elementos disponibles en el almacén, precio de cada ítem y descripción textual del producto: 

     struct item{
	   int amount_available;
	   int produc_id;
	   char* produc_description;
	   float price;
	   };

    Le piden también realizar una aplicación de prueba que permita a un usuario realizar las siguientes operaciones: (1) Añadir un nuevo producto, (2) eliminar un producto y (3) modificar la cantidad de elementos que hay de un ítem.

  4. Intente reaprovechar la estructura una vez más para que en vez de almacenar una cadena de texto, almacene la siguiente estructura de datos referente a la información de una WIFI, descrita tal y como sigue: 

    enum network_mode 
{
    Auto,
    AdHoc,
    Managed,
    Master,
    Repeater,
    Secondary,
    Monitor,
    Unknown
};

struct ap_scan_info
{
    unsigned char mac[6];        // Cell MAC
    char essid[15];              // ESSID
    enum network_mode mode;      // Operation mode (enumeration)
    int channel;                 // Channel for transmission
    unsigned short encrypted;    // Boolean stating if net is encrypted 
    unsigned int quality[2];     // Two integers stating quality current and max
 };

    Pistas: Para ello tendrá que cambiar la clave que utiliza para calcular la función de hash. Le recomendamos que utilice la MAC que es un identificador único de la red y como clave de la tabla. Le piden también un programa, de prueba, que introduzca 10000 elementos en la tabla-hash. ¿Cuánto tarda en realizarse una búsqueda? ¿Cuanto tardaría con una única lista (Nota: puede probarlo haciendo un resize de 1 sobre el array inicial de la tabla)?

  5. Por último, le piden que generalice su código, para poder reutilizarlo en prototipos futuros de la empresa. Intente generalizar el código que le dan haciendo que la parte dependiente del dato (i.e. creación, destrucción, volcado de datos) sea parametrizable. Para eso los laboratorio de SAUCEM han pensado en utilizar la técnica de punteros a funciones y le piden que añada esta solución a su código. El equipo ha estimado que necesita un puntero a función de int hash(void* key) (dependiente de la aplicación realizada y los datos), esta función se pasará como parámetro cuando se cree la tabla hash: int hash_table_create(int size, int (*hash_routine) (void *))). También creen que se pueden añadir punteros opcionales para imprimir un nodo y borrarlo.

Anterior Subir Siguiente
7.9.6. Borrar nodos de una lista encadenada  Inicio 7.9.8. Insertando y persistiendo una tabla-hash
© Universidad Carlos III de Madrid | Licencia Creative Commons