I'm building a program that creates one hash for each string, then associates that hash with a char * value. I've found, though, that if I run the code posted below enough times, eventually I trigger one of my custom "exceptions", shall we say. The only way to get the program to function is to change my printf, run it, then change it back. Here's my code:
Code:
#include <stdio.h>
#include <string.h>
#include "stdlib.h"
#include "math.h"
struct hashvaluepair {
int hash;
char *value;
};
typedefstructhashvaluepair hvp;
struct table {
int length;
hvp *backingArray;
};
typedefstructtable htable;
int hash(char *key)
{
int _hash = 0;
unsigned long keyLength = strlen(key);
int partSum = 0;
int elementsPerPart = 2;
for (int i=0; i <= keyLength; i++) {
if (i % elementsPerPart == 0) {
_hash = 10 * _hash + (partSum % 1000);
partSum = 0;
}
char literal = key[i];
int asciiStringRep = literal;
partSum += asciiStringRep;
}
return _hash;
}
htable * createHashTable()
{
htable *newHashTable = malloc(sizeof(htable));
newHashTable->backingArray = malloc(0);
newHashTable->length = 0;
return newHashTable;
}
int insertHVP(htable *table, hvp *pair)
{
// Create a new backing array to accommodate the new "hvp" variable.
int hvpSize = sizeof(pair);
table->backingArray = realloc(table->backingArray,sizeof(table->backingArray) + hvpSize);
hvp *array = table->backingArray;
int hvpIndex = 0;
// All elements in the array should be sorted according to their hashes. The struct with hash 800 should have a lower index than the struct with hash 912.
for (int i=0; ((pair->hash > array[i - 1].hash) && (i <= table->length)) || i==0; i++) {
hvpIndex = i;
}
for (int i=hvpIndex; i <= table->length; i++) {
array[i + 1] = array[i];
}
if (array[hvpIndex].hash == pair->hash) {
return 1 + (array[hvpIndex].value == pair->value);
}
array[hvpIndex] = *pair;
table->length += 1;
return 0;
}
int addKeyValuePair(char *key, char *value, htable *table)
{
hvp *hashValuePair = malloc(sizeof(hvp));
int _hash = hash(key);
hashValuePair->hash = _hash;
hashValuePair->value = value;
int returnVal = insertHVP(table, hashValuePair);
free(hashValuePair);
return returnVal;
}
char *valueForKey(char *key,htable *table)
{
int _hash = hash(key);
int minIndex = 0;
int maxIndex = table->length - 1;
int middleIndex = -1;
hvp *array = table->backingArray;
char *value = NULL;
// Here, I look for the hash-value pair by checking the first and last hashes in the array. If they are not there, my "while" loop will search for the hash-value pair by calculating ranges that get smaller until only one hash-value pair remains.
if (array[minIndex].hash == _hash)
{
value = array[minIndex].value;
}
else if (array[maxIndex].hash == _hash)
{
value = array[maxIndex].value;
}
else
{
while (array[middleIndex].hash != _hash) {
middleIndex = floor((minIndex + maxIndex) / 2);
hvp middle = array[middleIndex];
// printf("middle hash: %d", middle.hash);
int middleHash = middle.hash;
if (middleHash < _hash) {
minIndex = middleIndex;
}
else if (middleHash > _hash)
{
maxIndex = middleIndex;
}
else
{
value = middle.value;
}
}
}
return value;
}
int main(int argc, const char * argv[]) {
htable *table = createHashTable();
char *allison = "Allison";
char *andy = "Andy";
addKeyValuePair(allison, "1234 Whatever Way", table);
int errorCode = addKeyValuePair(andy, "1514 Anytown Dr", table);
if (errorCode > 0)
{
printf("Error code %d \n", errorCode);
abort();
}
printf("%s",valueForKey(andy, table));
free(table->backingArray);
free(table);
return 0;
}
Last edited:
