哈希表实现的c++代码
时间: 2023-11-11 13:18:29 浏览: 49
当然可以,下面是一个简单的哈希表实现的 C 代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
typedef struct {
char *key;
int value;
} Entry;
typedef struct {
Entry **entries;
} HashTable;
HashTable* createHashTable() {
HashTable* hashTable = malloc(sizeof(HashTable));
hashTable->entries = calloc(TABLE_SIZE, sizeof(Entry*));
return hashTable;
}
int hashCode(char *key) {
int hash = 0;
for (int i = 0; i < strlen(key); i++) {
hash += key[i];
}
return hash % TABLE_SIZE;
}
void insert(HashTable* hashTable, char *key, int value) {
int index = hashCode(key);
Entry* entry = malloc(sizeof(Entry));
entry->key = strdup(key);
entry->value = value;
if (hashTable->entries[index] == NULL) {
hashTable->entries[index] = entry;
} else {
// Handle collision: Linear probing
int newIndex = (index + 1) % TABLE_SIZE;
while (hashTable->entries[newIndex] != NULL) {
newIndex = (newIndex + 1) % TABLE_SIZE;
}
hashTable->entries[newIndex] = entry;
}
}
int get(HashTable* hashTable, char *key) {
int index = hashCode(key);
if (hashTable->entries[index] != NULL && strcmp(hashTable->entries[index]->key, key) == 0) {
return hashTable->entries[index]->value;
} else {
// Handle collision
int newIndex = (index + 1) % TABLE_SIZE;
while (hashTable->entries[newIndex] != NULL && strcmp(hashTable->entries[newIndex]->key, key) != 0) {
newIndex = (newIndex + 1) % TABLE_SIZE;
}
if (hashTable->entries[newIndex] != NULL && strcmp(hashTable->entries[newIndex]->key, key) == 0) {
return hashTable->entries[newIndex]->value;
} else {
return -1; // Key not found
}
}
}
void freeHashTable(HashTable* hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable->entries[i] != NULL) {
free(hashTable->entries[i]->key);
free(hashTable->entries[i]);
}
}
free(hashTable->entries);
free(hashTable);
}
int main() {
HashTable* hashTable = createHashTable();
// Inserting values into hash table
insert(hashTable, "apple", 5);
insert(hashTable, "banana", 10);
insert(hashTable, "orange", 15);
// Getting values from hash table
printf("Value for key 'apple': %d\n", get(hashTable, "apple"));
printf("Value for key 'banana': %d\n", get(hashTable, "banana"));
printf("Value for key 'orange': %d\n", get(hashTable, "orange"));
printf("Value for key 'watermelon': %d\n", get(hashTable, "watermelon"));
freeHashTable(hashTable);
return 0;
}
```
这个代码使用了线性探测法来处理哈希冲突。在插入操作中,如果发生冲突,会往后查找空槽位,直到找到一个空槽位或者遍历完整个哈希表。在查找操作中,如果发生冲突,会往后查找直到找到对应的键或者遍历完整个哈希表。由于这只是一个简单的示例,所以哈希表的大小是固定的。在实际使用中,我们可能会采用更复杂的解决冲突的方法,并且根据需要动态调整哈希表的大小。