哈希表

哈希表主要考虑两个问题:1)如何设计哈希函数2)如何解决冲突

hash函数计算出元素在hash表中的储存位置:locate(i)=hash(keyi)hash表用于存储元素

第1节 hash函数构造方法

1)直接定址法:Hash(key)=a*Key+b优点:以关键码key的某个线性函数值为散列地址,不会产生冲突。缺点: 要占用连续地址空间,空间效率低。

2)除留余数法:Hash(Key)=Key % p (设表长未m,取p为小于等于m的质数)优点:节约空间缺点:会产生冲突

第2节 处理冲突的方法

1)开放地址法:Hi=(Hash(key)+di) % m当d为1,2,3……这个线性序列时,叫做线性探测法当d为1,2,3……的平方时,叫做二次序列当d也可以为伪随机数(我猜测这样的话可能需要用一张表事先记录伪随机序列,获取随机数时就从这张表来获取)

2)链地址法:将相同散列地址的元素组成一个链表,那么用数组是应该存储链表的元素还是地址呢?换言之,数组元素的存储结构应该是怎样的?

其它:再散列法(双散列函数)建立一个公共溢出区

一个结论:链地址法优于开发地址法。除留余数法作为散列函数优于其它类型函数。所以在本章节中,只学习和使用链式哈希表。

第3节 链式哈希表

哈希表的存储结构

// 链表结点
typedef struct ListNode
{
    int data;
    struct ListNode *next;
}ListNode;

typedef struct ListNode *List;
typedef struct HashTable
{
    int tableSize;
    List *table; // 优于List table[MAXSIZE];
}HashTable;

哈希表的算法实现

// 哈希表初始化,返回一个指向Hash表的指针
HashTable initHashTable(int size)
{
    HashTable *H=malloc(sizeof(struct HashTable));
    H->tableSize=size;
    H->table=malloc(sizeof(List)*H->tableSize);

    // 为每个链表增加一个虚拟头结点
    for(int i=0;i<H->tableSize;i++)
    {
        H->table[i]=malloc(sizeof(struct ListNode));
        if(H->table[i]==NULL)
        {
            return NULL:
        }
        H->table[i]->next=NULL:
    }
    return H;
}

// 哈希表查找
ListNode* find(int key,HashTable* H)
{
    ListNode* p;
    List L;

    L=H->table[hash(key)];
    p=L->next;
    while(p!=null&&p->data!=key)
    {
        p=p->next;
    }
    return p;
}

// 哈希表插入
void insert(int key,HashTbale *H)
{
    ListNode* pos;
    pos=find(key,H);
    if(pos==NULL)
    {
        ListNode *p=new ListNode;
        L=H->table[hash(key)];
        p->next=L->next;
        p->data=key;
        L-next=p;
    }
}


注:如果哈希表的操作中不包含删除,那么就无需为链表添加头结点。但如果包含的话,最好还是使用头结点吧!

全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务