## What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the hashtable)

## Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer.

I get how the values are added before the hashtable is resized… that is common sense. (Insert 0 at index 3, 5 at index 1, etc.)

But when the table is resized, each element has a new position. HOW is 1’s new index 0? HOW is 5’s new index 7? How did each element of the array get assigned their new index upon table resize?

Any help would be appreciated.

Thanks

## Independence of order of insertion hashtable with open addressing

I’m taking a data-structure class, and the lecturer made the following assertion:

the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order.

No proof was given, so I tried to get one myself. However, I’m stuck.

My approach at the moment: I try to show that if I swap two adjacent keys the number of attempts doesn’t change. I get the idea behind it, and I think it’s going in the right direction, but I can’t manage to make it into a rigorous proof.

Aside, does this fact also hold for other probing techniques such as quadratic or double hashing?

## Do all the numbers belong to same slot in the Hashtable?

I was reading the CLRS.In the Hashing Chapter on page 262 a statement says: For example, if we know that the keys are random real numbers k independently and uniformly distributed in the range $$0 \leq k < 1$$, then the hash function $$h(k)= \lfloor km \rfloor$$

Question: Does Uniformly distributed meant all numbers have equal probability. if so then all numbers have the same $$k$$ values and belong to the same slot.

## Obtener un elemento de hashtable

Tengo un diccionario en el cual me piden que muestre definición a través de una palabra ingresada por el usuario. Por lo tanto la palabra ingresada la capturó en una variable llamada ‘entrada’ de tipo string.

Hashtable diccionario = New Hashtable(); Float valor; String entrada; Console.Write("ingrese la palabra"); entrada = Console.ReadLine(); valor = (float) diccionario.Item[entrada]; 

Bueno el problema es que yo espero que me devuelva en que posición se encuentra el key(entrada) y eh visto que en el visual studio 2010 estaría bien la sentencia. Pero en mi caso tengo visual studio 2012 y me muestra error en el: Diccionario.Item ¿De que otra forma podría intentarlo? Ya que necesito obtener la posición para mostrar el (key, value) del hashtable

## Iterable hashtable implementation in C

I’m just finished my version of iterable hashtable. I want to review code in general (code style, data structures, remarks about the algorithms) and I have some questions:

1. I don’t know how to implement errors in return-value way. So, I chose way when we contain error flag variable in struct. Is it correct?
2. What functions are missing in interface? Maybe pop() or something like this?
3. Where do I need includind headers like stddef.h or string.h? (e.g. I don’t use functions from string.h in my header, do I need include it in htable.h?)

htable.h:

#ifndef HTABLE_H #define HTABLE_H #include <stdio.h> #include <stddef.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <stdbool.h>  typedef struct node_t {     void* el;     struct node_t* nextp; } node_t;  typedef enum hterror_t {     HTE_OK,     HTE_MEM_EXHAUST,     HTE_REMOVE,     HTE_TOTAL } hterror_t;  typedef struct index_t index_t;  enum { HTABLE_SIZE = 8191 }; typedef struct htable_t {     node_t*    table[HTABLE_SIZE];     index_t*   indexes;     hterror_t  err_f;      uint32_t   (*hash)(void *);     int32_t    (*cmp)(void *, void *); } htable_t;  htable_t*  htable_create(uint32_t (*hash)(void *), int32_t (*cmp)(void *, void *)); node_t*    htable_lookup(htable_t* ht, void* el, bool create); void       htable_remove(htable_t* ht, void* el); void       htable_foreach(htable_t* ht, void (*fn)(node_t *, void *), void *arg); void       htable_destroy(htable_t* ht);  #endif // HTABLE_H 

htable.c:

#include "htable.h"  typedef struct index_t {     size_t index;     struct index_t* nextp; } index_t;  htable_t* htable_create(uint32_t (*hash)(void *), int32_t (*cmp)(void *, void *)) {     htable_t* htable = malloc(sizeof(htable_t));     if (htable == NULL)         return NULL;      memset(htable->table, 0, sizeof(htable->table[0]) * HTABLE_SIZE);     htable->indexes = NULL;     htable->err_f   = HTE_OK;     htable->hash    = hash;     htable->cmp     = cmp;      return htable; }  node_t* htable_lookup(htable_t* ht, void* el, bool create) {     node_t*   tmp;     uint32_t  h;      h = ht->hash(el) % HTABLE_SIZE;     for (tmp = ht->table[h]; tmp != NULL; tmp = tmp->nextp)         if (ht->cmp(tmp->el, el) == 0)             return tmp;      if (create) {         if (ht->table[h] == NULL) { /* if there's no node for hash h */             index_t* ni = malloc(sizeof(index_t));             if (ni == NULL) {                 ht->err_f = HTE_MEM_EXHAUST;                 return NULL;             }             ni->index = h;             ni->nextp = ht->indexes;             ht->indexes = ni;         }          node_t* newnode = malloc(sizeof(node_t));         if (newnode == NULL) {             ht->err_f = HTE_MEM_EXHAUST;             return NULL;         }         newnode->el = el;         newnode->nextp = ht->table[h];         ht->table[h] = newnode;     }      return tmp; }  void htable_remove(htable_t* ht, void* el) {     node_t*  p, * prev;     uint32_t h;      h = ht->hash(el) % HTABLE_SIZE;      prev = NULL;     for (p = ht->table[h]; p != NULL; p = p->nextp) {         if (ht->cmp(p->el, el) == 0) {             if (prev == NULL)                 ht->table[h] = p->nextp;             else                 prev->nextp = p->nextp;             free(p);             return ;         }         prev = p;     }      ht->err_f = HTE_REMOVE; }  void htable_foreach(htable_t* ht,                     void (*fn)(node_t *, void *), void *arg) {     index_t* prev, * p;     node_t*  cur_n;      prev = NULL;     for (p = ht->indexes; p != NULL; p = p->nextp) {         if (ht->table[p->index] == NULL) {             if (prev == NULL) {                 ht->indexes = p->nextp;                 free(p);                 p = ht->indexes;             } else {                 prev->nextp = p->nextp;                 free(p);                 p = prev;             }         }          for (cur_n = ht->table[p->index]; cur_n != NULL; cur_n = cur_n->nextp)             fn(cur_n, arg);     } }  void htable_destroy(htable_t* ht) {     index_t* buf_i;      for (; ht->indexes != NULL; ht->indexes = buf_i) {         buf_i = ht->indexes->nextp;         if (ht->table[ht->indexes->index] != NULL) {             node_t* buf_n;             for (; ht->table[ht->indexes->index] != NULL; ht->table[ht->indexes->index] = buf_n) {                 buf_n = ht->table[ht->indexes->index]->nextp;                 free(ht->table[ht->indexes->index]);             }         }          free(ht->indexes);     }      free(ht); } 

Simple usage of htable:

#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <math.h> #include "htable.h"  /* ihash and icmp are needed for construct htable */ uint32_t ihash(void* y) {     uint32_t x = *(uint32_t *) y;     x = ((x >> 16) ^ x) * 0x45d9f3b;     x = ((x >> 16) ^ x) * 0x45d9f3b;     x =  (x >> 16) ^ x;     return x; }  int32_t icmp(void* a, void* b) {     return *(int *) a - *(int *) b; }  /* icopy, ifree and iprint are not necessary */ void* icopy(void* i) {     int* _i = malloc(sizeof(int));     if (_i == NULL)         return NULL;     *_i = *(int *) i;      return _i; }  void ifree(node_t* n, void* arg) {     (void) arg;     if (n->el != NULL)         free(n->el); }  void iprint(node_t* np, void* arg) {     printf((char *) arg, (np == NULL) ? 0 : *(int *) np->el); }  int main() {     htable_t* ht = htable_create(ihash, icmp);     for (int i = 0; i < 255; ++i)         htable_lookup(ht, icopy(&i), true);      int k = 12;     iprint(htable_lookup(ht, &k, false), "lookup: %d\n");     ifree(htable_lookup(ht, &k, false), NULL);     htable_remove(ht, &k);     iprint(htable_lookup(ht, &k, false), "lookup: %d\n"); /* returns NULL */     htable_foreach(ht, iprint, "foreach: %d\n");     htable_foreach(ht, ifree, NULL); /* freeing memory that we allocated from the loop above */     htable_destroy(ht);      return 0; } 

## Hashtable implementation in C for generic values

I am trying to implement a hashtable that supports character keys and can return any type of value contained in a struct as long as it contains as long as it contains Bucket as one of its members.

