Convert sha256 to smaller uint type

user_12287100 0
Viewed 150

I'm implementing a hash table in c and I chose as key the sha256 hash of the file that I need to store. The problem is that I need to convert the key to a reusable index to insert in the hash table. I tought to rehash the key, but this way I would increase the possibility of overlapping values. Is there a way to use this hash as the key to the table?

The sha256 is store as a BYTE[32] or can be converted as a sting

void* ht_get(ht* table, const char *key) {
    size_t index = magicfunction(key);

    while (table->entries[index].key != NULL) {
        if (strcmp(key, table->entries[index].key) == 0) {
            // Found key, return value.
            return table->entries[index].value;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->capacity) {
            index = 0;
        }
    }
    return NULL;
 }
sha256 hashtable c
1 Answers

When I need an absolute minimalist hashmap in C, I usually end up doing something like that:

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

struct hmap_entry {
  const char *key;
  /* Or in your case: */
  /* char key[SIZE_OF_SHA256]; */

  void *payload;
};

#define HMAP_ENTRY_CNT 256
struct hmap {
  struct hmap_entry entries[HMAP_ENTRY_CNT];
};

static size_t str_hash(const char *s) {
  size_t hash = 0;
  while(*s) {
    hash = (hash << 7) ^ (size_t)*s++ ^ hash;
  }
  return hash;
}

static struct hmap_entry *hmap_search_entry(struct hmap *map
    , const char *key)
{
  size_t hash = str_hash(key);
  /* Or in your case: */
  /* size_t hash = 0; memcpy(&hash, key, sizeof(key)) */

  hash = hash % HMAP_ENTRY_CNT;

  struct hmap_entry *e = NULL;
  while(1) {
    e = map->entries + hash;

    if(e->key == NULL
        || strcmp(key, e->key) == 0) {
      break;
    }
    /* Or in your case: */
    /* if(e->key == NULL
          || memcmp(key, e->key, SIZE_OF_SHA256) == 0) {
        break;
       }
     */


    hash = (hash + 1) % HMAP_ENTRY_CNT;
  }
  return e;
}

And this is how I use it:

int main()
{
  struct hmap_entry *e;
  struct hmap map = {};

  /* insert foo */
  e = hmap_search_entry(&map, "foo");
  e->key = "foo";
  e->payload = "hello world";

  /* insert bar */
  e = hmap_search_entry(&map, "bar");
  e->key = "bar";
  e->payload = "Something else";

  /* get foo */
  e = hmap_search_entry(&map, "foo");
  if(e->key) {
    printf("Value of \"%s\" is \"%s\"\n", e->key, (const char *)e->payload);
  }
  else {
    printf("Not found!\n");
  }

  /* get bar */
  e = hmap_search_entry(&map, "bar");
  if(e->key) {
    printf("Value of \"%s\" is \"%s\"\n", e->key, (const char *)e->payload);
  }
  else {
    printf("Not found!\n");
  }

  /* get test */
  e = hmap_search_entry(&map, "test");
  if(e->key) {
    printf("Value of \"%s\" is \"%s\"\n", e->key, (const char *)e->payload);
  }
  else {
    printf("Not found!\n");
  }

  return 0;
}
user_92053990
Related