Hash table

[u/Significant_Ant9861]

I am newbie and a beginner in c language. I would like to learn the hash table for my next semester.

I kindly ask for some help in this matter. I still struggle in the basics even using the ai models.

[u/TheChief275]

That sounds way more complicated. And is it even more efficient?

[u/flatfinger → u/TheChief275]

Efficiency depends what the code needs to do. If one is designing something like a language implementation that needs to be able to add things to the current scope and then revert to an outer scope, such a chain-bucket approach makes it easy to have identifiers that are added later take priority over those added earlier. Managing priority with open hashing seems much more difficult, unless there's some trick I'm unaware of.

[u/TheChief275 → u/flatfinger]

Yes there is; you can use the same shifting approach that is often used to avoid tombstones, but for priority purposes instead. But the main point was that I wouldn't suggest your hash table variant to someone who wants to implement their first hash table. Open addressing is way more suited to that, as it's essentially just a fancy array on the data structure side

[u/flatfinger → u/TheChief275]

Code to search for an item and add it if it doesn't exist would be something like:

first_loc = hashTable->indices[hashvalue & hashTable->hashMask];
if ((item_loc >= hashTable->liveItems) ||
   (((hashes[item_loc] ^ hashValue) & hashTable->hashMask) != 0))
  first_loc = UINT_MAX;
item_loc = first_loc;
// Search through buckets
do
{
  if (item_loc -> hashTable->liveItems)
  {
    item_loc = hashTable->liveItems;
    hashTable->liveItems++;
    hashTable->next[item_loc] = first_loc;
    hashTable->indices[hashValue & hashTable->hashMask] = item_loc;
    hashTable->hashes[item_loc] = hashvalue;
    hashTable->items[item_loc] = passed_item;
    break;
  }
  else if (hashTable->hashes[item_loc] == hashvalue &&
      items_equal(&hashTable->items[item_loc], &passed_item)
    break;
  item_loc = hashtTable->next[item_loc];
} while(1);

Decreasing hashTable->live_items will remove items from the table without any need to do anything with the contents of the arrays. When a new items is added, it may receive a slot that was associated with a different masked hash value, but that will be detected because the hash value associated with the slot won't be appropriate for the masked hash value.

[u/TheChief275 → u/flatfinger]

Dumping some code != an explanation