The user has to supply the size of the hashtable (preferrably a large enough prime number) in the calling function.

It uses sdbm as a hash function. (Maybe adding a function pointer to let the user specify the kind of hash function they want to use could be a flexible option?)

Any code improvements/suggestions are welcome.

It uses a chaining mechanism using linked lists.

Here is the prototype:

#ifndef HASHTABLE_H #define HASHTABLE_H  #include "../linked_list/linked_list.h" #include <stdlib.h> #include <string.h> #include <stddef.h>  #define HT_INIT_FAILURE -1 #define HT_INIT_SUCCESS 0  #define HT_MAGIC_SIZE 997  typedef struct bucket {   char * key;   LL_Node ll_node; } Bucket;  typedef struct hashtable {   Bucket ** buckets;   unsigned int size; } Hashtable;   int hashtable_init(Hashtable * hashtable, int size); void hashtable_put(Hashtable * hashtable, char * key, Bucket * bucket); int hashtable_key_exists(Hashtable * hashtable, char * key); void hashtable_close(Hashtable * hashtable); Bucket * __hashtable_get_bucket(Hashtable * hashtable, char * key);  #define hashtable_get_value(bucket, struct_type, struct_member)     \   ((struct_type *)((char *)(bucket) - (unsigned long)(offsetof(struct_type, struct_member))))  #define hashtable_get(hashtable, key, struct_type, struct_member)   \   hashtable_get_value(__hashtable_get_bucket(hashtable, key), struct_type, struct_member);  #endif 

hashtable.c

#include "hashtable.h"  int hashtable_init(Hashtable * ht, int size) {   if ((ht->buckets = (Bucket **) malloc (sizeof(Bucket *) * size)) == NULL)     return HT_INIT_FAILURE;   ht->size = size;    for (int i = 0; i < size; i++)     ht->buckets[i] = NULL;    return HT_INIT_SUCCESS; }  unsigned long __hash_sdbm(char *str) {   unsigned long hash = 0;   int c;    while ((c = *str++))     hash = c + (hash << 6) + (hash << 16) - hash;    return hash; } int __key_matches(char * source, char * target) {   return (strcmp(source, target) == 0); }  void __insert_bucket(Hashtable * hashtable, int index, Bucket * bucket) {   if (hashtable->buckets[index] == NULL) {      LL_Node * head = &bucket->ll_node;       ll_create_list(head);     hashtable->buckets[index] = bucket;   }   else {      LL_Node * head = &(hashtable->buckets[index]->ll_node);     LL_Node * ptr = head;     int head_key_matches = (__key_matches(bucket->key,                       hashtable->buckets[index]->key));      Bucket * search_bucket;      ll_foreach(ptr, head) {        search_bucket = ll_get(ptr, Bucket, ll_node);        if (head_key_matches || __key_matches(bucket->key, search_bucket->key)) {          ll_replace(ptr, &bucket->ll_node);      return;        }          }     ll_push_front(head, &(bucket->ll_node));   } }  void hashtable_put(Hashtable * ht, char * key, Bucket * bucket) {   int index = __hash_sdbm(key) % ht->size;   bucket->key = key;   __insert_bucket(ht, index, bucket); }  Bucket * __hashtable_get_bucket(Hashtable * hashtable, char * key) {   int index = __hash_sdbm(key) % hashtable->size;      if (hashtable->buckets[index] == NULL)     return NULL;    Bucket * bucket = hashtable->buckets[index];    if (__key_matches(bucket->key, key)) {     return bucket;   }    else {     LL_Node * ptr;     LL_Node * head = &(hashtable->buckets[index]->ll_node);      ll_foreach(ptr, head) {       bucket = ll_get(ptr, Bucket, ll_node);       if (__key_matches(key, bucket->key)) {     return bucket;       }     }     return NULL;   } }  int hashtable_key_exists(Hashtable * ht, char * key) {   return (__hashtable_get_bucket(ht, key) == NULL); }  void hashtable_close(Hashtable *ht) {   free(ht->buckets);   ht->size = 0; } 

Here is an example of how it can be used:

