精华内容
下载资源
问答
  • 哈希查找代码

    2013-04-28 16:56:17
    严魏敏版教材《数据结构》源代码,学习的好帮手
  • 哈希查找C++源代码

    2010-05-29 12:43:34
    哈希查找 C++源代码 数据结构。 数据结构课作业。
  • 哈希查找

    2019-06-03 14:38:46
    在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技术是在记录的存储位置和记录的 key 之间建立一个确定的映射 f(),使得每个 key 对应一个存储位置 f(key)。若查找集合中存在这个记录,则必定在 f(key) 的...

    提起哈希,Java中的Hashtable类,它是由 key/value 的键值对组成的集合,它就是应用了哈希技术。

    那什么是哈希查找呢?在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技术是在记录的存储位置和记录的 key 之间建立一个确定的映射 f(),使得每个 key 对应一个存储位置 f(key)。若查找集合中存在这个记录,则必定在 f(key) 的位置上。哈希技术既是一种存储方法,也是一种查找方法。

    六种哈希函数 f(key) 的构造方法:

    1、直接定址法

    哈希地址:f(key) = a*key+b  (a,b为常数)

    这种方法的优点是:简单,均匀,不会产生冲突。但是需要事先知道 key 的分布情况,适合查找表较小并且连续的情况。

     

    2、数字分析法

    比如我们的11位手机号码“136xxxx5889”,其中前三位是接入号,一般对应不同运营公司的子品牌,如130是联通如意通,136是移动神州行等等。中间四位表示归属地。最后四位才是用户号。

    若我们现在要存储某家公司员工登记表,如果用手机号码作为 key,那么极有可能前7位都是相同的,所以我们选择最后四位作为 f(key) 就是不错的选择。

     

    3、平方取中法

    故名思义,比如 key 是1234,那么它的平方就是1522756,再抽取中间的3位就是227作为 f(key) 。

     

    4、折叠法

    折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些),然后将这几部分叠加求和,并按哈希表的表长,取后几位作为 f(key) 。

    比如我们的 key 是 9876543210,哈希表的表长为3位,我们将 key 分为4组,987|654|321|0 ,然后将它们叠加求和 987+654+321+0=1962,再取后3位即得到 f(key) = 962 。

     

    5、除留余数法

    哈希地址:f(key) = key mod p (p<=m) m为哈希表表长。

    这种方法是最常用的哈希函数构造方法。下面的代码中也使用了这种方法。

     

    6、随机数法

    哈希地址:f(key) = random(key)  

    这里 random 是随机函数,当 key 的长度不等时,采用这种方法比较合适。

     

    哈希函数冲突的两种解决方法:

    我们设计得再好的哈希函数也不可能完全避免冲突,当我们使用哈希函数后发现有 key1 != key2,但却有 f(key1) = f(key2) ,即发生冲突。

    1、开放定址法:

    开放定址法就是一旦发生了冲突,就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总是能找到,然后将记录插入。这种方法是最常用的解决冲突的方法。下面的代码中也使用了这种方法。

    代码:

    HashSearch.java

    public class Demo1 {
        
        //初始化哈希表
        public static int[] hashTable  = new int[8];
        
        //原始数据
        public static int[] list = new int[] {13, 29, 27, 28, 26, 30, 38, 35};
        
        
        public static void main(String[] args) {
            
            //待查找数据
            int data = 35;
            
            for(int i=0;i<hashTable.length;i++) {
                insert(hashTable, list[i]);
            }
            
            //遍历哈希列表
            System.out.println("哈希列表:"+showHashTable(hashTable));
            //查询数据在哈希中下标
            int result = search(hashTable,data);
            //判断查找是否成功,成功则返回下标
            if(result == -1) {
                System.out.println("查找失败");
            }else {
                System.out.println("数据位置为:"+result);
            }
            
        }
        
        /**
         * 哈希查找
         * @param hashTable
         * @param data
         * @return
         */
        public static int search(int[] hashTable,int data) {
            //除留余数法
            int model = data % hashTable.length;
            
            int hashAddress = model;
            
            while(hashTable[hashAddress] != data) {
                 // 利用 开放定址法 解决冲突
                hashAddress = (++hashAddress) % hashTable.length;
                //查找到开放单元(值为0代表未开放单元)或者下标循环回到原点,查找失败
                if(hashTable[hashAddress] == 0 || hashAddress == model) {
                    return -1;
                }
            }
            //查找成功返回下标
            return hashAddress;
        }
        
        /**
         * @method 哈希插入
         * @param  hashTable
         * @param  data
         */
        public static void insert(int[] hashTable,int data) {
            //除留余数法
            int hashAddress = data % hashTable.length;
            
            //int数组初始为0,判断当前下标数值是否0,不为0说明发送冲突,则下标移到下一位
            while(hashTable[hashAddress] != 0) {
                 // 利用 开放定址法 解决冲突
                hashAddress = (++hashAddress) % hashTable.length;
            }
            
            //将当前值存入字典中
            hashTable[hashAddress] = data;
        }
        
        //遍历哈希列表
        public static String showHashTable(int[] hashTable) {
            StringBuilder sb = new StringBuilder();
            for(int i:hashTable) {
                sb.append(i+" ");
            }
            
            return sb.toString();
        }
        
    }运行结果:
    

    哈希列表:38 35 26 27 28 13 29 30 
    数据位置为:1

     

    展开全文
  • 哈希查找

    2014-05-29 20:58:01
    代码 哈希查找树 源代码好用 值得拥有
  • 哈希查找代码实现

    千次阅读 2017-03-29 23:13:29
    博主邮箱:2930526477@qq.com(有志同道合之人,可以加qq交流交流编程心得)1、代码实现的介绍下面我将会实现哈希表的查找代码: 其中我会采取的散列构造函数为最常用的构造函数:除留取余数法 而解决冲突的方法...

    前言

    博客编写人:Willam
    博客编写时间:2017/3/29
    博主邮箱:2930526477@qq.com(有志同道合之人,可以加qq交流交流编程心得)

    1、代码实现的介绍

    下面我将会实现哈希表的查找代码:
    其中我会采取的散列构造函数为最常用的构造函数:除留取余数法
    而解决冲突的方法采用以下三种,分别实现:

    1. 线性探测
    2. 二次探测
    3. 链地址法

    如果需要了解哈希表的详细介绍,可参考博客:哈希表的详解

    2、线性探测的实现

    • linear.h文件的代码
    /************************************************************/
    /*                程序作者:Willam                          */
    /*                程序完成时间:2017/3/29                  */
    /*                有任何问题请联系:2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    
    //#pragma once是一个比较常用的C/C++杂注,
    //只要在头文件的最开始加入这条杂注,
    //就能够保证头文件只被编译一次。
    #ifndef   MY_H_FILE       //如果没有定义这个宏  
    #define   MY_H_FILE       //定义这个宏  
    
    #include<iostream>
    using namespace std;
    typedef int Keytype;
    
    //每次都是取质数最接近的质数
    
    struct Hash {
        Keytype * elem; //记录哈希表中的元素
        bool * isfull;  //记录哈希表是否有元素了
        int count;      //哈希表中元素的个数
        int sizeindex;
    
    };
    
    bool searchHash(Hash t, Keytype k, int & p, int &c,int * hashsize);
    bool insertHash(Hash & t, Keytype k, int * hashsize);
    bool DeleteHash(Hash & t, Keytype k, int * hashsize);
    void print(Hash  t, int * hashsize);
    
    #endif  
    
    
    
    • linear.cpp文件的代码
    #include"linear.h"
    
    
    //查找对应的关键字
    bool searchHash(Hash t, Keytype k, int & p,int &c,int * hashsize) {
        p = k%hashsize[t.sizeindex];
        while (t.isfull[p] && t.elem[p] != k && c < hashsize[t.sizeindex]-1) {
            ++c;
            //继续往下寻找下一个散列结点
            p=(k+c) % hashsize[t.sizeindex];
        }
        if (t.elem[p] == k) {
            return true;
        }
        return false;
    
    }
    
    
    
    
    bool insertHash(Hash & t, Keytype k, int * hashsize) {
        int p;
        int c = 0;
        if (searchHash(t, k, p,c,hashsize)) {
            return false;
        }
        else if (c==hashsize[t.sizeindex]-1) {//此时哈希表已经满,得重新分配了
            //首先是把之前的内容保存起来
            int temp;
            temp=hashsize[t.sizeindex];
            Keytype * elem = new Keytype[hashsize[t.sizeindex]];
            bool * isfull=new bool[hashsize[t.sizeindex]];
            for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
                elem[i] = t.elem[i];
                isfull[i] = t.isfull[i];
            }
            delete t.elem;
            delete t.isfull;
            ++t.sizeindex;
            //重新分配空间
            t.elem= new Keytype[hashsize[t.sizeindex]];
            t.isfull=new bool[hashsize[t.sizeindex]];
            int i;
            for (i = 0; i < temp; ++i) {
                 t.elem[i]=elem[i];
                 t.isfull[i] = isfull[i];
            }
            for (; i < hashsize[t.sizeindex]; ++i) {
                t.isfull[i] = false;
            }
        }
        else {
            //cout << p << endl;
            //直接插入对应的位置
            t.elem[p] = k;
            ++t.count;
            t.isfull[p] = true;
        }
    
    }
    
    bool DeleteHash(Hash & t, Keytype k, int * hashsize) {
        int p;
        int c = 0;
        if (!searchHash(t, k, p, c,hashsize)) {//没找到要删除的元素
            return false;
        }
        else {
            t.isfull[p] = false;
            --t.count;
        }
    }
    
    void print(Hash t, int * hashsize) {
        cout << "当前的表的长度:" << hashsize[t.sizeindex] << endl;
        cout << "Hash表的元素个数为:" << t.count << endl;
        cout << "打印整个表:" << endl;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
            if(t.isfull[i])
            cout << t.elem[i] << " ";
            else {
                cout << "^" << " ";
            }
        }
        cout << endl;
    }
    • main.cpp文件的代码
    #include"linear.h"
    int hashsize[]={ 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
    109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
    227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
    347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
    461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
    599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719,
    727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
    859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
    int main() {
        Hash t;
        t.count = 0;
        t.sizeindex = 0;
        t.elem = new Keytype[hashsize[t.sizeindex]];
        t.isfull = new bool[hashsize[t.sizeindex]];
        cout << "请先输入10个数" << endl;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
                t.isfull[i] = false;
        }
    
        for (int i = 0; i < 10; ++i) {
            int temp;
            cin >> temp;
            insertHash(t,temp,hashsize);
            //print(t, hashsize);
        }
        print(t,hashsize);
        cout << "输入需要查找的数:" << endl;
        int key;
        cin >> key;
        int p;
        int c = 0;
        if (searchHash(t, key,p,c, hashsize)) {
            cout << "查找成功" << endl;
            cout << "为第" << p+1 << "个元素" << endl;
        }
        else {
            cout << "查找失败" << endl;
        }
        cout << "输入需要删除的数:" << endl;
    
        cin >> key;
        if (DeleteHash(t, key, hashsize)) {
            cout << "删除成功,删除后的结果:" << endl;
            print(t, hashsize);
        }
        else {
            cout << "删除失败" << endl;
        }
    
        system("pause");
        return 0;
    }

    输入:

    12 67 56 16 25 37 22 29 15 47
    16
    15

    输出:
    这里写图片描述

    3、二次探测的实现

    对于二次探测,其实它和线性探测的插入删除代码都是一样的,只是查找过程中单位的移动量不同,所以我们只要修改对应的查找函数就可以了,修改成如下:

    //查找对应的关键字
    bool searchHash(Hash t, Keytype k, int & p,int &c,int * hashsize) {
        p = k%hashsize[t.sizeindex];
        while (t.isfull[p] && t.elem[p] != k && c < hashsize[t.sizeindex]-1) {
    
            //++c;
            //二次探测和线性探测的区别
            if (c == 0) {
                c=1;
                p = (k + c) % hashsize[t.sizeindex];
            }
            else if (c > 0) {
                c = -c;
                p = (k - c*c) % hashsize[t.sizeindex];
            }
            else if (c < 0) {
                c = -c + 1;
                p = (k + c*c) % hashsize[t.sizeindex];
            }
            //继续往下寻找下一个散列结点
        }
        if (t.elem[p] == k) {
            return true;
        }
        return false;
    
    }

    输入:

    12 67 56 16 25 37 22 29 15 47
    67
    12

    输出:
    这里写图片描述

    4、链地址法的实现

    • List.h文件的代码
    #pragma once
    /************************************************************/
    /*                程序作者:Willam                          */
    /*                程序完成时间:2017/3/29                  */
    /*                有任何问题请联系:2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    
    //#pragma once是一个比较常用的C/C++杂注,
    //只要在头文件的最开始加入这条杂注,
    //就能够保证头文件只被编译一次。
    
    
    #include<iostream>
    using namespace std;
    typedef int Keytype;
    
    struct Node {
        Keytype data; //每个结点的值
        Node * next;  //下一个结点
        Node() {
            next = NULL;
        }
    };
    
    
    //每次都是取质数最接近的质数
    struct Hash {
        Node * elem; //头结点链表
        int sizeindex;
    
    };
    
    bool searchHash(Hash t, Keytype k, Node* & p, Node * & pre, int * hashsize);
    bool insertHash(Hash & t, Keytype k, int * hashsize);
    bool DeleteHash(Hash & t, Keytype k, int * hashsize);
    void print(Hash  t, int * hashsize);
    
    
    • List.cpp文件的代码
    #include"List.h"
    bool searchHash(Hash t, Keytype k, Node * & p, Node * & pre, int * hashsize) {
    
        int index = k%hashsize[t.sizeindex];
        Node * head = t.elem[index].next;
        pre = NULL;
        while (head) 
        {//变量整个结点
            p = head;
            if (head->data == k) {
                return true;
            }
            pre = head;
            head = head->next;
        }
        return false;
    }
    
    
    //插入
    bool insertHash(Hash & t, Keytype k, int * hashsize) {
        Node * p;
        Node * pre;
        if (searchHash(t, k, p,pre, hashsize)) {
            return false;
        }
        else {
            Node * s = new Node;
            s->data = k;
            if (pre == NULL) {
                int index = k%hashsize[t.sizeindex];
                t.elem[index].next = s;
                return true;
            }
            p->next = s;
        }
        return true;
    }
    
    //删除结点
    bool DeleteHash(Hash & t, Keytype k, int * hashsize) {
        Node * p;
        Node * pre;
        if (!searchHash(t, k, p,pre,hashsize)) {
            return false;
        }
        else {
            if (pre == NULL) {
                int index = k%hashsize[t.sizeindex];
                t.elem[index].next =p->next;
                return true;
            }
            else {
                pre->next = p->next;
                delete p;
            }
        }
        return true;
    }
    
    void print(Hash  t, int * hashsize) {
        Node * p;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
            cout << i << " ";
            p = t.elem[i].next;
            while (p) {
                cout << p->data << " ";
                p = p->next;
            }
            cout << "^" << endl;
        }
    }
    • main.cpp文件的代码
    #include"list.h"
    int hashsize[]={ 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
    109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
    227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
    347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
    461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
    599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719,
    727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
    859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
    int main() {
        Hash t;
        t.sizeindex = 0;
        t.elem = new Node[hashsize[t.sizeindex]];
        cout << "请先输入10个数" << endl;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
            t.elem[i].next = NULL;
        }
    
        for (int i = 0; i < 10; ++i) {
            int temp;
            cin >> temp;
            insertHash(t,temp,hashsize);
            //print(t, hashsize);
        }
        print(t,hashsize);
    
    
        cout << "输入需要查找的数:" << endl;
        int key;
        cin >> key;
        Node *p;
        Node *pre;
        int c = 0;
        if (searchHash(t, key,p,pre, hashsize)) {
            cout << "查找成功" << endl;
            cout <<  p->data  << endl;
        }
        else {
            cout << "查找失败" << endl;
        }
        cout << "输入需要删除的数:" << endl;
    
        cin >> key;
        if (DeleteHash(t, key, hashsize)) {
            cout << "删除成功,删除后的结果:" << endl;
            print(t, hashsize);
        }
        else {
            cout << "删除失败" << endl;
        }
    
        system("pause");
        return 0;
    }

    输入:

    12 67 56 16 25 37 22 29 15 47
    29
    29

    输出:
    这里写图片描述

    展开全文
  • 查找算法之哈希查找

    2019-04-26 09:22:33
    哈希查找定义: 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。O(1)的查找,即所谓的秒杀。哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数,它将原来直观、整洁的数据...

    哈希查找定义:

    哈希查找是通过计算数据元素的存储地址进行查找的一种方法。O(1)的查找,即所谓的秒杀。哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数,它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。

    哈希查找的操作步骤:

    1)       用给定的哈希函数构造哈希表;

    2)       根据选择的冲突处理方法解决地址冲突;

    3)       在哈希表的基础上执行哈希查找。

    建立哈希表操作步骤:

    1)       step1 取数据元素的关键字key,计算其哈希函数值(地址)。若该地址对应的存储空间还没有被占用,则将该元素存入;否则执行step2解决冲突。

    2)       step2 根据选择的冲突处理方法,计算关键字key的下一个存储地址。若下一个存储地址仍被占用,则继续执行step2,直到找到能用的存储地址为止。

    哈希查找步骤为:

    1)       Step1 对给定key值,计算哈希地址 Di=Hash(key);若HST为空,则查找失败;若HST=key,则查找成功;否则,执行step2(处理冲突)。

    2)       Step2 重复计算处理冲突的下一个存储地址 Dk=R(Dk-1),直到HST[Dk]为空,或HST[Dk]=key为止。若HST[Dk]=key,则查找成功,否则查找失败。

     

    比如说:”5“是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个”2",那么此时的”5“和“2”就建立一种对应关系,这种关系就是所谓的“哈希关系”,在实际应用中也就形成了”2“是key,”5“是value。

    那么有的朋友就会问如何做哈希,首先做哈希必须要遵守两点原则:

    ①: key尽可能的分散,也就是我丢一个“6”和“5”给你,你都返回一个“2”,那么这样的哈希函数不尽完美。

    ②:哈希函数尽可能的简单,也就是说丢一个“6”给你,你哈希函数要搞1小时才能给我,这样也是不好的。

    其实常用的做哈希的方法有“五种”:

    第一种:”直接定址法“。

    很容易理解,key=Value+C;这个“C"是常量。Value+C其实就是一个简单的哈希函数。

    第二种:“除法取余法”。

    很容易理解, key=value%C;解释同上。

    第三种:“数字分析法”。

    这种蛮有意思,比如有一组value1=112233,value2=112633,value3=119033,

    针对这样的数我们分析数中间两个数比较波动,其他数不变。那么我们取key的值就可以是

    key1=22,key2=26,key3=90。

    第四种:“平方取中法”。此处忽略,见名识意。

    第五种:“折叠法”。

    这种蛮有意思,比如value=135790,要求key是2位数的散列值。那么我们将value变为13+57+90=160,然后去掉高位“1”,此时key=60,哈哈,这就是他们的哈希关系,这样做的目的就是key与每一位value都相关,来做到“散列地址”尽可能分散的目地。

    影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时,就会发生冲突。为减少发生冲突的可能性,哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。

    常用的解决冲突的方法有以下两种:  

    (1)   开放地址法  

    如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。  

    (2)   链地址法

    将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。

     

    实现哈希函数为“除法取余法”,解决冲突为“开放地址线性探测法”,代码如下:

     

    
    public class HashSearch {
     
        public static void main(String[] args) {
            //“除法取余法”
            int hashLength = 13;
     
            int [] array  = { 13, 29, 27, 28, 26, 30, 38 };
     
            //哈希表长度
            int[] hash = new int[hashLength];
            //创建hash
            for (int i = 0; i < array.length; i++)
            {
                insertHash(hash, hashLength, array[i]);
            }
            
            int result = searchHash(hash,hashLength, 29);
     
            if (result != -1)
                System.out.println("已经在数组中找到,索引位置为:" + result);
            else
                System.out.println("没有此原始");
        }
     
        /****
         * Hash表检索数据
         * 
         * @param hash
         * @param hashLength
         * @param key
         * @return
         */
        public static int searchHash(int[] hash, int hashLength, int key) {
            // 哈希函数
            int hashAddress = key % hashLength;
     
            // 指定hashAdrress对应值存在但不是关键值,则用开放寻址法解决
            while (hash[hashAddress] != 0 && hash[hashAddress] != key) {
                hashAddress = (++hashAddress) % hashLength;
            }
     
            // 查找到了开放单元,表示查找失败
            if (hash[hashAddress] == 0)
                return -1;
            return hashAddress;
     
        }
     
        /***
         * 数据插入Hash表
         * 
         * @param hash 哈希表
         * @param hashLength
         * @param data
         */
        public static void insertHash(int[] hash, int hashLength, int data) {
            // 哈希函数
            int hashAddress = data % hashLength;
     
            // 如果key存在,则说明已经被别人占用,此时必须解决冲突
            while (hash[hashAddress] != 0) {
                // 用开放寻址法找到
                hashAddress = (++hashAddress) % hashLength;
            }
     
            // 将data存入字典中
            hash[hashAddress] = data;
        }
    }
    


    原文:https://blog.csdn.net/xiaoping8411/article/details/7706376 
     

    展开全文
  • 可以实现最小完美哈希查找,及查找时间复杂度为O(1),且load size 为1
  • 哈希查找算法的源代码 c语言 问题描述 针对自己的班集体中的人名设计一个哈希表使得平均查找长度不超过R完成相应的建表和查表程序 [基本要求] 假设人名为中国姓名的汉语拼音形式待填入哈希表的人名共有30个取平均...
  • 优质范文 哈希查找算法的源代码 c语言 问题描述 针对自己的班集体中的人名设计一个哈希表使得平均查找长度不超过R完成相应的建表和查表程序 [基本要求] 假设人名为中国姓名的汉语拼音形式待填入哈希表的人名共有30...
  • 哈希查找代码实现 注释超详细哦) 什么是理想的哈希表呢。哈希表(通常用数组来存放这张表)中记录的存储位置和他的关键字之间有一个确定的对应关系f(key),这就是哈希函数,常见的哈希函数; 直接定制法,除...

    哈希查找(代码实现 注释超详细哦)

     

    什么是理想的哈希表呢。哈希表(通常用数组来存放这张表)中记录的存储位置和他的关键字之间有一个确定的对应关系f(key),这就是哈希函数,常见的哈希函数;

    • 直接定制法,除留余数法

    它使每一个关键字和结构中唯一一个存储位置相对应。因而查找时可以根据f(key)算出要查找关键字的位置,达到快速查找的目的(不需要比较查找效率可达到O(1))。但是这是一种很理想的情况,实际上在应用中会有这种情况的产生;

      • 多个元素通过相同的哈希函数——》计算出相同的哈希地址—-〉产生哈希冲突(原位置被占)
      • 那么如何解决哈希冲突?
      • 1》检查哈希函数设计是否合理?
      • 2》哈希函数的值域必须在哈希表的范围内
      • 3》尽量使哈希地址分散。(其中一种方法就是二次探测)

        当已经发生时;

        4》从发生哈希冲突的位置开始,向后找下一个“哈希地址”。(逐个超后探测,线型探测)缺陷;存在数据堆积。防治方法(二次探测)

         

    如下是我实现的代码

    #include <malloc.h>
    #include <stdio.h>
    #include <assert.h>
    
    typedef enum {EX,EM,DL}State;//储存位置的状态,是已存,空,还是删除过,在这个哈希表中删除过元素的存储空间是不可再用的
    typedef int DataType;
    
    typedef struct HTELEM {
            DataType  _data;//存入的关键字(关键字不一定是数值,当然目前我们做的这个表中存的是数值)
            State _state;
    }HTELEM;
    
    
    typedef struct HashTable{
            HTELEM*  arr;//存放哈希表的数组
            int _capacity;//数组的容量
            int _size;//已用存储位置的大小
            int _IsLineDetective;//标志着选择的哈希函数
    }HT,HashTable;
    
    
    void   swap (HT*ht,HT*newht)//交换两个哈希表的内容
    {
            int temp=0;
            temp=(int)ht->arr;
            ht->arr=newht->arr;
            newht->arr=(HTELEM*)temp;
    
    
    
            temp=ht->_capacity;
            ht->_capacity=newht->_capacity;
            newht->_capacity=temp;
    
            temp=ht->_size;
            ht->_size=newht->_size;
            newht->_size=temp;
    
            temp=ht->_IsLineDetective;
            ht->_IsLineDetective=newht->_IsLineDetective;
            newht->_IsLineDetective=temp;
    }
    
    void HashTableInit(HT*ht ,int capacity,int IsLineDetectiev)//初始化哈希表
    {
            int i=0;
            ht->arr=(HTELEM*)malloc(sizeof(HTELEM)*capacity);//给存放哈希表的数组动态开辟内存
            for (i=0;i<capacity;i++)//所有位置的储存状态置为空
            {
                    ht->arr[i]._state=EM;
            }
    
            ht->_size=0;
            ht->_IsLineDetective=IsLineDetectiev;
            ht ->_capacity=capacity;
    }
    
    
    int HashFunc (DataType  data, HT*ht)
    {
            return    data%ht->_capacity;//哈希函数;除留余数法
    }
    
    int DetectiveLine(int hashaddr,HT*ht)//一次线型探测
    {
            hashaddr++;
            if (hashaddr==ht->_capacity)
                    hashaddr=0;
            return hashaddr;
    }
    
    int Detective2(int hashaddr,int i,HT*ht)//二次(平方)探测
    {
            hashaddr=hashaddr+2*i+1;
            if (hashaddr>=ht->_capacity)
                    hashaddr%=ht->_capacity;
            return hashaddr;
    }
    
    void HashTableInsert (HT *ht ,DataType data)//哈希表的插入
    {
            int i=0;
            int hashaddr=-1;
            assert (ht);
    
    
            CheckCapacity(ht);//查看并决定是否需要扩容
    
    
            hashaddr=HashFunc(data,ht);//通过哈希函数计算应插位置
    
            while (EM!=ht->arr[hashaddr]._state)
            {
                    if (ht->arr[hashaddr]._state==EX)
                    {
                            if (ht->arr[hashaddr]._data==data)//已经有这个数据就不用插入,直接返回
                                    return;
                    }
                    if (ht->_IsLineDetective)//当前的位置被占(被不是要插的数据占),或被删除过,则不可用(哈希冲突),向后探测
                    {
                            hashaddr=DetectiveLine(hashaddr,ht);
                    }
                    else {
                            ++i;
                            hashaddr=Detective2(hashaddr,i,ht);
                    }
    
            }
    
            ht ->arr[hashaddr]._state=EX;//向已经找到的位置,放入数据
            ht->arr[hashaddr]._data=data;
            ht->_size++;
    }
    
    
    
    int HashTableFind (HT*ht,DataType data)//在哈希表中查找数据,与插入相似
    {
            int hashaddr=-1,startaddr=-1,i=0;
            assert(ht);
            hashaddr =HashFunc(data,ht);
            startaddr=hashaddr;//记录开始查找位置(既不发生哈希冲突时应存位置)
    
            while (EM!=ht->arr[hashaddr]._state)
            {
                    if (ht->arr[hashaddr]._state==EX)//找到返回
                            if (ht->arr[hashaddr]._data==data)
                                    return    hashaddr;
    
                    if (ht->_IsLineDetective)//向后查找
                    {
                            hashaddr=DetectiveLine(hashaddr,ht);
                            if (hashaddr==startaddr)
                                    return -1;
                    }
                    else {
                            ++i;
                            hashaddr=Detective2(hashaddr,i,ht);
                            if (hashaddr==startaddr)
                                    return -1;
    
                    }
            }
            return -1;
    }
    
    
    
    void HashTableDelete(HT* ht ,DataType   data)//哈希表的删除
    {
    
            int ret=-1;
            assert (ht);
    
            ret =HashTableFind(ht,data);
    
            if (ret!=-1)
            {
                    ht->arr[ret]._state=DL;
                    ht->_size--;
            }
    }
    
    int HashTableSize(HT*ht)//哈希表的大小
    {
            assert (ht);
            return ht->_size;
    }
    
    
    int HashTableEmpty(HT*ht)//哈希表是否为空
    {
            assert (ht);
            if (  0==ht->_size)
                    return 1;
    }
    
    
    void HashTableDestory(HT*ht)//哈希表的销毁
    
    {
            int i=0;
            free(ht->arr);
            ht->arr=NULL;
            ht->_size=0;
            ht->_IsLineDetective=0;
            ht ->_capacity=0;
    }
    
    int CheckCapacity(HT*ht)//哈希表的扩容
    {
            int i=0;
            int capacity;
            assert (ht );
            if (ht->_size*10/ht->_capacity>7)//当已用空间占到总容量的70%时扩容
            {
                    HT newht;
                    capacity=ht->_capacity*2;
                    HashTableInit(&newht ,capacity,ht->_IsLineDetective);//初始化一个新表,(新表的容量是老表的2倍)
    
                    for (i=0;i<ht->_capacity;i++)//把老表中的元素插入新表
                    {
                            if (EX==ht->arr[i]._state)
                                    HashTableInsert (&newht ,ht->arr[i]._data);
                    }
                    swap(&newht,ht);//把新表的内容交给老表(新表只是一个函数体内的变量,除了函数体会被销毁)
                    HashTableDestory(&newht);//销毁新表
            }
            return 1;
    }
    
    
    
    
    void TestHashTable()
    {
            HashTable ht;
            HashTableInit(&ht,6,1);
            HashTableInsert (&ht ,23);
            HashTableInsert (&ht ,14);
            HashTableInsert (&ht ,74);
            HashTableInsert (&ht ,33);
            HashTableInsert (&ht ,19);
            HashTableInsert (&ht ,29);
            HashTableInsert (&ht ,29);
    
            printf("size=%d\n",HashTableSize(&ht));
            if (-1!=HashTableFind(&ht,33))
            {
                    printf ("have\n");
            }
            else
                    printf ("no have\n");
            if (-1!=HashTableFind(&ht,3))
            {
                    printf ("have\n");
            }
            else
                    printf ("no have\n");
    
    
            HashTableDelete(&ht,23);
            printf ("size=%d\n",HashTableSize(&ht));
            if (-1!=HashTableFind(&ht,33))
            {
                    printf ("have\n");
            }
            else
                    printf ("no have\n");
    }
    
    
    int main ()
    {
            TestHashTable();
            return 0;
    }
    -- INSERT --                                                                                                               258,2         Bot
    

     

     

    这里就完成了我们关于哈希表的代码。大家有什么意见或者建议,或者哪里不清楚可以留言呦!

    展开全文
  • Console.WriteLine("********************哈希查找(C#版)********************\n"); //创建哈希表 for (int i = 0; i < list.Count; i++) { Insert(hashTable,list[i]); } Console.WriteLine("展示哈希...
  • 数据结构哈希查找

    2021-01-30 22:36:04
    数据结构之查找哈希查找哈希函数构造方法冲突解决办法哈希查找分析 哈希查找 哈希查找是通过设定的哈希函数H(key)和处理冲突的办法将关键字映射的一个地址集(区间),并将关键字在地址集中的“像”作为在表中的存储...
  • 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。⑴用给定的哈希函数构造哈希表;⑵根据选择的冲突处理方法解决地址冲突;⑶在哈希表的基础上执行哈希查找。构造哈希函数:直接定址法、数字分析法、平方取...
  • 哈希表进行查找代码,数据结构中创建哈希表,解决冲突等等

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 108,968
精华内容 43,587
关键字:

哈希查找代码