散列表数据结构,允许在恒定时间内查找项目。它通过散列值并将该值转换为数组中的偏移量来工作。哈希表的概念很容易理解,但实现起来显然比较困难。我没有在这里粘贴整个哈希表,但这里有几个星期前我在C做的哈希表的片段...
创建哈希表的基础之一是有一个很好的散列函数。我在哈希表中使用的djb2散列函数:
int ComputeHash(char* key)
{
int hash = 5381;
while (*key)
hash = ((hash << 5) + hash) + *(key++);
return hash % hashTable.totalBuckets;
}
然后是在表创建和管理桶
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;
}
AppendLinkedNode实际的代码本身找到链表的最后一个节点,向它附加一个新节点。
的代码将被用于这样的:
if(InitHashTable(100) == false) return -1;
AddNode("10", "TEN");
找到一个节点是简单的:
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;
}
,并使用如下:
char* value = FindNode("10");
Java实现的想法是那么为*有机*成为编程的维基百科。不要强迫问题;这种业力养殖的气味。 – xanadont 2009-07-18 14:36:41