commit b870f7276c79356b0cacce012f3d04f25ca7a406
parent cf1d09cb5650940d5d80fbfc37214b8fc6baab42
Author: x0tero <gxoelotero@gmail.com>
Date: Tue, 5 Mar 2024 11:34:47 +0100
hashTable, hashMap ou diccionario en C
Diffstat:
1 file changed, 199 insertions(+), 0 deletions(-)
diff --git a/hashTable/hash_table.c b/hashTable/hash_table.c
@@ -0,0 +1,198 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define TABLE_SIZE 5
+
+typedef struct ENTRY {
+ char* key;
+ char* value;
+ struct ENTRY* sig;
+} ENTRY_T;
+
+typedef struct {
+ ENTRY_T** entries;
+} HTABLE_T;
+
+
+
+HTABLE_T* htable_init() {
+ HTABLE_T* hashtable = malloc(sizeof(HTABLE_T)); // Allocate HashTable
+ hashtable->entries = calloc(TABLE_SIZE, sizeof(ENTRY_T)); // Allocate entries
+
+ // Set each entry to NULL (needed for proper operation)
+ for (int i = 0; i < TABLE_SIZE; i++) {
+ hashtable->entries[i] = NULL;
+ }
+
+ return hashtable;
+}
+
+
+
+unsigned int hash(const char* key) {
+ unsigned long int value = 0;
+
+ for (unsigned int i = 0; i < strlen(key); i++){
+ value = value * 37 + key[i];
+ }
+ value = value % TABLE_SIZE;
+ return value;
+}
+
+
+
+// Inicializa un nodo entry
+ENTRY_T* htable_pair(const char* key, const char* value){
+ // Allocate the entry
+ ENTRY_T* entry = malloc(sizeof(entry));
+ entry->key = malloc(strlen(key)+1); // +1 polo NULL TERMINATOR '\0'
+ entry->value = malloc(strlen(value) + 1);
+
+ // Copy the key and value in place
+ strcpy(entry->key, key);
+ strcpy(entry->value, value);
+
+ // sig (seguinte) starts out NULL but may be set later on
+ entry->sig = NULL;
+ return entry;
+}
+
+
+void htable_set (HTABLE_T* hashtable, const char* key, const char* value) {
+ unsigned int slot = hash(key);
+ ENTRY_T* entry = hashtable->entries[slot];
+
+ if (entry == NULL) {
+ hashtable->entries[slot] = htable_pair(key, value);
+ return;
+ }
+
+ // Mira se estas intentando introducir unha clave que xa tes no hashTable para actualizala
+ ENTRY_T* prev;
+ while (entry != NULL) {
+ // Comproba
+ if (!strcmp(entry->key, key)) {
+ // Update value
+ free(entry->value);
+ entry->value = malloc(strlen(value) + 1);
+ strcpy(entry->value, value);
+ return;
+ }
+
+ // walk to next
+ prev = entry;
+ entry = prev->sig;
+ }
+
+ // End of node list reached -> add new element
+ prev->sig = htable_pair(key, value);
+}
+
+
+// Devolve NULL senon existe
+char* htable_get(HTABLE_T* hashtable, const char* key) {
+ unsigned int slot = hash(key);
+
+ // Try to find a valid slot
+ ENTRY_T* entry = hashtable->entries[slot];
+
+ // No slot means no entry
+ if (entry == NULL) return NULL;
+
+ // Walk through each entry in the slot, which could just be a single thing
+ while (entry != NULL) {
+ // Return a value if found
+ if (!strcmp(entry->key, key) == 0) {
+ return entry->value;
+ }
+
+ // Proceed to next key if available
+ entry = entry->sig;
+ }
+
+ // Reaching here means there were >= 1 entries but no key match
+ return NULL;
+}
+
+
+void htable_remove(HTABLE_T* hashtable, const char* key) {
+ unsigned int slot = hash(key);
+ // Try to find a valid slot
+ ENTRY_T* entry = hashtable->entries[slot];
+ ENTRY_T** tmp = &(hashtable->entries[slot]);
+ if (entry == NULL) return;
+
+ // Se esta na cabeza e ten sig deixas o sig a cabeza
+ // Senon ten sig borraslle a cabeza
+ if (!strcmp(entry->key, key)) {
+ if (entry->sig == NULL) {
+ hashtable->entries[slot] = NULL;
+ free(entry);
+ }
+ else {
+ hashtable->entries[slot] = entry->sig;
+ free(entry);
+ }
+ }
+ else {
+ ENTRY_T* aux;
+ while (*tmp != NULL) {
+ if (!strcmp((*tmp)->key, key)) {
+ // Borrar a entry
+ aux = *tmp;
+ *tmp = (*tmp)->sig;
+ return;
+ }
+ tmp = &((*tmp)->sig);
+ }
+ }
+ return;
+}
+
+
+void htable_print(HTABLE_T* hashtable) {
+ for (int i = 0; i < TABLE_SIZE; i++) {
+ ENTRY_T* entry = hashtable->entries[i];
+
+ if (entry == NULL) continue;
+
+ printf("slot[%4d]: ", i);
+ for(;;) {
+ printf("%s=%s ", entry->key, entry->value);
+
+ if(entry->sig == NULL) break;
+ entry = entry->sig;
+ }
+
+ printf("\n");
+ }
+}
+
+
+
+int main() {
+ HTABLE_T* ht = htable_init();
+
+ htable_set(ht, "name1", "em");
+ htable_set(ht, "name2", "russian");
+ htable_set(ht, "name3", "pizza");
+ htable_set(ht, "name4", "doge");
+ htable_set(ht, "name5", "pyro");
+ htable_set(ht, "name6", "joost");
+ htable_set(ht, "name7", "kalix");
+ htable_set(ht, "name8", "lemon");
+ htable_set(ht, "name9", "lollipop");
+ htable_set(ht, "name10", "oreo");
+ htable_set(ht, "name11", "apache");
+ htable_set(ht, "name12", "fanta");
+ htable_set(ht, "name13", "kake");
+ htable_set(ht, "name14", "tuna");
+ htable_set(ht, "name15", "presunto");
+
+ htable_remove(ht, "name7");
+ htable_remove(ht, "name2");
+
+ htable_print(ht);
+ return 0;
+}
+\ No newline at end of file