#include "hashtable.h" #include <stdlib.h> #include <stdio.h>  typedef struct entry_t {   int val;   Bucket bucket;   } Entry;  int main() {   Hashtable hashtable;   Hashtable * ht = &hashtable;    if (hashtable_init(ht, 10) == HT_INIT_FAILURE)     return EXIT_FAILURE;    Entry * entry = (Entry *) malloc(sizeof(Entry));   entry->val = 10;    hashtable_put(ht, "john", &(entry->bucket));    Entry * res;    Entry * entry2 = (Entry *) malloc(sizeof(Entry));   entry2->val = 12;    hashtable_put(ht, "pan", &(entry2->bucket));    Entry * entry3 = (Entry *) malloc(sizeof(Entry));   entry3->val = 15;    hashtable_put(ht, "tran", &(entry3->bucket));    res = hashtable_get(ht, "john", Entry, bucket);   printf("%d\n", res->val);    res = hashtable_get(ht, "pan", Entry, bucket);   printf("%d\n", res->val);    res = hashtable_get(ht, "tran", Entry, bucket);   printf("%d\n", res->val);    Entry * entry4 = (Entry *) malloc(sizeof(Entry));   entry4->val = 100;    hashtable_put(ht, "pan", &(entry4->bucket));    res = hashtable_get(ht, "john", Entry, bucket);   printf("Replaced\n%d\n", res->val);    res = hashtable_get(ht, "pan", Entry, bucket);   printf("%d\n", res->val);    res = hashtable_get(ht, "tran", Entry, bucket);   printf("%d\n", res->val);    if (hashtable_key_exists(ht, "trans"))     printf("Doesn't exist");   else     printf("Exists");    if (hashtable_key_exists(ht, "tran"))     printf("Doesn't exist");   else     printf("Exists");    free(entry);   free(entry3);   free(entry2);   free(entry4);    hashtable_close(ht);    return EXIT_SUCCESS; } 

Please excuse the lazily written test main function.

## Any quick way in Python to create and access a hashtable?

I am trying to implement a LHS pattern match with a RHS action code in Python How can I get a fast hashtable match. Is this possible in Python? I need to fast match features in terms of x,y,c where x and y are coordinates and c is the color at index(x,y) of a 2d array.

## Unable to pass Set-PnPListItem a hashtable as value

Set-PnPListItem should set users in list fields but I can’t get the format right. Usually, I would set it like documented, i.e. @{"PersonField" = "user1@domain.com","21"}.

However, in my case each list item could have different fields to be updated. Therefore, the hashtable might contain different key-value-pairs for each list item. That’s why I need to be able to pass -Value the hashtable itself.

Now, trying to pass a hashtable like this results in ‘ The specified user could not be found.’ :

It seems the error is not due to the hashtable containing multiple pairs. I tried a hashtable with only one pair and the error is the same. Could it have to do with the values not being treated as strings?

Do you have any idea how I can get it to work? Thanks a lot.

EDIT:

So by trial and error I found a workaround but I have no idea why it has to be that way.

The way I populate the hashtable seems to make a difference. What’s not working was:

EDIT: So by trial and error I found a workaround but I have no idea why I have to do what I have to do for it to work.

Doing the following does not work with Set-PnPListItem -List $list -Identity [...] -Values$ updates:

$updates = @{} if ($ null -ne $currentSiteOwners) {$ updates.Owner = $currentSiteOwners() } However, using the .ToLower() method makes it work: $ updates = @{} if ($null -ne$ currentSiteOwners) { $updates.Owner =$ currentSiteOwners.ToLower() }

The fact that the .ToLower()method converts the id’s contained in \$ currentSiteOwners to lower case cannot be the reason as they are not letters to begin with. The method must be performing some kind of string transformation that -Valueultimately accepts.

Anyone any clue?

## HashTable using C

Introduction

This is my first attempt to mess with memory allocation using C and create something close to a python dictionary. Coming from a high level programming language like python/java, I am not really used to correctly handling low level code. I tried to follow c conventions/style but I can tell I already failed that since I lack the discipline required.

