哈希集合、哈希表的拉链法实现

哈希表

• 705. 设计哈希集合

// 拉链法
struct ListNode {
    int val;
    struct ListNode *next;
};

typedef struct {
    struct ListNode *data;
} MyHashSet;

// 模
const int hashSize = 1009;

MyHashSet *myHashSetCreate() {
    MyHashSet *myHashSet = (MyHashSet *) malloc(sizeof(MyHashSet));
    myHashSet->data = (struct ListNode *) malloc(sizeof(struct ListNode) * (hashSize + 1));
    for (int i = 0; i <= hashSize; ++i) {
        myHashSet->data[i].val = -1;
        myHashSet->data[i].next = NULL;
    }
    return myHashSet;
}

// 散列
int hash(int key) {
    return key % hashSize;
}

struct ListNode *getList(MyHashSet *obj, int key) {
    return &(obj->data[hash(key)]);
}

// 返回查找的节点
struct ListNode *findNode(struct ListNode *head, int key) {
    struct ListNode *p = head;
    while (p != NULL && p->next != NULL) {
        if (p->next->val == key) return p;
        p = p->next;
    }
    return NULL;
}

bool containsNode(struct ListNode *head, int key) {
    return findNode(head, key) != NULL;
}

void insertNode(struct ListNode *head, int key) {
    struct ListNode *node = (struct ListNode *) malloc(sizeof(struct ListNode));
    node->val = key;
    node->next = head->next;
    head->next = node;
}

void removeNode(struct ListNode *head, int key) {
    struct ListNode *p = head;
    while (p != NULL && p->next != NULL) {
        // 如果存在也只会有一个节点
        if (p->next->val == key){
            p->next = p->next->next;
            return;
        } 
        p = p->next;
    }
}

void myHashSetAdd(MyHashSet *obj, int key) {
    struct ListNode *head = getList(obj, key);
    if (containsNode(head, key)) return;
    insertNode(head, key);
}

void myHashSetRemove(MyHashSet *obj, int key) {
    struct ListNode *head = getList(obj, key);
    if (!containsNode(head, key)) return;
    removeNode(head, key);
}

bool myHashSetContains(MyHashSet *obj, int key) {
    struct ListNode *head = getList(obj, key);
    return containsNode(head, key);
}

void myHashSetFree(MyHashSet *obj) {
    if (obj != NULL) {
        if (obj->data != NULL) {
            free(obj->data);
            obj->data = NULL;
        }
        free(obj);
        obj = NULL;
    }
}

• 706. 设计哈希映射

// 拉链法
struct MyListNode {
    int key;
    int value;
    struct MyListNode *next;
};

typedef struct {
    struct MyListNode *data;
} MyHashMap;

const int hashSize = 1009;

MyHashMap *myHashMapCreate() {
    MyHashMap *myHashMap = (MyHashMap *) malloc(sizeof(MyHashMap));
    myHashMap->data = (struct MyListNode *) malloc(sizeof(struct MyListNode) * (hashSize + 1));
    for (int i = 0; i <= hashSize; ++i) {
        myHashMap->data[i].key = -1;
        myHashMap->data[i].next = NULL;
    }
    return myHashMap;
}

int hash(int key) {
    return key % hashSize;
}

struct MyListNode *getList(MyHashMap *obj, int key) {
    return &(obj->data[hash(key)]);
}

struct MyListNode *findNode(struct MyListNode *head, int key) {
    while (head != NULL) {
        if (head->key == key)return head;
        head = head->next;
    }
    return NULL;
}

void insertNode(struct MyListNode *head, int key, int value) {
    struct MyListNode *node = (struct MyListNode *) malloc(sizeof(struct MyListNode));
    node->key = key;
    node->value = value;
    node->next = head->next;
    head->next = node;
}

void removeNode(struct MyListNode *head, int key) {
    while (head != NULL && head->next != NULL) {
        if (head->next->key == key) {
            head->next = head->next->next;
            return;
        }
        head = head->next;
    }
}

void myHashMapPut(MyHashMap *obj, int key, int value) {
    struct MyListNode *head = getList(obj, key);
    struct MyListNode *node = findNode(head, key);
    if (node == NULL) {
        insertNode(head, key, value);
    } else {
        node->value = value;
    }
}

int myHashMapGet(MyHashMap *obj, int key) {
    struct MyListNode *head = getList(obj, key);
    struct MyListNode *node = findNode(head, key);
    if (node != NULL) return node->value;
    return -1;
}

void myHashMapRemove(MyHashMap *obj, int key) {
    struct MyListNode *head = getList(obj, key);
    struct MyListNode *node = findNode(head, key);
    if (node != NULL) removeNode(head, key);
}

void myHashMapFree(MyHashMap *obj) {
    if (obj != NULL) {
        if (obj->data != NULL) {
            free(obj->data);
            obj->data = NULL;
        }
        free(obj);
        obj = NULL;
    }
}