HashSet 和 TreeSet的区别和代码实现

实现方式：

• HashSet底层实现使用哈希表，使用哈希函数存储数据。
• TreeMap地层实现使用红黑树。

顺序性：

• HashMap不能保证元素有序。
• TreeMap按照自然顺序或者自定义排序方式对元素进行排序。

性能：

• HashMap的插入、查找和删除的平均时间复杂度为o(1)
• TreeMap的插入、查找和删除的平均时间复杂度为o(log N)其中N为元素数量。

代码实现：

HashSet

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//默认大小
#define HASH_TABLE_SIZE 100
//定义结构体
typedef struct {
    char* key;
    int value;
} Entry;

typedef struct {
    Entry** table;
} HashMap;

unsigned int hash(const char* key) {
    unsigned int hashValue = 0;
    for (int i = 0; i < strlen(key); i++) {
        hashValue = hashValue * 31 + key[i];
    }
    return hashValue % HASH_TABLE_SIZE;
}

HashMap* createHashMap() {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->table = (Entry**)calloc(HASH_TABLE_SIZE, sizeof(Entry*));
    return map;
}

void put(HashMap* map, const char* key, int value) {
    unsigned int index = hash(key);
    Entry* entry = (Entry*)malloc(sizeof(Entry));
    entry->key = strdup(key);
    entry->value = value;

    Entry* current = map->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            // 键已存在，更新值
            current->value = value;
            free(entry->key);
            free(entry);
            return;
        }
        current = current->next;
    }

    entry->next = map->table[index];
    map->table[index] = entry;
}

int get(HashMap* map, const char* key) {
    unsigned int index = hash(key);
    Entry* current = map->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1;  // 键不存在
}

void destroyHashMap(HashMap* map) {
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Entry* current = map->table[i];
        while (current != NULL) {
            Entry* next = current->next;
            free(current->key);
            free(current);
            current = next;
        }
    }
    free(map->table);
    free(map);
}

int main() {
    HashMap* map = createHashMap();
    put(map, "key1", 1);
    put(map, "key2", 2);
    put(map, "key3", 3);
    printf("Value of key2: %d\n", get(map, "key2"));
    destroyHashMap(map);
    return 0;
}

TreeSet

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char* key;
    int value;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(const char* key, int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = strdup(key);
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* insert(Node* root, const char* key, int value) {
    if (root == NULL) {
        return createNode(key, value);
    }

    int cmp = strcmp(key, root->key);
    if (cmp < 0) {
        root->left = insert(root->left, key, value);
    } else if (cmp > 0) {
        root->right = insert(root->right, key, value);
    } else {
        // 键已存在，更新值
        root->value = value;
    }

    return root;
}

int search(Node* root, const char* key) {
    if (root == NULL) {
        return -1;  // 键不存在
    }

    int cmp = strcmp(key, root->key);
    if (cmp < 0) {
        return search(root->left, key);
    } else if (cmp > 0) {
        return search(root->right, key);
    } else {
        return root->value;
    }
}

void destroyTree(Node* root) {
    if (root == NULL) {
        return;
    }
    destroyTree(root->left);
    destroyTree(root->right);
    free(root->key);
    free(root);
}

int main() {
    Node* root = NULL;
    root = insert(root, "key1", 1);
    root = insert(root, "key2", 2);
    root = insert(root, "key3", 3);
    printf("Value of key2: %d\n", search(root, "key2"));
    destroyTree(root);
    return 0;
}