一、环境说明

1. 本文是 leetcode 705题 :设计哈希集合，使用c语言实现
2. 测试环境:Visual Studio 2019
3. 一题双解。
4. 2022/10/15更新，现在链表法支持插入负数了。

二、代码展示

2.1 数组法实现哈希集合:

#define MaxSize 1000001

typedef struct {
    int *elem;//存放元素的桶
    int count;//总计元素个数，这题不用
} MyHashSet;


MyHashSet* myHashSetCreate() {
    MyHashSet* newHash= (MyHashSet*)calloc(1,sizeof(MyHashSet));//初始化哈希表
    newHash->elem = (int*)calloc(MaxSize,sizeof(int));//初始化桶的个数为MaxSize
    return newHash;
}

void myHashSetAdd(MyHashSet* obj, int key) {
    obj->elem[key]=1;//用1表示元素存在了
}

void myHashSetRemove(MyHashSet* obj, int key) {
    obj->elem[key]=0;//0表示元素不存在了
}

bool myHashSetContains(MyHashSet* obj, int key) {
    if(obj->elem[key])//存在该元素
        return true;
    return false;
}

void myHashSetFree(MyHashSet* obj) {
    free(obj->elem);
    free(obj);
}

2.2 链表法实现哈希集合:

#define MaxSize 769 //桶的数量
typedef struct LinkNode{
    int elem;//结点值
    struct LinkNode *next;
}LinkNode,*LinkList;//链表

typedef struct {
    int key;//键值，这题不用
    LinkList hashHead[MaxSize];//桶
} MyHashSet;//哈希表

MyHashSet* myHashSetCreate() {//创建哈希表
    MyHashSet *newHash = (MyHashSet*)calloc(1,sizeof(MyHashSet));
    return newHash;
}

bool myHashSetContains(MyHashSet* obj, int elem) {//检测元素是否存在
    LinkList curList=elem<0?obj->hashHead[(-elem)%MaxSize]:obj->hashHead[elem%MaxSize];//curList指向被搜索的桶
    while(curList){
        if(curList->elem==elem){
            return true;
        }
        curList=curList->next;
    }
    return false;
}

void myHashSetAdd(MyHashSet* obj, int elem) {//增加元素
    LinkList curList = elem<0?obj->hashHead[(-elem)%MaxSize]:obj->hashHead[elem%MaxSize];
    if(myHashSetContains(obj,elem)){//已存在该元素,插入失败
        return;
    }
    //插入操作
    LinkList inNode = (LinkList)calloc(1,sizeof(LinkNode));
    inNode->elem = elem;
    inNode->next = curList;//头插法，头结点也有元素
    if(elem>=0){
        obj->hashHead[elem%MaxSize] = inNode;
    }else{
        obj->hashHead[(-elem)%MaxSize] = inNode;
    }
}

void myHashSetRemove(MyHashSet* obj, int elem) {//删除元素
    LinkList curNode=obj->hashHead[elem%MaxSize],preNode=NULL;//当前结点和前一结点
    if(!myHashSetContains(obj,elem))//不存在该元素，删除失败
        return;
    while(curNode&&curNode->elem!=elem){//curNode非空,且未遍历到要删除的结点
        preNode = curNode;
        curNode=curNode->next;
    }
    if(NULL==preNode){//待删除结点是头结点
        obj->hashHead[elem%MaxSize] = curNode->next;
        free(curNode);
        return;
    }
    //其他删除操作
    preNode->next = curNode->next;
    free(curNode);
}


void myHashSetFree(MyHashSet* obj) {//释放哈希表空间
    int i=0;
    LinkList freeNode,curNode;
    for(i=0;i<MaxSize;i++){//遍历每个桶
        freeNode = NULL;
        curNode = obj->hashHead[i];
        while(curNode){//释放桶中结点
            freeNode = curNode;
            curNode=curNode->next;
            free(freeNode);
        }
        obj->hashHead[i]=NULL;
    }
    free(obj);
}

三、代码分析

3.1 数组法：

注意事项： 实现较简单。需要注意的一点是MaxSize要设置为1000001，因为题目说，测试用例的范围是0~1000000，一共1000001个数。

3.2 链表法：

注意事项： 实现较复杂，需要读者对链表有一定了解。需要注意的是，代码中的链表，头结点也是存了实际结点值的，要区别于头结点不存值的链表来理解。

3.3 总结：

数组法占用固定的大空间，遇到哈希冲突，还只能手动扩大空间。链表法解决了哈希冲突，且动态申请空间。

四、AC

1. 数组法AC：
   

2. 链表法AC:
   

链表法的空间利用率更高！

五、复杂度分析

5.1 数组法复杂度分析

• 时间复杂度:O(n) ,n是输入数组的长度，遍历数组的时间复杂度O（n）。
• 空间复杂度:O(M)，哈希表的空间复杂度是O（M）

5.2 链表法复杂度分析

• 时间复杂度:O(n) ,同数组法。
• 空间复杂度:O(n),n是输入数组的大小，链表的空间复杂度是O(n)。