#include <stdio.h> #include <stdlib.h> #include <string.h>  #define HASH_TABLE_SIZE 255 #define DEBUG_HASH_INDEX 0  // for debugging with predictable indexes  typedef struct HashItem HashItem;  struct HashItem {   char * key;   char * value;   HashItem * tail; };   void freeNode(struct HashItem * node);   void initialize_hash_table(HashItem * hash_table[]) {   for (int i=0; i<HASH_TABLE_SIZE; i++) {     hash_table[i] = NULL;   } }   unsigned long get_hash_index(char *str) {   if (DEBUG_HASH_INDEX) return 4;  // https://xkcd.com/221/   // http://www.cse.yorku.ca/~oz/hash.html   unsigned long hash = 5381;   int c;    while ((c = *str++))       hash = ((hash << 5) + hash) + c; /* hash * 33 + c */    return hash % HASH_TABLE_SIZE; }   char * hget(HashItem * hash_table[], char * key) {   unsigned long idx = get_hash_index(key);   struct HashItem * node = hash_table[idx];   while (node != NULL) {     if (strcmp(key, node->key) == 0){       // if it has the same key we update the value       return node->value;     }     node = node->tail;   }   return NULL; }   void Hdel(HashItem * hash_table[], char * key) {   unsigned long idx = get_hash_index(key);   struct HashItem * head = hash_table[idx];   if (strcmp(key, head->key) == 0){     // if it has the same key we update the value     if (head->tail != NULL){       hash_table[idx] =  head->tail;     } else {       hash_table[idx] = NULL;     }     freeNode(head);     return;   } }   void hset(HashItem * hash_table[], char * key, char * value) {   unsigned long idx = get_hash_index(key);    if (hash_table[idx] == NULL) {     // idx is empty      struct HashItem * new_pair = (struct HashItem*) malloc(sizeof(HashItem));     new_pair->key = key;     new_pair->value = value;     new_pair->tail = NULL;     hash_table[idx] = new_pair;   } else {     // idx is not empty      if (strcmp(key, hash_table[idx]->key) == 0){       // if it has the same key we update the value       hash_table[idx]->value = value;      } else {       // we insert it in the tail       struct HashItem * node = hash_table[idx];        while (1) {         if (node->tail == NULL) {           struct HashItem * new_pair = (struct HashItem*) malloc(sizeof(HashItem));           new_pair->key = key;           new_pair->value = value;           new_pair->tail = NULL;           node->tail = new_pair;           break;         }         if (strcmp(key, node->tail->key) == 0) {           node->tail->value = value;           break;         }         node = node->tail;        } // end while      } // end else   } }   void display(HashItem * hash_table[]) {   // displays the key/values alongside their idx   struct HashItem * node;   int inner;   for (int idx = 0; idx < HASH_TABLE_SIZE; idx++) {      if (hash_table[idx] != NULL) {        printf("DISP idx: %d/0 | key: %s | value: %s\n", idx, hash_table[idx]->key, hash_table[idx]->value);       node = hash_table[idx]->tail;       inner = 1;       while (node != NULL) {         printf("DISP idx: %d/%d | key: %s | value: %s\n", idx, inner, node->key, node->value);         inner++;         node = node->tail;       }     }   } }   void freeNode(struct HashItem * node) {   free(node->key);   free(node->value);   free(node);   node = NULL; }   void freeInnerNodes(struct HashItem * node) {   if (node == NULL) return;   if (node->tail != NULL) freeInnerNodes(node->tail);   printf("FREE | key: %s | value: %s\n", node->key, node->value);   freeNode(node); }   void freeHashTable(HashItem * hash_table[]) {   for (int idx = 0; idx < HASH_TABLE_SIZE; idx++) {     if (hash_table[idx] != NULL) {       freeInnerNodes(hash_table[idx]);     }   } }   static char *rand_string(char *str, size_t size) {     const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJK...";     if (size) {         --size;         for (size_t n = 0; n < size; n++) {             int key = rand() % (int) (sizeof charset - 1);             str[n] = charset[key];         }         str[size] = '';     }     return str; }   char* rand_string_alloc(size_t size) {      char *s = malloc(size + 1);      if (s) {          rand_string(s, size);      }      return s; }   int main() {   struct HashItem* HASH_TABLE[HASH_TABLE_SIZE];   char * randkey = rand_string_alloc(12);   initialize_hash_table(HASH_TABLE);   hset(HASH_TABLE, randkey, rand_string_alloc(12));   for (int i = 0; i < 5; i++) {     hset(HASH_TABLE, rand_string_alloc(12), rand_string_alloc(12));   }   display(HASH_TABLE);   Hdel(HASH_TABLE, randkey);   display(HASH_TABLE);   freeHashTable(HASH_TABLE);   return 0; }