StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A hash table a data structure that allows lookup of items in constant time. It works by hashing a value and converting that value to an offset in an array. The concept of a hash table is fairly easy to understand, but implementing is obviously harder. I'm not pasting the whole hash table here, but here are some snippets of a hash table I made in C a few weeks ago...</p> <p>One of the basics of creating a hash table is having a good hash function. I used the djb2 hash function in my hash table:</p> <pre><code>int ComputeHash(char* key) { int hash = 5381; while (*key) hash = ((hash << 5) + hash) + *(key++); return hash % hashTable.totalBuckets; } </code></pre> <p>Then comes the actual code itself for creating and managing the buckets in the table</p> <pre><code>typedef struct HashTable{ HashTable* nextEntry; char* key; char* value; }HashBucket; typedef struct HashTableEntry{ int totalBuckets; // Total number of buckets allocated for the hash table HashTable** hashBucketArray; // Pointer to array of buckets }HashTableEntry; HashTableEntry hashTable; bool InitHashTable(int totalBuckets) { if(totalBuckets > 0) { hashTable.totalBuckets = totalBuckets; hashTable.hashBucketArray = (HashTable**)malloc(totalBuckets * sizeof(HashTable)); if(hashTable.hashBucketArray != NULL) { memset(hashTable.hashBucketArray, 0, sizeof(HashTable) * totalBuckets); return true; } } return false; } bool AddNode(char* key, char* value) { int offset = ComputeHash(key); if(hashTable.hashBucketArray[offset] == NULL) { hashTable.hashBucketArray[offset] = NewNode(key, value); if(hashTable.hashBucketArray[offset] != NULL) return true; } else { if(AppendLinkedNode(hashTable.hashBucketArray[offset], key, value) != NULL) return true; } return false; } HashTable* NewNode(char* key, char* value) { HashTable* tmpNode = (HashTable*)malloc(sizeof(HashTable)); if(tmpNode != NULL) { tmpNode->nextEntry = NULL; tmpNode->key = (char*)malloc(strlen(key)); tmpNode->value = (char*)malloc(strlen(value)); strcpy(tmpNode->key, key); strcpy(tmpNode->value, value); } return tmpNode; } </code></pre> <p>AppendLinkedNode finds the last node in the linked list and appends a new node to it.</p> <p>The code would be used like this:</p> <pre><code>if(InitHashTable(100) == false) return -1; AddNode("10", "TEN"); </code></pre> <p>Finding a node is a simple as:</p> <pre><code>HashTable* FindNode(char* key) { int offset = ComputeHash(key); HashTable* tmpNode = hashTable.hashBucketArray[offset]; while(tmpNode != NULL) { if(strcmp(tmpNode->key, key) == 0) return tmpNode; tmpNode = tmpNode->nextEntry; } return NULL; } </code></pre> <p>And is used as follows:</p> <pre><code>char* value = FindNode("10"); </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload