精华内容
下载资源
问答
  • 线性探测/闭散列法实现哈希表
    2018-05-22 18:35:15

    线性探测解决哈希冲突的哈希表

            哈希表是一种不用遍历,可以随机访问元素,实现时间复杂度为O(1)的一种数据结构,大大节省了时间。

    一. 哈希表定义

            我们一般定义一个数组用来表示一个哈希表的存储元素的空间,并且通过哈希函数来实现确定某个元素的存入位置、查找某个元素、删除某个元素。

    哈希函数

            我们定义哈希函数,一般采用除整取余法:hash(key) = key % m(m为内存单元个数,可以自己定义)。这里我们定义为10。我们就可以根据该哈希函数计算元素的存储位置:

            hash(1) = 1;hash(2) = 2;hash(8) = 8;hash(5) = 5;hash(10) = 0

            所以,这组数据存储如下:


    这样,我们就可以根据数组下标随机访问我们想要查找的元素,实现时间复杂度O(1)。

            这里的每一个下标对应一个元素,就类似于一个中文单词对应有一个英文单词,这个我们叫做键值对

    二. 哈希冲突

            利用以上所说的哈希函数来存储元素时,我们可能会遇到取到的余数相同,即存储位置相同。比如说hash(1)=1,hash(11)=1,但是下标为1的位置我们只能存入一个元素,这样的情况就叫做哈希冲突。

            为了解决哈希冲突,当然相应的也会有很多办法。其中,我们最常用的有两种:开散列法、闭散列法。

    开散列法:每个下标对应的元素不是单纯的只放一个元素,而是存放一个链表,将相同余数的元素当做一个结点都放在链表上。(该方法见另一篇博客开散列实现哈希表

    闭散列法:发生冲突时,若要插入位置已有元素,但是哈希表还有存储位置,就线性向后探测,遇到的第一个可插入元素位置就可以进行操作。(本文即使用该方法实现哈希表

    负载因子:因为使用哈希表的目的是实现时间上的好处,避免了遍历,可以随机访问,使得操作变得简单并且高效。但是若哈希表中存储了很多元素,这样产生哈希冲突的可能性就很大,使用哈希表目的也得不到实现。这个时候就有了负载因子的出现,负载因子就是控制哈希表中存入元素的个数,若是存入元素的个数占哈希表可存元素的比例,达到或超过了负载因子,这个时候我们就应该扩充哈希表,或者是停止使用当前的哈希表。

    三. 哈希表的实现——闭散列法

    1. 哈希表的结构定义

    //除整取余法:线性向后探测存放
    #pragma once
    
    #include <stdio.h>
    
    #define SHOW_NAME printf("\n====================%s====================\n", __FUNCTION__);
    #define HASHMAXSIZE 1000
    
    typedef int KeyType;
    typedef int ValType;
    typedef size_t (*HashFunc)(KeyType key);//函数指针,用来调用哈希函数,控制元素存入位置                      
    
    typedef enum
    {
        Empty,//表示当前元素为空状态
        Valid,//表示当前元素为有效状态
        Deleted,//表示当前元素为被删除状态
    }Stat;
    
    typedef struct HashElem//表示哈希表中的一个元素,该元素包括键值对
    {
        KeyType key;
        ValType val;
        Stat stat;//表示当前元素的状态
    }HashElem;
    typedef struct HashTable
    {
        HashElem data[HASHMAXSIZE];
        HashFunc func;
        size_t size;//表示当前哈希表中有效元素的个数,哈希表不是线性结构,所以不能用[0,size)表示有效元素区间
    }HashTable;      

            如上代码,我们定义一个枚举用来表示每个元素的状态,除了有效之外,其他两种状态我们都可以对它进行插入操作。我们在哈希表中存的每一个元素包括key与它对应的值,以及该元素的状态。整个哈希表我们用一个数组表示,调用一个函数用作实现该哈希表的哈希函数,哈希表中还包括一个size用以计算当前哈希表中存入了多少了元素。下面就是哈希表的基本操作:

    2. 初始化

    size_t HashFuncDefault(KeyType key)//哈希函数                                                              
    {
        return key%HASHMAXSIZE;
    }
    void HashInit(HashTable* ht, HashFunc func)//初始化
    {
        ht->size = 0;
        ht->func = func;
        size_t i = 0;
        for(i=0; i<HASHMAXSIZE; ++i)
        {   
            ht->data[i].stat = Empty;
        }   
        return;
    }
    

    3. 销毁

    //2.销毁
    void HashDestroy(HashTable* ht)//销毁
    {
        ht->size = 0;
        ht->func = NULL;
        size_t i = 0;
        for(i=0; i<HASHMAXSIZE; ++i)
        {
            ht->data[i].stat = Empty;
        }
        return;
    }       

    3. 打印函数,用以测试

    //3.打印函数,用于测试
    void HashPrint(HashTable* ht, const char* msg)//打印函数
    {
        printf("[%s]\n", msg);
        if(ht == NULL)
            return;
        size_t i = 0;
        for(; i<HASHMAXSIZE; ++i)
        {   
            if(ht->data[i].stat == Valid)
            {   
                printf("%d: [%d:%d]\n", i, ht->data[i].key, ht->data[i].val);
            }   
        }   
        return;
    }
    

    4. 插入操作

    (1)根据负载因子判断当前哈希表是否能继续插入

    (2)根据key调用哈希函数计算插入位置offset

    (3)若当前offset状态不为有效,直接进行插入操作

    (4)若当前offset状态有效,就线性向后探测直至遇到一个不为有效状态的位置,进行插入

    (5)插入操作结束之后,++size

    //4.插入操作
    void HashInsert(HashTable* ht, KeyType key, ValType val)//插入
    {
        if(ht == NULL)//非法输入
            return;
        //1.根据负载因子判断哈希表是否可以继续插入
        //我们约定负载因子为0.8
        if(ht->size >= 0.8*HASHMAXSIZE)
        {
            //当前哈希表已达到负载因子上限,插入失败
            return;
        }
        //2.根据key计算插入位置offset
        size_t offset = ht->func(key);
        while(1)
        {
            //3.若offset位置状态不为Valid,直接插入
            if(ht->data[offset].stat != Valid)
            {
                ht->data[offset].stat = Valid;
                ht->data[offset].key = key;
                ht->data[offset].val = val;
                //6.插入结束后++size
                ++ht->size;
                return;
            }
            //5.若发现哈希表中已有key相同的元素,我们约定为插入失败
            //也可以约定为继续向后查找插入或者替换已有的key键值对,这个由程序员自行决定
            else if(ht->data[offset].key == key && ht->data[offset].stat == Valid)
            {
                return;
            }
            //4.当前offset位置状态是Valid,线性向后查找,找到第一个不为Valid状态的位置插入
            else
            {                                                                                                                                                               
                ++offset;
                //若已探测到数组最后,就从头开始
                if(offset >= HASHMAXSIZE)
                    offset = 0;
            }
    

    5. 给定一个key值,查找对应的value值

    (1)根据key调用哈希函数计算key对应的位置offset

    (2)若当前offset状态有效且key与查找的key相同,查找成功

    (3)若当前offset状态有效,但key不相同,就线性向后探测直至遇到一个不为有效状态的位置,查找失败

    //5.给定一个key,查找对应的val
    int HashFind(HashTable* ht, KeyType key, ValType* val)//查找
    {
        if(ht == NULL || val == NULL)//非法操作
            return 0;
        if(ht->size == 0)//哈希表为空
            return 0;
        //1.根据key计算offset
        size_t offset = ht->func(key);
        while(1)
        {
            //2.从offset开始线性向后查找
            //3.找到了相同的key,返回val,操作成功
            if(ht->data[offset].key == key && ht->data[offset].stat == Valid)
            {
                *val = ht->data[offset].val;
                return 1;
            }
            //5.查找过程直至遇到一个不为Valid状态的元素,说明查找失败
            else if(ht->data[offset].stat != Valid)
                return 0;
            //4.找不到相同的key,继续向后查找
            else
            {
                offset++;
                if(offset >= HASHMAXSIZE)
                    offset = 0;
            }                                                                                                                                                               
        }
    }
    

    6. 给定一个key,删除值为key的元素

        这里查找过程与上面相同,删除过程即将该元素的状态设置为Deleted即可,要注意的是删除之后要--size。

    //6.给定一个key,删除对应元素
    void HashRemove(HashTable* ht, KeyType key)//删除操作
    {
        if(ht == NULL)//非法操作
            return;
        if(ht->size == 0)//空哈希表
            return;
        //1.根据key计算offset
        size_t offset = ht->func(key);
        //2.从offset线性向后查找要删除元素
        while(1)
        {
            //3.若当前key与要删除的key相同,删除元素即将其状态设置为Deleted
            if(ht->data[offset].key == key && ht->data[offset].stat == Valid)
            {
                ht->data[offset].stat = Deleted;
                --ht->size;
                return;
            }
            //4.若查找过程中遇到状态为Empty的元素,则查找失败
            else if(ht->data[offset].stat == Empty)
                return;
            //5.除3、4情况以外,++offset,线性探测下一个元素
            else
            {
                ++offset;
                offset = offset >= HASHMAXSIZE ? 0 : offset;
            }
        }
    }
    

    7. 以下为以上函数的测试代码

    void TestInit()
    {
        SHOW_NAME;
        HashTable ht;
        HashInit(&ht, HashFuncDefault);
        printf("expected is 0, actual is %d\n", ht.size);
        printf("expected is %p, actual is %p\n", HashFuncDefault, ht.func);
    }
    
    void TestDestroy()
    {
        SHOW_NAME;
        HashTable ht;
        HashInit(&ht, HashFuncDefault);
        HashDestroy(&ht);
        printf("expected is 0, actual is %d\n", ht.size);
        printf("expected is nil, actual is %p\n", ht.func);
    }
    
    void TestInsert()
    {
        SHOW_NAME;
        HashTable ht;
        HashInit(&ht, HashFuncDefault);
        HashInsert(&ht, 1, 1);
        HashInsert(&ht, 2, 2);
        HashInsert(&ht, 1001, 3);
        HashInsert(&ht, 1002, 4);
        HashPrint(&ht, "插入4个元素");
    }
    
    void TestFind()
    {
        SHOW_NAME;
        HashTable ht;                                                                                                                                                       
        HashInit(&ht, HashFuncDefault);
        HashInsert(&ht, 1, 1);
        HashInsert(&ht, 2, 2);
        HashInsert(&ht, 1001, 3);
        HashInsert(&ht, 1002, 4);
        HashPrint(&ht, "插入4个元素");
        int value;
        int ret = HashFind(&ht, 1001, &value);
        printf("expected is 3, actual is %d\n", value);
        ret = HashFind(&ht, 2001, &value);
        if(ret == 0)
            printf("查找失败\n");
    }
    
    void TestRemove()
    {
        SHOW_NAME;
        HashTable ht;
        HashInit(&ht, HashFuncDefault);
        HashInsert(&ht, 1, 1);
        HashInsert(&ht, 2, 2);
        HashInsert(&ht, 1001, 3);
        HashInsert(&ht, 1002, 4);
        HashPrint(&ht, "插入4个元素");
        HashRemove(&ht, 1001);
        HashPrint(&ht, "删除key=1001的元素");
        HashRemove(&ht, 2001);
        HashPrint(&ht, "删除key=2001的元素");
    }
    


    更多相关内容
  • 哈希(一)闭散列法

    千次阅读 2018-05-15 16:11:21
    哈希(一)闭散列法 哈希概念 在二叉树搜索中,我们总是要对数据进行排序然后在根据排序结果进行查找。然而对于某些场景来说,总是要进行多次比较才可以搜索到数据,这样复杂度较高,较为复杂。于是我们想出了...

    哈希(一)闭散列法

    哈希概念

    在二叉树搜索中,我们总是要对数据进行排序然后在根据排序结果进行查找。然而对于某些场景来说,总是要进行多次比较才可以搜索到数据,这样复杂度较高,较为复杂。于是我们想出了一种新的方法根据关键码进行映射查找类似于我们去书店借书时,店长有一个小本本记录当天借书与还书的情况来搜素数据。于是我们将这种关键码映射的方法称作哈希结构。

    理想的搜索方式为我们进行一次搜索便可以找到想要的数据。那么我们可以构建一个类似于上面书店这个例子的账本,每一页存一本书的信息,提到书名我们便可以通过其中特殊的映射方式只寻找一次便找到账本关于这本书的这一页。我们将这种映射方式定义为HashFunc。

    当我们向该结构中:

    • 插入数据时:根据该数据的关键码算出插入位置,然后进行插入。状态置为存在。
    • 删除数据时:根据该数据关键码算出删除位置,若位置已经存在数据则为哈希冲突,重新映射插入数据。

    现在让我们总结下哈希结构开散列的特点:
    数据通过映射插入哈希表中,每一个位置只可以存在一个数据。

    我们用以下哈希表为例 :
    映射方式为 :**key(数据)%N(表容量)**除留余数法
    假设我们插入 13,15
    哈希表

    不过我们可以发现,当我们需要插入的数据变多时,将会出现问题,例如当我们插入24时,映射位置也是2,那么会发生冲突,这就产生了一个新的概念**“哈希冲突”**。

    哈希冲突

    产生哈希冲突的本质是由于一对一映射的时候,由于两种数据产生了同一种映射导致位置不够。那么我们可以将第二个数放在其他方便查找的位置。这里提供两种方式解决哈希冲突。

    1. 找到该位置后第一个空的位置插入即可。
    2. 找到该位置后第i平方的位置插入,第一次找到后面第一个位置,如果有数据那就找第4个位置,以此类推。

    查找数据时我们先找到映射位置,如果该数据与映射位置的数据不相等时,我们在根据放置方式进行再次查找即可。不过这样又会产生新的问题,当我们插入了11个数据时,由于我们解决了哈希冲突每一个位置都插入了数据,这样我们在插入数据时将会无法插入。我们引入下一个概念,负载因子。

    负载因子

    我们定义负载因子为哈希表当前数据除以哈希表容量,那么当负载因子过大时将会产生很大的哈希冲突,我们找一个数将会无比麻烦,所以当负载因子高于某一个值时我们要进行扩容操作。根据研究,闭散列的负载因子一般控制在0.7到0.8之间。例如JAVA的系统库将负载因子设在了0.75.
    可是我们扩容来说又有新的问题,当我们下一个容量选择不恰当的话,将会产生很多值映射在一个位置的尴尬情况,为了解决这个问题,我们每一次的扩容都选择质数,这里给出下面代码实现所采用的素数表。
    这里写图片描述

    代码实现

    下面给出哈希闭散列的代码实现以供参考。

    定义哈希表结构体

    typedef int KeyType;
    typedef int ValueType;
    
    enum Status
    {
    	EMPTY,
    	EXITS,
    	_DELETE,
    };//每一个位置的状态
    
    typedef struct HashNodeAZ
    {
    	KeyType _key;
    	ValueType _value;
    	Status _status;
    }HashNode;//节点
    
    typedef struct HashTable
    {
    	HashNode* _tables;
    	size_t _size;
    	size_t _N;
    }HashTable;
    

    扩容用素数表

    size_t GetNextPrimeNum(size_t cur)
    {
    	static int prime_array[] = {
    		17,/* 0 */ 37, /* 1 */79,/* 2 */
    		163,/* 3 */331,/* 4 */673,/* 5 */
    		1361,/* 6 */2729,/* 7 */5471,/* 8 */
    		10949,/* 9 */21911,/* 10 */43853,/* 11 */
    		87719,/* 12 */175447,/* 13 */350899,/* 14 */
    	};
    	if (cur == 0)
    	{
    		return prime_array[0];
    	}
    	for (int i = 0;i < 27;i++)
    	{
    		if (cur == prime_array[i])
    		{
    			return prime_array[i + 1];
    		}
    	}
    	return 0;
    }
    

    计算映射方法

    size_t HashFunc(KeyType key, size_t N)
    {
    	return key % N;
    }
    

    初始化

    void HashTableInit(HashTable* ht)
    {
    	ht->_N = GetNextPrimeNum(0);
    	ht->_tables = (HashNode*)malloc(sizeof(HashNode)*ht->_N);
    	ht->_size = 0;
    	int i = 0;
    	for (;i < ht->_N;i++)
    	{
    		ht->_tables[i]._status = EMPTY;
    	}
    }
    

    扩容

    void HashInsertCapacity(HashTable* ht)
    {
    	if (((ht)->_size * 10) >((ht)->_N * 7))
    	{
    		HashTable newhash;
    		newhash._N = GetNextPrimeNum(ht->_N);
    		newhash._tables = (HashNode*)malloc(sizeof(HashNode)*newhash._N);
    		for (int i = 0;i < newhash._N;i++)
    		{
    			newhash._tables[i]._status = EMPTY;
    		}
    		newhash._size = 0;
    		for (int j = 0;j < (ht)->_N;j++)
    		{
    			if ((ht)->_tables[j]._status == EXITS)
    			{
    				HashTableInsert(&newhash, 
    				ht->_tables[j]._key, ht->_tables[j]._value);
    			}
    		}
    		HashTableDestory(ht);
    		ht->_N = newhash._N;
    		ht->_size = newhash._size;
    		ht->_tables = newhash._tables;
    		
    	}
    }
    

    插入

    int HashTableInsert(HashTable* ht, KeyType key, ValueType value)
    {
    
    	HashInsertCapacity(ht);
    	int i = HashFunc(key, ht->_N);
    	while (ht->_tables[i]._status == EXITS)
    	{
    		if (ht->_tables[i]._key == key)
    		{
    			return -1;
    		}
    		if (i == ht->_N)
    		{
    			i = 0;
    		}
    		i++;
    	}
    	ht->_tables[i]._key = key;
    	ht->_tables[i]._value = value;
    	ht->_tables[i]._status = EXITS;
    	ht->_size++;
    	return 0;
    }
    

    查找

    HashNode* HashTableFind(HashTable* ht, KeyType key)
    {
    	int i = HashFunc(key, ht->_N);
    	while (ht->_tables[i]._status == EXITS)
    	{
    		if (ht->_tables[i]._key == key)
    		{
    			return &ht->_tables[i];
    		}
    		if (i == ht->_N)
    		{
    			i = 0;
    		}
    		i++;
    	}
    	return NULL;
    }
    

    删除

    int HashTableRemove(HashTable* ht, KeyType key)
    {
    	int i = HashFunc(key, ht->_N);
    	while (ht->_tables[i]._status == EXITS)
    	{
    		if (ht->_tables[i]._key == key)
    		{
    			ht->_tables[i]._status = _DELETE;
    			ht->_size--;
    			return 0;
    		}
    		i++;
    	}
    	return -1;
    }
    

    打印哈希表

    void HashPrint(HashTable* ht)
    {
    	int i = 0;
    	for (;i < ht->_N;i++)
    	{
    		if (ht->_tables[i]._status == EMPTY)
    		{
    			printf("[%d EMPTY] ", i);
    		}
    		if (ht->_tables[i]._status == EXITS)
    		{
    			printf("[EXITS : %d ] ", ht->_tables[i]._key);
    		}
    		if (ht->_tables[i]._status == _DELETE)
    		{
    			printf("[%d DELETE] ", i);
    		}
    	}
    }
    
    
    展开全文
  • 闭散列法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索...

    设散列表为 HT[13], 散列函数为 H (key) = key %13 。用闭散列法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。

    (1) 采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

    H(12 =12H23=10 H45=6

    H57=5H20=7H03=3

    H78=0, H(31 =5H15=2 H36 =10

    关于搜索不成功的平均搜索长度计算的问题:

    查找失败的如何计算?首先我们已经采用线性探查法构造了一个表格,这时候当我们提供一个关键码求它进行求模运算得出下标,利用下标去表格查找对应的位置比较关键码,如果关键码不同,则一直往下查找,查到到位置为空的时候还没有查到相同关键码则宣告查找失败(原因:线性探查法表格的构造,当出现下标被占领时,则一直往下查找空余位置进行写入,所以查找失败,只要一直查找到位置为空的时候还没有查找到相同关键码,则宣告失败)

    例如 ①关键码 70 % 13 = 5,查找表格,发现下标为5的位置关键码为57,则继续往下查找,发现一直查找到下标为9的时候为空,还没找到关键码为70的,则查找失败,失败次数为5次;②同理关键码 62 % 13 = 10,查找表格,发现下标为10的位置关键码为23,往下查找,查找到下标为1的位置为空,则查找失败,失败次数为5

    (2) 采用双散列法寻找下一个空位 , 再散列函数为 RH ( key) = (7* key) % 10 + 1, 寻找下一个空位的公式为 Hi = (H i-1 + RH ( key )) % 13, H 1 = H ( key)。画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度。

     

    我是热爱学习的呵呵哒~如果你觉得文章很棒,对你有帮助的话,可以点赞+收藏+加关注喔~

    如果文章有不正确的地方,欢迎交流指正,我将虚心请教~o(>ω<)o

    我会定期更新文章,继续为您提供优质文章

     
    展开全文
  •  即不同关键字通过相同哈希函数计算出相同的哈希地址,对于哈希冲突的处理方法,通常有两种:闭散列法和开散列法,本文先介绍闭散列法,也叫开放地址法。当发生哈希冲突时,如果哈希表未被装满,说明在...

    通常,我们所谓的哈希冲突可以定义为对于两个不相等的数据元素 i和 j,将他们代入哈希函数hashFunc有: 
                hashFunc(i) == hashFunc(j)
                即不同关键字通过相同哈希函数计算出相同的哈希地址,对于哈希冲突的处理方法,通常有两种:闭散列法和开散列法,本文先介绍闭散列法,也叫开放地址法。当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把关键字key存放到表中“下一个位置“。

    首先定义一个哈希表结构体HashTable,结构体里面包含储存关键字key集合的数组table,数组元素的个数size,数组的容量capacity和所设计的哈希函数hashFunc。采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。这里将数组table中的每个位置当前状况采用标一种枚举类型的state来标注,state分为三种状态:删除DELETED,存在EXIST和空白EMPTY。同时,将数组table定义为一种包含关键字key和枚举state的Element结构体类型。相关代码如下:

    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    typedef  int  Key;
    
    typedef  enum
    {
    	EMPTY,
    	EXIST,
    	DELETED
    }State;
    
    typedef struct  Element{
    	Key   key;
    	State   state;
    }Element;
    
    typedef   int ( *HashFuncType)(Key key, int capacity);
    
    typedef   struct  HashTable
    {
    	Element *table;
    	int size;//数据个数
    	int capacity;//容量
    	HashFuncType   hashFunc;//哈希函数
    }HashTable;

    对于哈希表结构体的初始化和销毁,代码如下:

    //初始化
    void   HashInit(HashTable *pHT, int capacity, HashFuncType hashFunc)
    {
    	pHT->table = (Element *)malloc(sizeof(Element)*capacity);
    	assert(pHT->table);
    	pHT->size = 0;
    	pHT->capacity = capacity;
    	pHT->hashFunc = hashFunc;
    
    	for (int i = 0; i < capacity; i++)
    	{
    		pHT->table[i].state = EMPTY;
    	}
    }
    
    //销毁
    void Destory(HashTable *pHT)
    {
    	free(pHT->table);
    }

    这里对于哈希函数的定义采用除留余数法,代码如下:

    
    int hashFunc(Key key, int capacity)
    {
    	return key%capacity;
    }
    

              当发生哈希冲突时,如果哈希表未被装满,把key存放到表中“下一个” 空位中去 ,对于寻找下一个空余位置,有两种方法,首先介绍第一种方法——一次线性探测法,当插入时,从发生冲突的位置开始,依次继续向后探测,如果该位置中有元素且和待插入元素key相同,则不用插入;如果该位置中有元素但不是待插入元素则发生哈希冲突,使用线性探测找到下一个空位置,插入新元素key。采用一次线性探测,发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”。解决办法把数组的容量capacity扩容为原来的2倍。扩充的前提条件是散列表的负载因子不小于7。负载因子可定义为

            

    即pHT->size*10/pHT->capacity<7。

    一次线性探测插入的代码如下:

    //插入
    //key重复不允许插入
    void ExpandIfRequired(HashTable *pHT)
    {
    	//不扩容
    	if (pHT->size*10/pHT->capacity<7)
    	{
    		return;
    	}
    	//需要扩容
    	int newCapacity = pHT->capacity * 2;
    	HashTable newHT;
    	HashInit(&newHT, newCapacity, pHT->hashFunc);
        //将旧数组中的数据搬移到新数组中
    	for (int i = 0; i < pHT->capacity; i++)
        {
    		if (pHT->table[i].state == EXIST)
    		{
    			HashInsert(&newHT, pHT->table[i].key);
    		}
    	}
    	free(pHT->table);
    	pHT->table = newHT.table;
    	pHT->capacity = newHT.capacity;
    }
    
    int HashInsert(HashTable *pHT, Key key)
    {
    	ExpandIfRequired(pHT);
    	int index = pHT->hashFunc(key, pHT->capacity);
    	while (1)
    	{
    		if (pHT->table[index].key == key
    			&&pHT->table[index].state == EXIST)
    		{
    			return 0;
    		}
    		if (pHT->table[index].state != EXIST)
    		{
    			pHT->table[index].key = key;
    			pHT->table[index].state = EXIST;
    			pHT->size++;
    			return 1;
    		}
    		index = (index + 1) % pHT->capacity;
    	}
    
    	return 0;
    }

         对于插入我的测试代码如下:

    void   test()
    {
    	HashTable ht;
    	HashInit(&ht, 10, hashFunc);
    
    	HashInsert(&ht, 1);
    	HashInsert(&ht, 11);
    	HashInsert(&ht, 21);
    	HashInsert(&ht, 31);
    	HashInsert(&ht, 41);
    	HashInsert(&ht, 51);
    	HashInsert(&ht, 61);
    	HashInsert(&ht, 71);
    	HashInsert(&ht, 81);
    	
    	Destory(&ht);
    }

         下面是测试行结果

    对于关键字的查找,如果找到关键字返回其所在位置下标,否则返回0,代码如下:

    //查找
    int HashSearch1(HashTable *pHT, Key key)
    {
    	int index = pHT->hashFunc(key, pHT->capacity);
    	while ((pHT->table[index].state) != EMPTY)
    	{
    		if (pHT->table[index].key == key&&pHT->table[index].state == EXIST)
    		{
    			return index;
    		}
    		else
    			index = (index + 1) % pHT->capacity;
    	}
    	//没找到
    	return 0;
    }

    对于关键字的删除,当查找到要删除的关键字时,只需将这个位置的状态置为删除DELETED。如果删除失败,则返回0。代码如下:

    void HashTableRemove(HashTable *pHT, Key key)
    {
    	int index = pHT->hashFunc(key, pHT->capacity);
    	while ((pHT->table[index].state) !=EMPTY)
    	{
    		if (pHT->table[index].key == key&&pHT->table[index].state == EXIST)
    		{
    			pHT->table[index].state = DELETED;
    			return 1;
    		}
    		else
    			index = (index + 1) % pHT->capacity;
    	}
    	return 0;
    }

    接下来的第二种方法是二次探测法,二次探测法相对于一次探测法,优点在于解决了一次探测数据“堆积”的问题。。二次探测法的下一个空位计算方式为index = (oindex + i*i) % pHT->capacity,其中i代表查找次数,oindex代表上一找到的位置。这里只叙述二次探测法查找代码,其代码如下:

    int HashSearch2(HashTable *pHT, Key key)
    {
    	int oindex = pHT->hashFunc(key, pHT->capacity);//i-1次查找的的元素下标
    	int index = oindex;
    	int i = 1;//i代表查找次数
    	while ((pHT->table[index].state) != EMPTY)
    	{
    		if (pHT->table[index].key == key&&pHT->table[index].state == EXIST)
    		{
    			return index;
    		}
    		//二次探测法变化的位置
    		index = (oindex + i*i) % pHT->capacity;
    		i++;
    	}
    	//没找到
    	return 0;
    }

     

    展开全文
  • 这个映射函数就做散列函数,存放记录的数组叫做散列表。 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间...
  • 闭散列:也叫开放定址,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去 1. 线性探测 比如场景,现在需要插入元素44,先通过哈希...
  • 散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址, 具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来, 各链表的头结点存储在哈希表中。...
  • 散列技术在搜索中所用的时间复杂度最坏也是为O(n), 所以散列技术是一首那个非常高效的数据结构,快速的实现搜索,插入,删除,打印等。 所谓散列技术,就是将一串数据中的关键字值与该数据在结构中的地址形成一种...
  • 哈希表(闭散列、拉链--哈希桶)

    千次阅读 2017-02-20 11:03:57
    哈希表,也称散列表,是一种通过key值来直接访问在内存中的存储的数据结构。它通过一个关键值的函数(被称为散列函数)将所需的数据映射到表中的位置来访问数据。
  • 本文章主要介绍哈希的概念、关于处理哈希表中哈希冲突的闭散列方式以及代码实现其哈希表闭散列方式的插入查找删除操作!
  • 闭散列方法与开散列方法

    万次阅读 2013-08-23 10:33:10
    今天看了云风的blog得知lua 是闭散列的,go 是开散列的,一时不知开闭散列是啥意思就查了下,原来就是解决hash冲突的方法,而且都很熟悉,只是名字忘了 冲突解决策略 尽管散列函数的目标是使得冲突最少,但实际上...
  • 哈希之散列方法: 插入元素时:根据需要插入元素的值,通过某种计算得出元素的存储位置,将该元素插入到其对应的位置。 查找元素时:根据需要查找的元素进行某种计算得到其存储位置,将该位置的元素与查找的元素...
  • 文章目录前言一、闭散列二、开散列1.引入库2.读入数据三、再散列(了解) 前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快...这个映射函数叫做散列函数,存放记录的数组叫做散列表。
  • -采用闭散列处理哈希冲突问题,不能随便物理删除哈希表当中已有元素,比如如果删除4,44查找起来就会受影响,一次线性探测删除一个元素时候还需要对删除位置进行一个新的标志。 画一张图吧,上面例子里面当中的4,...
  • 散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个 桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 以上就是哈希的...
  • 闭散列 也叫开放定址,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢? 线性探测 比如 现在需要...
  • 闭散列 开放定值,当发生哈希冲突时,如果哈希表没有装满,说明在哈希表中必然还有空位置,那么我们可以将元素放到冲突的下一个位置。如何寻找下一个位置。 线性探测:从发生冲突的位置开始,依次向后探测,直到...
  • 这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。 下面介绍业内比较流行的hash冲突解决策略: 线性探测(Linear probing) 双重哈希...
  • 插入的时候要先对其进行查找如果有了就失败 开散列 介绍 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素...
  • 请设计一个整型散列表,散列函数为除留余数,处理冲突时的探查方法为线性探查,其中散列表的长度、除留余数的模和关键码的个数由键盘输入,再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中...
  • 这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数Hash(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数Hash
  • 散列方法又称哈希算法,实际上是对关键码值的索引,与关键码值对应的数据记录一般被存放在其他地方。 散列是一种非常高效的检索方法,散列技术把数据组织到一个表中,根据关键码的值来确定表中每个记录的位置,故...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,557
精华内容 1,022
关键字:

闭散列法