c语言实现哈希表数据结构
哈希表的数据结构:
其实就是数组+链表:如图,
通过一个hash函数将key转化成数组的下标,如果对应的下标在数组里面有数据,那么就冲突了,冲突了怎么办呢,这个时候就把这个数组当成链表的头结点,然后通过头插法或者尾插法将新的节点数据插入到这个链表里面,理论上有hash表的size有多大,就有多少条链表,上图就有16条,冲突得越多,链表的长度就越大。由于查找key的时候,通过key算出对应的数组下标,这个计算的过程是hash算法实现的,一般时间复杂度为O(1),所以得到下标的时间复杂度是O(1), 通过下标在数组中找数据的时间复杂度也是O(1), 所以哈希表的查找的时间复杂度在没有冲突的情况下是O(1), 一旦有冲突,那么就要遍历链表了。这个时候的时间复杂度就是根据链表的长度来决定的。
通过上面的数据结构,能够定义出每个hash节点的数据结构
typedef struct HashNode{ char *key; int value; struct HashNode *nextNode; }HashNode;
而哈希表即上面HashNode的数组
typedef struct HashTable{ HashNode * hashNode[MAX_TABLE_SIZE]; int currentIndex; }HashTable;
好了,我们的数据结构构造出来了之后,接下来就是,初始化,添加,查找,删除,等一系列操作hash表的骚操作了
初始化:
void InitHashTable(HashTable *hashTable) { memset(hashTable->hashNode, 0, sizeof(HashNode *) * MAX_TABLE_SIZE); hashTable->currentIndex = 0; }
插入函数:
//插入key value void Insert(HashTable *hashTable, char *key, int value) { int pos = HashFun(key) % MAX_TABLE_SIZE; HashNode * newNode = (HashNode *)malloc(sizeof(HashNode)); newNode->nextNode = NULL; newNode->key = (char *)malloc(sizeof(char) * (strlen(key) + 1)); strcpy(newNode->key, key); newNode->key[strlen(key)] = '\0'; newNode->value = value; HashNode *p = hashTable->hashNode[pos]; if (p == NULL) { //如果头结点为空,说明没有冲突 hashTable->hashNode[pos] = newNode; hashTable->currentIndex++; return; } //头结点不为空,同时头结点的key和输入的key相同,覆盖value if (strcmp(p->key, key) == 0) { p->value = value; return; } //头结点不为空,冲突,插入到链表的第二个节点 HashNode *q = p->nextNode; newNode->nextNode = q; p->nextNode = newNode; }
获取key对应的value
int * Get(HashTable *hashTable, char *key) { int pos = HashFun(key) % MAX_TABLE_SIZE; HashNode *p = hashTable->hashNode[pos]; if (p == NULL) { //如果头结点为空,说明不存在这样的key return NULL; } else { HashNode *q = p; while (q != NULL) { if(strcmp(q->key, key) == 0) { return &(q->value); } q = q->nextNode; } return NULL; } }
删除对应的key
int Drop(HashTable *hashTable, char *key) { int pos = HashFun(key) % MAX_TABLE_SIZE; HashNode *p = hashTable->hashNode[pos]; if (p == NULL) { //如果头结点为空,说明不存在这样的key return 0; } else { if(strcmp(p->key, key) == 0) { //删除的如果是头结点 hashTable->hashNode[pos] = p->nextNode; free(p->key); free(p); return 1; } //删除的不是头结点的情况 HashNode *q = p->nextNode; HashNode * last = p; while (q != NULL) { if(strcmp(q->key, key) == 0) { last->nextNode = q->nextNode; free(q->key); free(q); return 1; } last = q; q = q->nextNode; } return 0; } }
打印所有数据
void PrintHashTable(HashTable *hashTable) { for(int i = 0; i < MAX_TABLE_SIZE; i++) { HashNode *head = hashTable->hashNode[i]; if (head == NULL) continue; printf("\n数组下标:%d======>", i); printf("(%s:%d)", head->key, head->value); head = head->nextNode; while(head) { printf("-->(%s:%d)", head->key, head->value); head = head->nextNode; } } }
释放堆内存
void ClearHashTable(HashTable* hashTable) { for(int i = 0; i < MAX_TABLE_SIZE; i++) { HashNode *head = hashTable->hashNode[i]; while(head) { HashNode *temp = head->nextNode; free(head->key); free(head); head = temp; } } }
哈希规则
unsigned long HashFun(const char *key) { unsigned long hash = 0; int len = strlen(key); for (int i = 0; i < len; i++) { hash = hash * 33 + key[i]; } return hash; }
main函数测试
int main(void) { HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable)); InitHashTable(hashTable); Insert(hashTable,"1234", 1); Insert(hashTable,"11234", 1); Insert(hashTable,"hello", 2); Insert(hashTable,"world", 3); Insert(hashTable,"hzp", 4); Insert(hashTable,"java", 5); Insert(hashTable,"b", 12); Insert(hashTable,"c", 12); Insert(hashTable,"c1", 12); Insert(hashTable,"c++", 18); Insert(hashTable,"html", 18); Insert(hashTable,"web", 18); Insert(hashTable,"python", 56); PrintHashTable(hashTable); int *data = Get(hashTable,"b"); printf("\n====%d=====\n", *data); Drop(hashTable, "python"); PrintHashTable(hashTable); ClearHashTable(hashTable); }
运行截图:
附代码:
#include#include <string.h> #include #define MAX_KEY_LEN 100 #define MAX_TABLE_SIZE 1000 typedef struct HashNode{ char *key; int value; struct HashNode *nextNode; }HashNode; typedef struct HashTable{ HashNode * hashNode[MAX_TABLE_SIZE]; int currentIndex; }HashTable; unsigned long HashFun(const char *key) { unsigned long hash = 0; int len = strlen(key); for (int i = 0; i < len; i++) { hash = hash * 33 + key[i]; } return hash; } //初始化 void InitHashTable(HashTable *hashTable) { memset(hashTable->hashNode, 0, sizeof(HashNode *) * MAX_TABLE_SIZE); hashTable->currentIndex = 0; } //插入key value void Insert(HashTable *hashTable, char *key, int value) { int pos = HashFun(key) % MAX_TABLE_SIZE; HashNode * newNode = (HashNode *)malloc(sizeof(HashNode)); newNode->nextNode = NULL; newNode->key = (char *)malloc(sizeof(char) * (strlen(key) + 1)); strcpy(newNode->key, key); newNode->key[strlen(key)] = '\0'; newNode->value = value; HashNode *p = hashTable->hashNode[pos]; if (p == NULL) { //如果头结点为空,说明没有冲突 hashTable->hashNode[pos] = newNode; hashTable->currentIndex++; return; } //头结点不为空,同时头结点的key和输入的key相同,覆盖value if (strcmp(p->key, key) == 0) { p->value = value; return; } //头结点不为空,冲突,插入到链表的第二个节点 HashNode *q = p->nextNode; newNode->nextNode = q; p->nextNode = newNode; } int * Get(HashTable *hashTable, char *key) { int pos = HashFun(key) % MAX_TABLE_SIZE; HashNode *p = hashTable->hashNode[pos]; if (p == NULL) { //如果头结点为空,说明不存在这样的key return NULL; } else { HashNode *q = p; while (q != NULL) { if(strcmp(q->key, key) == 0) { return &(q->value); } q = q->nextNode; } return NULL; } } int Drop(HashTable *hashTable, char *key) { int pos = HashFun(key) % MAX_TABLE_SIZE; HashNode *p = hashTable->hashNode[pos]; if (p == NULL) { //如果头结点为空,说明不存在这样的key return 0; } else { if(strcmp(p->key, key) == 0) { //删除的如果是头结点 hashTable->hashNode[pos] = p->nextNode; free(p->key); free(p); return 1; } //删除的不是头结点的情况 HashNode *q = p->nextNode; HashNode * last = p; while (q != NULL) { if(strcmp(q->key, key) == 0) { last->nextNode = q->nextNode; free(q->key); free(q); return 1; } last = q; q = q->nextNode; } return 0; } } void ClearHashTable(HashTable* hashTable) { for(int i = 0; i < MAX_TABLE_SIZE; i++) { HashNode *head = hashTable->hashNode[i]; while(head) { HashNode *temp = head->nextNode; free(head->key); free(head); head = temp; } } } void PrintHashTable(HashTable *hashTable) { for(int i = 0; i < MAX_TABLE_SIZE; i++) { HashNode *head = hashTable->hashNode[i]; if (head == NULL) continue; printf("\nindex:%d======>", i); printf("(%s:%d)", head->key, head->value); head = head->nextNode; while(head) { printf("-->(%s:%d)", head->key, head->value); head = head->nextNode; } } } int main(void) { HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable)); InitHashTable(hashTable); Insert(hashTable,"1234", 1); Insert(hashTable,"11234", 1); Insert(hashTable,"hello", 2); Insert(hashTable,"world", 3); Insert(hashTable,"hzp", 4); Insert(hashTable,"java", 5); Insert(hashTable,"b", 12); Insert(hashTable,"c", 12); Insert(hashTable,"c1", 12); Insert(hashTable,"c++", 18); Insert(hashTable,"html", 18); Insert(hashTable,"web", 18); Insert(hashTable,"python", 56); PrintHashTable(hashTable); int *data = Get(hashTable,"b"); printf("\n====%d=====\n", *data); Drop(hashTable, "python"); PrintHashTable(hashTable); ClearHashTable(hashTable); }