精华内容
下载资源
问答
  • 哈希查找速度
    千次阅读
    2017-10-12 20:30:47
    哈希算法存取之所以快,是因为其 直接通过关键字key得到要存取的记录内存存储位置


    试想这样的场景,你很想学太极拳,听说学校有个叫张三丰的人打得特别好,于是你到学校学生处找人,学生处的工作人员可能会拿出学生名单,一个一个的查找,最终告诉你,学校没这个人,并说张三丰几百年前就已经在武当山作古了。可如果你找对了人,比如在操场上找那些爱运动的同学,人家会告诉你,"哦,你找张三丰呀,有有有,我带你去。于是他把你带到了体育馆内,并告诉你,那个教大家打太极的小伙子就是张三丰',原来"张三丰.是因为他太极拳打得好而得到的外号。学生处的老师找张三丰,那就是顺序表查找,依赖的是姓名关键字的比较。而通过爱好运动的同学询问时,没有遍历,没有比较,就凭他们"欲找太极'张三丰',必在体育馆当中"的经验,直接告诉你位置。


    也就是说,我们只需要通过某个函数f,使得:存储位置=f (关键字)


    那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。这就是一种新的存储技术一一散列技术(哈希算法)。


    散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key 对应一个存储位置f (key)。查找时,根据这个确定的对应关系找到给定值key 的映射f (key) ,若查找集合中存在这个记录,则必定在f (key) 的位置上。这里我们把这种对应关系f 称为散列函数, 又称为哈希(Hash) 函数。按这个思想,采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。 那么关键字对应的记录存储位置我们称为散列地址。


    整个散列过程其实就是两步。
    (1) 在存储时,通过散列函数计算记录的散列地址,并按此散列地址存储该记录。
    (2) 当查找记录时,我们通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录。由于存取用的是同一个散列函数, 因此结果当然也是相同的。


    所以说,散列技术既是一种存储方法,也是一种查找方法。然而它与线性表、树、图等结构不同的是,前面几种结构,数据元素之间都存在某种逻辑关系,可以用连线图示表示出来,而散列技术的记录之间不存在什么逻辑关系,它只与关键字有关联。因此,散列主要是面向查找的存储结构。


    我们时常会碰到两个关键字key1 != key2,但是却有f(key1) = f(key2),这种现象我们称为哈希冲突,如果没有哈希冲突,散列表是一种非常高效的查找数据结构,其时间复杂度为O(1);

    更多相关内容
  • 哈希查找

    2018-01-04 16:38:09
    哈希表和哈希函数 在记录的存储位置和它的关键字之间是建立一个确定的对应关系(映射函数),使每个...若查找关键字为 key,则其值存放在 f(key) 的存储位置上。由此,不需比较便可直接取得所查记录。 注:哈希

    简述

    数组的特点是:寻址容易,插入和删除困难;

    而链表的特点是:寻址困难,插入和删除容易。

    那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?

    答案是肯定的,这就是我们要提起的哈希表。






    Hash的应用

    1、Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系。

    2、查找:哈希表,又称为散列,是一种更加快捷的查找技术。我们之前的查找,都是这样一种思路:集合中拿出来一个元素,看看是否与我们要找的相等,如果不等,缩小范围,继续查找。而哈希表是完全另外一种思路:当我知道key值以后,我就可以直接计算出这个元素在集合中的位置,根本不需要一次又一次的查找!

    举一个例子,假如我的数组A中,第i个元素里面装的key就是i,那么数字3肯定是在第3个位置,数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想,建立一个从key到位置的函数,然后进行直接计算查找。

    3、Hash表在海量数据处理中有着广泛应用。


    优缺点

    优点:不论哈希表中有多少数据,查找、插入、删除(有时包括删除)只需要接近常量的时间即0(1)【时间复杂度】的时间级。实际上,这只需要几条机器指令。

    哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。

    如果不需要有序遍历数据,并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

    缺点:它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序员必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

    

    哈希表和哈希函数

    在记录的存储位置和它的关键字之间是建立一个确定的对应关系(映射函数),使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数,根据这个原则建立的表称为哈希表(Hash Table),也叫散列表

    以上描述,如果通过数学形式来描述就是:

    若查找关键字为 key,则其值存放在 f(key) 的存储位置上。由此,不需比较便可直接取得所查记录

    注:哈希查找与线性表查找和树表查找最大的区别在于,不用数值比较。

     

    冲突

    若 key1 ≠ key2 ,而 f(key1) = f(key2),这种情况称为冲突(Collision)。

    根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这一映射过程称为构造哈希表

    构造哈希表这个场景就像汽车找停车位,如果车位被人占了,只能找空的地方停。

     

     

     

     

    构造哈希表

    由以上内容可知,哈希查找本身其实不费吹灰之力,问题的关键在于如何构造哈希表和处理冲突。

    常见的构造哈希表的方法有 5 种:

    (1)直接定址法

    说白了,就是小学时学过的一元一次方程

    即 f(key) = a * key + b。其中,a和b 是常数。

     

    (2)数字分析法

    假设关键字是R进制数(如十进制)。并且哈希表中可能出现的关键字都是事先知道的,则可选取关键字的若干数位组成哈希地址。

    选取的原则是使得到的哈希地址尽量避免冲突,即所选数位上的数字尽可能是随机的。

     

    (3)平方取中法

    取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,仅取其中的几位为地址不一定合适;

    而一个数平方后的中间几位数和数的每一位都相关, 由此得到的哈希地址随机性更大。取的位数由表长决定。

     

    (4)除留余数法

    取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。

    即 f(key) = key % p (p ≤ m)

    这是一种最简单、最常用的方法,它不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。

    注意:p的选择很重要,如果选的不好,容易产生冲突。根据经验,一般情况下可以选p为素数

     

    (5)随机数法

    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 f(key) = random(key)。

    通常,在关键字长度不等时采用此法构造哈希函数较为恰当。

     

     

    解决冲突

    设计合理的哈希函数可以减少冲突,但不能完全避免冲突。

    所以需要有解决冲突的方法,常见有两类

    (1)开放定址法

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

    例子

    若要将一组关键字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。

    采用除留余数法构造哈希表;采用开放定址法处理冲突。

    不妨设选取的p和m为13,由 f(key) = key % 13 可以得到下表。

    需要注意的是,在上图中有两个关键字的探查次数为 2 ,其他都是1。

    这个过程是这样的:

    a. 12 % 13 结果是12,而它的前面有个 25 ,25 % 13 也是12,存在冲突。

    我们使用开放定址法 (12 + 1) % 13 = 0,没有冲突,完成。

    b. 35 % 13 结果是 9,而它的前面有个 9,9 % 13也是 9,存在冲突。

    我们使用开放定址法 (9 + 1) % 13 = 10,没有冲突,完成。

     

    (2)拉链法

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

    在这种方法中,哈希表中每个单元存放的不再是记录本身,而是相应同义词单链表的头指针。

    例子

    如果对开放定址法例子中提到的序列使用拉链法,得到的结果如下图所示:


    左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。


    实现一个哈希表

    假设要实现一个哈希表,要求

    a. 哈希函数采用除留余数法,即 f(key) = key % p (p ≤ m)

    b. 解决冲突采用开放定址法,即 f2(key) = (f(key)+i) % size (p ≤ m)

     

    (1)定义哈希表的数据结构

    class HashTable {
         public  int key = 0;  //  关键字
         public  int data = 0;  //  数值
         public  int count = 0;  //  探查次数
    }

     

    (2)在哈希表中查找关键字key

    根据设定的哈希函数,计算哈希地址。如果出现地址冲突,则按设定的处理冲突的方法寻找下一个地址。

    如此反复,直到不冲突为止(查找成功)或某个地址为空(查找失败)。

    复制代码
    /**
     * 查找哈希表
     * 构造哈希表采用除留取余法,即f(key) = key mod p (p ≤ size)
     * 解决冲突采用开放定址法,即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
     * ha为哈希表,p为模,size为哈希表大小,key为要查找的关键字
     
    */
    public  int searchHashTable(HashTable[] ha,  int p,  int size,  int key) {
         int addr = key % p;  //  采用除留取余法找哈希地址

        
    //  若发生冲突,用开放定址法找下一个哈希地址
         while (ha[addr].key != NULLKEY && ha[addr].key != key) {
            addr = (addr + 1) % size;
        }

         if (ha[addr].key == key) {
             return addr;  //  查找成功
        }  else {
             return FAILED;  //  查找失败
        }
    }
    复制代码

     

    (3)删除关键字为key的记录

    在采用开放定址法处理冲突的哈希表上执行删除操作,只能在被删记录上做删除标记,而不能真正删除记录。

    找到要删除的记录,将关键字置为删除标记DELKEY。
    复制代码
    public  int deleteHashTable(HashTable[] ha,  int p,  int size,  int key) {
         int addr = 0;
        addr = searchHashTable(ha, p, size, key);
         if (FAILED != addr) {  //  找到记录
            ha[addr].key = DELKEY;  //  将该位置的关键字置为DELKEY
             return SUCCESS;
        }  else {
             return NULLKEY;  //  查找不到记录,直接返回NULLKEY
        }
    }
    复制代码

     

    (4)插入关键字为key的记录

    将待插入的关键字key插入哈希表
    先调用查找算法,若在表中找到待插入的关键字,则插入失败;
    若在表中找到一个开放地址,则将待插入的结点插入到其中,则插入成功。 
    复制代码
    public  void insertHashTable(HashTable[] ha,  int p,  int size,  int key) {
         int i = 1;
         int addr = 0;
        addr = key % p;  //  通过哈希函数获取哈希地址
         if (ha[addr].key == NULLKEY || ha[addr].key == DELKEY) {  //  如果没有冲突,直接插入
            ha[addr].key = key;
            ha[addr].count = 1;
        }  else {  //  如果有冲突,使用开放定址法处理冲突
             do {
                addr = (addr + 1) % size;  //  寻找下一个哈希地址
                i++;
            }  while (ha[addr].key != NULLKEY && ha[addr].key != DELKEY);

            ha[addr].key = key;
            ha[addr].count = i;
        }
    }
    复制代码

     

    (5)建立哈希表

    先将哈希表中各关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字序列依次插入。

    复制代码
    public  void createHashTable(HashTable[] ha,  int[] list,  int p,  int size) {
         int i = 0;
        
         //  将哈希表中的所有关键字清空
         for (i = 0; i < ha.length; i++) {
            ha[i].key = NULLKEY;
            ha[i].count = 0;
        }

         //  将关键字序列依次插入哈希表中
         for (i = 0; i < list.length; i++) {
             this.insertHashTable(ha, p, size, list[i]);
        }
    }
    
    展开全文
  • 查找算法之哈希查找

    千次阅读 2018-06-11 21:04:22
      哈希也称散列,哈希表是一种与数组、链表等不同的数据结构,与他们需要不断的遍历比较来查找的办法,哈希表设计了一个映射关系f(key)= address,根据key来计算存储地址address,这样可以1次查找,f既是存储数据...

      哈希也称散列,哈希表是一种与数组、链表等不同的数据结构,与他们需要不断的遍历比较来查找的办法,哈希表设计了一个映射关系f(key)= address,根据key来计算存储地址address,这样可以1次查找,f既是存储数据过程中用来指引数据存储到什么位置的函数,也是将来查找这个位置的算法,叫做哈希算法。

    1、相关名词

    1. :哈希表中存储数据的位置,每一个位置对应唯一的一个地址,桶就好比一个记录。

    2. :每一个记录中可能包含很多字段,每一个字段就是槽。

    3. 碰撞/冲突:若不同的数据经过哈希函数运算后对应到了相同的地址,就成为碰撞/冲突。

    4. 溢出:如果数据经过哈希运算后,对应到的桶已满,则会发生溢出。

    2、哈希查找算法的实现(链地址法/拉链法)

      如果遇到冲突,哈希表一般是怎么解决的呢?具体方法有很多,最常用的就是开发定址法和链地址法。链地址法的原理是把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0…m-1]存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。

    这里写图片描述

    #include <iostream>
    #include <vector>
    #include <list>
    #include <random>
    #include <ctime>
    using namespace std;
    
    const int hashsize = 12;
    
    //定一个节点的结构体
    template <typename T, typename U>
    struct HashNode 
    {
        T _key;
        U _value;
    };
    
    //使用拉链法实现哈希表类
    template <typename T, typename U>
    class HashTable
    {
    public:
        HashTable() : vec(hashsize) {}//类中的容器需要通过构造函数来指定大小
        ~HashTable() {}
        bool insert_data(const T &key, const U &value);
        int hash(const T &key);
        bool hash_find(const T &key);
    private:
        vector<list<HashNode<T, U>>> vec;//将节点存储到容器中
    };
    
    //哈希函数(除留取余)
    template <typename T, typename U>
    int HashTable<T, U>::hash(const T &key)
    {
        return key % 13;
    }
    
    //哈希查找
    template <typename T, typename U>
    bool HashTable<T, U>::hash_find(const T &key)
    {
        int index = hash(key);//计算哈希值
        for (auto it = vec[index].begin(); it != vec[index].end(); ++it)
        {
            if (key == it -> _key)//如果找到则打印其关联值
            {
                cout << it->_value << endl;//输出数据前应该确认是否包含相应类型
                return true;
            }
        }
        return false;
    }
    
    //插入数据
    template <typename T, typename U>
    bool HashTable<T, U>::insert_data(const T &key, const U &value)
    {
        //初始化数据
        HashNode<T, U> node;
        node._key = key;
        node._value = value;
        for (int i = 0; i < hashsize; ++i)
        {
            if (i == hash(key))//如果溢出则把相应的键值添加进链表
            {
                vec[i].push_back(node);
                return true;
            }
        }
    }
    
    int main(int argc, char const *argv[])
    {
        HashTable<int, int> ht;
        static default_random_engine e;
        static uniform_int_distribution<unsigned> u(0, 100);
        long long int a = 10000000;
        for (long long int i = 0; i < a; ++i)
            ht.insert_data(i, u(e));
        clock_t start_time = clock();
        ht.hash_find(114);
        clock_t end_time = clock();
        cout << "Running time is: " << static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC * 1000 <<
            "ms" << endl;//输出运行时间。
        system("pause");
        system("pause");
        return 0;
    }
    

    3、STL中的hash算法

      hash_*系列例如hash_map,hash_set 等已经被废弃了,C++11用unordered_map,unordered_set等来替代

    #include <iostream>
    #include <string>
    #include <random>
    #include <unordered_set>
    #include <unordered_map>
    using namespace std;
    int main(int argc, char const *argv[])
    {
    	unordered_set<int> ht;
        static default_random_engine e;
        static uniform_int_distribution<unsigned> u(0, 100);
        long long int a = 1000;
        for (long long int i = 0; i < a; ++i)
            ht.insert(u(e));
        if (ht.find(1) != ht.end())
        	cout << "get it!" << endl;
        
        unordered_map<int, string> mymap;
        mymap[1] = "A";
        mymap[2] = "B";
        mymap[3] = "C";
        if(mymap.find(1) != mymap.end())
        {
        	cout << mymap[1] << endl;
        }
        system("pause");
    	return 0;
    }
    

    四、哈希冲突的解决方法

      经过哈希运算后的索引值发生重复时,就会产生碰撞的问题,而碰撞的情况在数据量很大时特别容易发生。

    1、开放地址法

    (1)线性探测法

      当冲突发生时,以线性的方式往后寻找空的存储位置,一旦找到一个位置就把数据放进去。但是线性探测容易聚集
    在这里插入图片描述

    (2)平方探测法

      平方探测法:以增量序列1^2 -1^2, 2^2, -2^2, …… , q^2, -q^2。且 q<= [ TableSize/2 ] 循环试探下一个存储地址。
    在这里插入图片描述

    2、再哈希法

      再哈希法就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次哈希,直至不发生冲突位置

      缺点:每次冲突都要重新散列,计算时间增加

    3、链地址法(拉链法)

    在这里插入图片描述
      拉链法的平均查找长度较短,更适合于造表前无法确定表长的情况,删除结点的操作易于实现缺点是需要额外的空间

    五、不同处理冲突的平均查找长度

    在这里插入图片描述
      装填因子( a a a) = 哈希表中的记录数(实际元素个数) / 哈希表的长度。

    1、线性探测法的平均查找长度

    在这里插入图片描述
      查找不成功:即从当前位置往后的第一个不为空的位置的距离。例如:
    在这里插入图片描述
    在这里插入图片描述

    2、链地址法的平均查找长度

    在这里插入图片描述在这里插入图片描述

    六、算法总结

    1、哈希表的性能

      由于哈希表高效的特性,查找或者插入的情况在大多数情况下可以达到O(1),时间主要花在计算hash上,当然也有最坏的情况就是hash值全都映射到同一个地址上,这样哈希表就会退化成链表,查找的时间复杂度变成O(n),但是这种情况比较少,只要不要把hash计算的公式外漏出去并且有人故意攻击。

    2、拉链法的优缺点

    优点:
      解决了哈希表堆聚现象,减小了平均查找长度。删除结点相对于线性探测更加易于实现,只需要找到相应结点再删除就可以了,而开放地址法中不能这样做,因为在哈希表中置空数组中的结点会导致后面的数据无法访问。

    缺陷:
      当数据量比较小的时候,开放地址法不用开辟空间,如果相对于拉链法节省的结点空间用来扩大散列表则可以使装填因子(结点数与表长的比值),这样也就减少了开放地址法的冲突,提高平均查找速度。

    (3) Hash的应用

    1、Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系。

    2、查找:哈希表,又称为散列,是一种更加快捷的查找技术。我们之前的查找,都是这样一种思路:集合中拿出来一个元素,看看是否与我们要找的相等,如果不等,缩小范围,继续查找。而哈希表是完全另外一种思路:当我知道key值以后,我就可以直接计算出这个元素在集合中的位置,根本不需要一次又一次的查找!

    举一个例子,假如我的数组A中,第i个元素里面装的key就是i,那么数字3肯定是在第3个位置,数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想,建立一个从key到位置的函数,然后进行直接计算查找。

    3、Hash表在海量数据处理中有着广泛应用。

    参考:https://www.cnblogs.com/s-b-b/p/6208565.html
    https://blog.csdn.net/MBuger/article/details/62418754
    https://blog.csdn.net/duan19920101/article/details/51579136
    https://blog.csdn.net/haishu_zheng/article/details/77278119

    展开全文
  • 本节讨论两类不同的查找表:静态查找表和动态查找表,给出在不同查找表上进行查找的不同算法和性能分析以及动态查找表的创建方法。 1 查找的基本概念 静态查找: 基于线性表的查找 动态查找: 基于树的查找(二叉...

    整理内容来源:zzu信息工程学院数据结构ppt
    本节讨论两类不同的查找表:静态查找表动态查找表,给出在不同查找表上进行查找的不同算法和性能分析以及动态查找表的创建方法。

    1 查找的基本概念

    静态查找:

    • 基于线性表的查找

    动态查找:

    • 基于树的查找(二叉排序树、平衡二叉排序树、B-树和B+树)
    • 基于散列表的查找

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2 基于线性表的查找

    2.1 定义和分类

    在这里插入图片描述
    基于线性表的查找主要是两部分:(索引顺序表用的不是很多)

    • 顺序查找(适用于两种存储结构)
    • 折半查找(有序表)

    注意区分 “有序”“顺序”:有序表中的“有序”是逻辑意义上的有序,指表中的元素按某种规则已经排好了位置。顺序表中的“顺序”是物理意义上的,指线形表中的元素一个接一个的存储在一片相邻的存储区域中。可以粗略地将“顺序表”理解为数组,将“有序表”理解为排好的数组。

    2.2 顺序查找

    2.2.1 思想

    从表中第一条/最后一条记录开始,逐个进行记录的关键字与给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,返回其在顺序表中的位序;反之,若直至最后一条/第一条记录其关键字和给定值比较都不等,则查找不成功,返回0

    2.2.2 算法实现

    监视哨:为能自动检验数组下标越界,在0下标处设置哨兵,若查找不成功,则循环会在0下标处自动终止,函数返回0

    int  Search_Seq( SSTable  ST,  KeyType key ){  
    	ST.elem[0].key = key; //0下标为监视哨
        for(i = ST.length; !EQ(ST.elem[i].key,key ); --i);           
        return i;              
    }//Search_Seq 
    

    举例:
    在这里插入图片描述

    2.2.3 性能分析

    这么暴力的做法时间复杂度当然不会低了
    在这里插入图片描述
    这里对O(n)可能没什么感觉,我们再往下看。

    2.3 折半查找

    折半查找在算法题中用的很多了,我之前专门写过关于折半查找的博客:算法 - 二分查找

    2.3.1 定义

    折半查找(二分查找):先确定待查记录所在范围,逐步缩小范围,直到找到或找不到该记录止。
    不过应注意,折半查找的应用范围是:有序表
    二分查找的思想和具体实现可参考那篇博客。

    2.3.2 判定树

    在这里插入图片描述

    2.3.3 性能分析

    时间复杂度为O(logn),当数量级比较大时,时间复杂度的差异就体现出来了。详见下图:
    在这里插入图片描述

    2.4 索引顺序表

    索引顺序表就不展开讲了,它的特点是:分块有序、块内无序。

    • 分块有序:用折半查找
    • 块内无序:用顺序查找

    在这里插入图片描述

    3 二叉排序树(二叉查找树、BST)

    3.1 定义

    二叉排序树是指空树或具有下列性质的二叉树:(不得不感慨课件确实很严谨)

    • 根的左子树若非空,则左子树上所有结点的关键字值均小于根结点的关键字值;
    • 根的右子树若非空,则右子树上所有结点的关键字值均大于根结点的关键字值;
    • 它的左右子树同样是二叉排序树。

    可以看出,这是一种递归式定义。

    3.2 查找过程

    • 若二叉排序树为空,则查找失败,返回空指针;
    • 若二叉排序树不空:
      • 首先将给定值和根结点的关键字比较,若相等则查找成功,返回根结点的地址。
      • 若给定值小于根结点的关键字值,则在其左子树上继续查找;
      • 若给定值大于根结点的关键字值,则在其右子树上继续查找。

    关于二叉排序树的算法实现,我们选用的存储结构是链式存储结构,即(lchild, data, rchild)
    原因是:链式存储结构可以快速实现插入和删除操作。
    具体的算法如下:

    BiTree SearchBST(BiTree T, KeyType key){
    	if((!T) || EQ(key,T->data.key)) return T;
    	if(LT(key,T->data.key)) 
    		return SearchBST(T->lchild, key); 
      	else return SearchBST(T->rchild, key);
    } //SearchBST 
    

    3.2 插入、构造方法

    在这里插入图片描述
    我们对查找算法可以适当修改,修改后的查找算法如下:

    Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){  //修改后的查找算法
       if(!T){  p=f;  return FALSE;  } 
       else if EQ(key,T->data.key)     
         {  p=T;   return TRUE;  }
       else if LT(key,T->data.key)          
    	   return SearchBST(T->lchild,key,T,p);    
       else return SearchBST(T->rchild,key,T,p); 
    }// SearchBST 
    

    其实对查找算法就是修改了如果查找不成功的话,对这个叶子结点进行了记录。(利用&p)

    ----------------------(乱入,前面的内容push一下)----------------
    在这里突然想到了“指针和引用的区别”,之前看过一篇文章一直存着,分享给大家:指针与引用, 值传递与地址传递的关系
    ----------------------(前面的内容pop出来)---------------------------

    如果得到了叶子结点,那我们就可以进行二叉排序树的插入操作了:

    Status InsertBST(BiTree &T, ElemType e)
    {
       if(!SearchBST(T,e.key,NULL,p))       
       {
         s=(BiTree)malloc(sizeof(BiTNode));             
         if(!s)   exit(OVERFLOW);
         s->data = e;     s->lchild = s->rchild = NULL; 
         if(!p) T=s;                   
         else if LT(e.key, p->data.key)   p->lchild = s;
         else   p->rchild = s;                 
         return TRUE;
       }
       else return FALSE;                    
    } 
    

    插入的示例和补充:
    在这里插入图片描述
    注意这里啊,在插入时,我们不需要移动其他结点,只需要修改一个结点的指针就好了。
    并且我们还应注意到,BST的建树过程就是查找失败时元素不断插入的过程。

    3.3 删除

    对于一般的二叉树,删去树中的一个结点会破坏整棵树的结构。对二叉排序树,删去一个结点相当于删去有序序列中的一个记录。
    在这里插入图片描述
    在删除时,我们有以下几种情况:
    在这里插入图片描述
    在这里插入图片描述
    注意上面这种情况,不管被删结点是只有左子树还是只有右子树,都把它的某个子树挂到它的父节点的子树上。

    在这里插入图片描述
    在这里插入图片描述
    个人喜欢第2种。

    3.4 性能分析

    在等概率情况下,完全二叉树的查找效率最高。在随机的情况下,二叉排序树的平均查找长度和O(logn)是等数量级的。
    其实看到这了难道不觉得和折半查找的判定树很像嘛,就是平均情况下。两者的原理是一样的。
    这里为什么要说“等概率情况”呢,因为有n个结点的二叉排序树并不唯一,平均查找长度与二叉排序树的形态有关,而二叉排序树的形态由关键字的插入顺序决定。比如插入顺序是1234531254构造的排序树是不同的。前者深度大,查找效率自然低了(前者其实等价于顺序查找)。
    怎样可以忽略关键字的插入顺序呢,这就是下面要介绍的平衡二叉排序树了。

    4 平衡二叉树(AVL树)

    4.1 定义

    平衡二叉树(AVL树):它或者是一棵空树,或者是满足下列性质的二叉树:

    • 其左、右子树深度之差的绝对值不大于1
    • 其左、右子树都是平衡二叉树

    害,怎么说呢,又是一个递归定义。(习惯了
    那么为什么要引入平衡二叉树呢,在二叉排序树的性能分析中我们已经看到,若一棵二叉排序树是平衡的,则树上任何结点的左右子树的深度之差不超过1,二叉树的深度与log2n同数量级。这样就可以保证它的平均查找长度与log2n同数量级。
    举个例子:
    在这里插入图片描述

    4.2 构造

    在这里插入图片描述
    这里就要介绍一种比较高级的平衡旋转技术:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    举个例子:10,5,15,12,20,14,30,18,35,2,0,3,4,构造该序列的平衡二叉排序树:
    其实没有图片画的那么复杂,这个平衡旋转技术还是很有感觉的。(就描述不出的平衡感
    在这里插入图片描述

    4.3 性能分析

    和BST树一样,性能是O(log2n)

    5 B-、B+树

    5.1 B-树的定义

    在这里插入图片描述
    这个定义需要强调两点:

    • 结点中的关键字个数至多为m-1(因为每个结点至多有m棵子树)
    • 根至少有一个关键字(因为若根结点不是叶子结点,至少有两棵子树)

    定义还有一个小要求:
    在这里插入图片描述
    给一个B-树的例子,便于理解。
    在这里插入图片描述

    5.2 引入B-树的原因

    前面介绍的查找方法适用于待查记录数较小的文件,查找时记录都读入内存中进行处理,统称为内查找法。若文件很大,查找时不能把记录全部读入内存(大量数据仍存放在硬盘上)时,则查找过程需要反复进行内、外存交换。
    由于硬盘的驱动受机械运动的制约,速度慢。所以提高查找效率的关键就是减少访问外存的次数。
    1970年R bayer和E macreight提出用B-树作为索引组织文件,提高访问速度、减少时间。B-树具有占用存储空间少、查找效率高等优点,常用在文件系统和数据库系统的索引技术中。
    举个例子:
    用二叉树组织文件,当文件的记录个数为106时,树高平均为17(log2106)。若以256阶B-树组织数据,则树高最多仅为3

    5.3 B-树的查找过程

    在这里插入图片描述
    查找操作的两个过程是:

    • 沿指针搜索结点(在磁盘中进行)
    • 在结点内进行查找(在内存中进行,因为前一步找到结点后会把结点内的信息读入内存中处理)

    在结点内进行查找一般是顺序查找或折半查找,而沿指针搜索结点的过程如下:
    从根开始查找,如果 Ki = KEY 则查找成功。

    • Ki < KEY < Ki+1; 查找 Ai 指向的结点
    • KEY < K1; 查找 A0 指向的结点
    • KEY > Kn; 查找 An指向的结点
    • 若 找到叶子,则查找失败。

    5.4 B-树的查找分析

    在磁盘上进行一次查找比在内存中进行一次查找耗时多很多,因此B-树的查找效率主要取决于访问外设的次数,即:取决于待查关键字所在结点在B-树上的层次数
    比如:
    设N=106,m=256,则h<=3,即最多访问外存3次可找到所有的记录。
    最后提一嘴关于B-树,B树就是B-树,不知道是谁把B-Tree翻译成B-树,误导了当年的我,想当年我一直不知道B树和B-树是一个玩意儿……

    5.5 B+树

    B+树是B-树的变异树。
    一棵mB+树和mB-树的差异:

    • n棵子树的结点中含有n个关键字;
    • 所有的叶子节点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子节点本身依关键字的大小自小而大顺序链接。
    • 所有的非终端节点可以看成是索引部分,结点中仅含有其子树(根结点)中的最大(或最小)关键字

    这个定义应该不难理解。
    当时B+树没要求掌握,所以课件上给的东西也很少。

    5.6 B+树的查找

    • 从最小关键字顺序查找
    • 从根开始随机查找

    6 哈希查找

    这个我就不写了,之前写过一篇。可以参考文章:【数据结构】【哈希】哈希表的概念和算法实现

    7 总结

    最后呢,总结一下查找的时间复杂度:

    • 顺序查找:O(n)
    • 折半查找:O(logn),(O(log2n)) 因为要先快排所以总复杂度为O(nlogn)
    • 二叉排序树(二叉查找树、BST):O(logn)(平均情况下)
    • 平衡二叉排序树(AVL树):O(logn)(O(log2n))
    • B树:O(logn) (O(log2n))
    • 哈希查找:O(1)
    展开全文
  • C++哈希查找算法简单实现

    千次阅读 2019-11-29 17:18:59
    也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含...
  • 顺序查找也叫线性查找,是按照序列原有顺序对数组进行遍历比较查询的基本查找算法,顺序查找是最简单的搜索算法,其实现如下: def seq_search(li,val): for ind,v in enumerate(li): if v == val: return ind # ...
  • 【数据结构Python】查找哈希算法

    千次阅读 2022-03-07 19:49:52
    顺序查找 #以随机数生成1~150之间的80个整数,然后实现顺序查找 import random val=0 data=[0]*80 for i in range(80): data[i]=random.randint(1,150) while val!=-1: find=0 val=int(input('请输入查找键值(1-...
  • 二分查找二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。首先,假设表中元素是按升序排列,将表中间位置记录...
  • 先看数组存储数据是怎么样的。 现在有一个数组,它里面每个单元存储的是数据的地址 ...是一种乱放,既然是乱放,那么查找起来就比较耗时。 哈希表是怎么存储数据的呢? 哈希表同样是一个指针数组。 同样需要...
  • 所以一开始我也很难理解为什么查找速度可以达到O(1)。 其原因简单来说是通过建立key值与地址的映射关系,即哈希函数。 假设如下图这样一张表,保存4个人的姓名和电话号码,可通过vector<pair<...
  • 顺序查找是最普通的一种查找方式,它的基本原理:将要查找的元素与从线性表的开始到最后的每个元素进行逐个比较,看是否有匹配的 话不多说上代码: public class Demo4 { //顺序查找 static ArrayList<Integer...
  • 哈希查找效率及应用场景

    千次阅读 2017-10-26 18:19:22
    哈希查找效率及应用场景
  • 一、顺序查找  条件:无序或有序队列。  原理:按顺序比较每个元素,直到找到关键字为止。  时间复杂度:O(n)  二、二分查找(折半查找)  条件:有序数组  原理:查找过程从数组的中间元素开始,...
  • 【查找算法】哈希查找

    千次阅读 2020-02-26 12:44:45
    本篇文章将介绍一种新的查找算法——哈希查找。 文章目录何为哈希查找?散列表冲突构造散列函数直接定址法除留余数法解决冲突的方式开放地址法链地址法 何为哈希查找? 先看定义: 哈希查找是通过计算数据元素的...
  • 哈希函数的定义3.哈希表 1.哈希函数的定义 一般情况下,需在关键字与记录在表中的存储位置之间建立一个函数关系,以 H(key) 作为关键字为key 的记录在表中的位置,通常称这个函数 h(key) 为哈希函数。 哈希函数...
  • Hash函数与算法、哈希查找、哈希冲突解决方法总结

    千次阅读 多人点赞 2019-09-01 22:02:57
    Hash哈希 1.基本概念   Hash,也叫哈希或散列,就是把任意长度的输入(也叫预映射),通过散列算法,变换成固定长度的输出,该输出就是散列值。   若结构中存在和关键字key相等的记录,则必定在H(key)的存储位置...
  • 哈希表的插入、删除、查找的时间复杂度都是 O(1); 而平衡二叉查找树的插入、删除、查找的时间复杂度都是 O(logn)。 哈希速度快,但缺点明显,被反杀: 散列表中的数据是无序存储的,如果要输出有序的数据,需要...
  • 为此,将哈希表和多比特树相结合,提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中,采用哈希表存储路由下一跳的信息,根据目的IP地址在二层Tree结构中按最长前缀匹配的原则进行...
  • 【算法与数据结构 10】哈希表——高效查找的利器

    千次阅读 多人点赞 2020-09-24 17:03:21
    查找方面,哈希表的速度比树还要快,基本可以瞬间查找到想要的元素。 不足:哈希表中的数据是没有顺序概念的,所以不能以一种固定的方式(比如从小到大)来遍历其中的元素。在数据处理顺序敏感的问题时,选择哈希...
  • 避免 这个问题的一个方法就是使用一个哈希函数来约束簇块的数量。哈希函数将会给定一个数值用来限定簇块数量的预计范围,但它得到的值是相对等分布的。哈希函数中存在的一个问题就是函数值会打乱记录原本的顺序。你...
  • 哈希索引能否进行范围查找? 本文的问题来自于博主遇到的一个面试问题。博主与面试官的对线顺序如下: 面试官: 数据库的索引结构有哪些? 我:B+索引,hash索引,fulltext索引? 面试官:那你对比说明一下B+索引和...
  • 本文从数据结构角度认识哈希表,更多关于Java...因此,在面对查找问题时,这些数据结构必须采取逐一比较的方法去实现。 而哈希表的设计采用了函数映射的思想,将记录的存储位置与记录的关键字关联起来。这样的设计方
  • 我在电信行业和信息安全行业里的工作经历发现,目前网络上的哈希算法都在查询速度上远远无法满足日趋增长的网络大数据要求。因此产生了自己写算法的想法。 现在我把自己的算法初稿发布出来,用我在一家信息安全的...
  • 算法:哈希

    2022-03-25 20:54:48
    也就是说,它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value,然后把键值对映射到表中一个位置来访问记录,以加快查找速度。这个映射函数叫做哈希函数(散列函数),用于存放记录的数组叫做 哈希...
  • 数据结构--哈希查找

    千次阅读 2018-12-29 21:23:53
    哈希查找也是一种查找方式,在此之前,如果了解其它查找方法,然后对比该方法最好 本篇文章主要从两个方面介绍哈希表,一是哈希表的构造方法,另一个是哈希表的处理冲突方法。 同时,本篇文章介绍元素类型为数字...
  • 哈希表去除数据中的重复项 哈希表(Hash Table,也...哈希表通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做哈希函数,存放记录的数组称做哈希表。
  • 如果有一种方法,可以实现“地址 = f (关键字)”的映射关系,那么就可以快速完成基于数据的数值的查找了。这就是哈希表的核心思想。 如何设计哈希函数 我们先看一些常用的设计哈希函数的方法: 第一,直接定制法 ...
  • 终于下定决心把查找和排序好好整一整,今天就弄了一个对分查找,也成为对半查找。原理十分简单,话不多说,直接上源代码。未完待续,持续更新中。。。 1、对半查找,要求输入有序序列。 // sort.cpp : 定义控制台...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 92,807
精华内容 37,122
关键字:

哈希查找速度