哈希表 哈希函数 哈希冲突:

• 线性探测法解决哈希冲突
• 链地址法解决哈希冲突

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

#define SIZE 10

// 哈希表元素
typedef struct Element {
    int data;
    struct Element *next;
} Element;

// 哈希表
typedef struct HashMap {
    Element *table[SIZE];
} HashMap;

// 哈希函数
int hash(int key) {
    return key % SIZE;
}

Element *createElement(int data) {
    Element *element = (Element *)malloc(sizeof(Element));
    element->data = data;
    element->next = NULL;
    return element;
}

HashMap *createHashMap() {
    HashMap *hashMap = (HashMap *)malloc(sizeof(HashMap));
    for (int i = 0; i < SIZE; i++)
        hashMap->table[i] = NULL;
    return hashMap;
}

// 线性探测,当检测一圈发现表中存满后还没有空位就将当前位置的数据覆盖
void insert(HashMap *hashMap, int data) {
    if (hashMap == NULL) {
        return;
    }

    int index = hash(data);
    Element *element = createElement(data);
    while (hashMap->table[index] != NULL) {
        index = (index + 1) % SIZE;
        if (index % SIZE == hash(data)) {
            break;
        }
    }
    hashMap->table[index] = element;
}

// 链地址法解决哈希冲突
void insert2(HashMap *hashMap, int data) {
    if (hashMap == NULL) {
        return;
    }

    int index = hash(data);
    Element *element = createElement(data);
    if (hashMap->table[index] == NULL) {
        hashMap->table[index] = element;
    } else {
        element->next = hashMap->table[index];
        while (element->next->next != NULL) {
            element->next = element->next->next;
        }
        element->next->next = element;
        element->next = NULL;
    }
}

// 基于线性探测插入的查找
int find(HashMap *hashMap, int data) {
    if (hashMap == NULL) {
        return -1;
    }

    int index = hash(data);
    for (int i = 0; i < SIZE; ++i) {  // 等循环走完index变回原值也就是走完一圈了
        if (hashMap->table[index]->data == data) {
            return index;
        } else {
            index = (index + 1) % SIZE;
        }
    }
    return -1;
}

// 基于链地址法插入的查找
int find2(HashMap *hashMap, int data) {
    if (hashMap == NULL) {
        return -1;
    }
    int index = hash(data);
    Element *element = hashMap->table[index];
    while (element != NULL) {
        if (element->data == data) {
            return index;
        } else {
            element = element->next;
        }
    }
    return -1;
}

// 基于线性探测插入的删除
void delete(HashMap *hashMap, int data) {
    if (hashMap == NULL) {
        return;
    }

    int index = find(hashMap, data);
    if (index != -1) {
        free(hashMap->table[index]);
        hashMap->table[index] = NULL;
    }
}

// 基于链地址法插入的删除
void delete2(HashMap *hashMap, int data) {
    if (hashMap == NULL) {
        return;
    }
    int index = find2(hashMap, data);
    if (index == -1) {
        return;
    } else if (hashMap->table[index]->data == data) {
        free(hashMap->table[index]);
        hashMap->table[index] = NULL;
    }

    Element *temp, *element;
    temp = element = hashMap->table[index];

    while (element != NULL) {
        if (element->data == data) {
            temp->next = element->next;
            free(element);
            return;
        } else {
            temp = element;
            element = element->next;
        }
    }
}

int main() {
    HashMap *hashMap = createHashMap();
    insert2(hashMap, 18);
    insert2(hashMap, 27);
    insert2(hashMap, 63);
    insert2(hashMap, 55);
    insert2(hashMap, 45);
    insert2(hashMap, 36);
    insert2(hashMap, 72);
    insert2(hashMap, 81);
    insert2(hashMap, 9);
    insert2(hashMap, 90);
    insert2(hashMap, 44);
    insert2(hashMap, 184);
    insert2(hashMap, 34);
    for (int i = 0; i < SIZE; i++) {
        if (hashMap->table[i] != NULL) {
            printf("%d ", hashMap->table[i]->data);
        }
    }
    printf("\n");

    printf("%d\n", find2(hashMap, 184));

    delete2(hashMap, 184);

    delete2(hashMap, 45);

    return 0;
}

贡献者

pinkdopeybug

版权所有

版权归属：PinkDopeyBug

许可证：署名 4.0 国际 (CC-BY-4.0)