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

    2020-09-25 18:59:16
    哈希查找 散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这...

    哈希查找

    Hash查找算法流程:

    • 用给定的哈希函数构造哈希表
    • 根据选择的冲突处理方法解决哈希冲突问题(在构建哈希表时出现两个关键字经过散列函数映射到相同哈希值,这种现象叫哈希冲突)。

    散列表

    散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。由于Hash不仅要为数值分配空间,也要为键分配空间,所以它是一种典型的空间换时间算法。

    散列函数

    散列函数的规则:通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。
    具体的散列函数计算方法如下:

    • 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即hash(k) = k 或 hash(k) = a · k + b,其中a、b为常数(这种散列函数叫做自身函数)
    • 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
    • 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
    • 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
    • 随机数法
    • 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k) = k mod p, p<=m。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

    哈希冲突解决办法

    拉链法

    通过哈希函数,我们可以将键转换为数组的索引(0-M-1),但是对于两个或者多个键具有相同索引值的情况,我们需要有一种方法来处理这种冲突。一种比较直接的办法就是,将大小为M 的数组的每一个元素指向一个链表,链表中的每一个节点都存储散列值为该索引的键值对,这就是拉链法。下图很清楚的描述了什么是拉链法(“John Smith”和“Sandra Dee” 通过哈希函数都指向了152 这个索引,该索引又指向了一个链表, 在链表中依次存储了这两个字符串)。
    在这里插入图片描述
    单独链表法:将散列到同一个存储位置的所有元素保存在一个链表中(聚集),该方法的基本思想就是选择足够大的M,使得所有的链表都尽可能的短小,以保证查找的效率。当链表过长、大量的键都会映射到相同的索引上,哈希表的顺序查找会转变为链表的查找,查找时间将会变大。对于开放寻址会造成性能的灾难性损失。
    在这里插入图片描述实现基于拉链表的散列表,目标是选择适当的数组大小M,使得既不会因为空链表而浪费内存空间,也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于,这种数组大小M的选择不是关键性的,如果存入的键多于预期,那么查找的时间只会比选择更大的数组稍长。另外,我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期,索然有些浪费空间,但是查找速度就会很快。所以当内存不紧张时,我们可以选择足够大的M,可以使得查找时间变为常数,如果内存紧张时,选择尽量大的M仍能够将性能提高M倍。

    开放寻址法

    线性探测法:使用大小为M的数组来保存N个键值对,其中M>N,我们需要使用数组中的空位解决碰撞冲突。如下图所示:
    在这里插入图片描述对照前面的拉链法,在该图中,“Ted Baker” 是有唯一的哈希值153的,但是由于153被“Sandra Dee”占用了。而原先“Snadra Dee”和“John Smith”的哈希值都是152的,但是在对“Sandra Dee”进行哈希的时候发现152已经被占用了,所以往下找发现153没有被占用,所以索引加1 把“Sandra Dee”存放在没有被占用的153上,然后想把“Ted Baker”哈希到153上,发现已经被占用了,所以往下找,发现154没有被占用,所以值存到了154上。

    哈希查找实现

    基于C实现的单独链表法Hash查找。

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    
    typedef struct node
    {
    	int nValue;
    	int nIndex;
    	struct node *pNext;
    }Hash;
    
    Hash **CreatHashTable(int arr[], int length)
    {
    	if(arr==NULL || length<0) return NULL;
    	Hash **pHash = (Hash**)malloc(sizeof(Hash*)*length);
    	memset(pHash, 0, sizeof(Hash*)*length);
    	
    	int i;
    	int nIndex;
    	Hash *pTemp = NULL;
    	for(i=0;i<length;i++)
    	{
    		nIndex = arr[i] % length;
    		pTemp = (Hash*)malloc(sizeof(Hash));
    		pTemp->nValue = arr[i];
    		pTemp->nIndex = i;
    		pTemp->pNext = pHash[nIndex];
    		pHash[nIndex] = pTemp;
    	}
    	return pHash;
    }
    
    int HashSearch(Hash **pHash, int length, int num)
    {
    	if(pHash == NULL || length < 0) return -1;
    	int nIndex = num % length;
    	Hash *pTemp = pHash[nIndex];
    	while(pTemp)
    	{
    		if(pTemp->nValue == num)
    		{
    			return pTemp->nIndex;
    		}
    		pTemp = pTemp->pNext;
    	}
    	return -1;
    }
    
    int main()
    {
    	int arr[] = {1, 2, 101, 6, 201, 19, 18};
    	Hash **pHash = CreatHashTable(arr, sizeof(arr)/sizeof(arr[0]));
    	int nIndex = HashSearch(pHash, sizeof(arr)/sizeof(arr[0]), 101);
    	printf("%d \n", nIndex);
    	return 0;
    }
    
    
    展开全文
  • 【查找算法】哈希查找

    千次阅读 2020-02-26 12:44:45
    本篇文章将介绍一种新的查找算法——哈希查找。 文章目录何为哈希查找?散列表冲突构造散列函数直接定址法除留余数法解决冲突的方式开放地址法链地址法 何为哈希查找? 先看定义: 哈希查找是通过计算数据元素的...

    本篇文章将介绍一种新的查找算法——哈希查找。

    何为哈希查找?

    先看定义:

    哈希查找是通过计算数据元素的存储地址进行查找的一种方法。

    哈希查找通过给定的哈希函数构造哈希表(也叫散列表),然后通过计算存储地址进行元素查找。

    所以我们先来聊聊散列表。

    散列表

    散列是一种新的存储方式,它既不是按给定形式顺序存储,也不是毫无规律地进行存储,而是通过计算元素的存储地址实现存储。

    计算元素存储地址的基本思想是:记录的存储位置与关键字之间存在对应关系,这个对应关系称为一个hash函数。

    举个例子,现有一个数据元素序列,{1,3,5,7,9},若规定每个元素k的存储地址H(k) = k,则其存储结构

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

    千次阅读 2017-10-26 18:08:53
    查找算法之哈希查找

    引言:哈希查找,也称为散列查找(本文以哈希称呼),在介绍哈希查找之前,我们先了解一下什么是哈希函数、哈希表

    1、哈希函数

    哈希技术是在记录的存储位置和它的key之间建立一个确定的对应关系f,使得每个key对应一个存储位置f(key)。建立了key与存储位置的映射关系,公式如存储位置 = f(key 这里把这种对应关系f称为哈希(Hash)函数

    2、哈希表

    采用哈希技术将key存在在一块连续的存储空间中,这块连续存储空间称为哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

    六种哈希函数的构造方法:

    1,直接定址法:

    函数公式:f(key)=a*key+b (a,b为常数) 

    比如:关键字是2,a=1,b=1,那么2+1=3就为存储位置。

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

    2,数字分析法:

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

    若我们现在要存储某家公司员工登记表,如果用手机号码作为关键字,那么极有可能前7位都是相同的,所以我们选择后面的四们作为哈希地址就是不错的选择。

    3,平方取中法:

    故名思义,比如关键字是1234,那么它的平方就是1522756,再抽取中间的3位就是227作为哈希地址。

    4,折叠法:

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

    比如我们的关键字是9876543210,哈希表表长三位,我们将它分为四组,987|654|321|0 ,然后将它们叠加求和987+654+321+0=1962,再求后3位即得到哈希地址为962,哈哈,是不是很有意思。

    5,除留余数法:

    函数公式:f(key)=key mod p (p<=m)m为哈希表表长。

    这种方法是最常用的哈希函数构造方法。

    6,随机数法:

    函数公式:f(key)= random(key)。

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

    设计得最好的哈希函数也不可能完全避免冲突,当我们在使用哈希函数后发现两个关键字key1!=key2,但是却有f(key1)=f(key2),即发生冲突。解决冲突,有2种方法

    方法一:开放定址法:

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

    C#实现代码:

    namespace HashSearch.CSharp

    {

        class Program

        {

            //初始化哈希表

            static int hashLength = 7;

            static int[] hashTable= new int[hashLength];

     

            //原始数据

            static List<int> list = new List<int>() { 13,29,27,28,26,30,38 };

     

            static void Main(string[] args)

            {

                Console.WriteLine("********************哈希查找(C#版)********************\n");

                

                //创建哈希表

                for (int i = 0; i < list.Count; i++)

                {

                    Insert(hashTable,list[i]);

                }

                Console.WriteLine("展示哈希表中的数据:{0}",String.Join(",",hashTable));

     

                while (true)

                {

                    //哈希表查找

                    Console.Write("请输入要查找的数据:");

                    int data = int.Parse(Console.ReadLine());

                    var result = Search(hashTable, data);

                    if (result == -1) Console.WriteLine("对不起,没有找到!");

                    else Console.WriteLine("数据的位置是:{0}", result);

                }

            }

     

            /// <summary>

            /// 哈希表插入

            /// </summary>

            /// <param name="hashTable">哈希表</param>

            /// <param name="data">待插入值</param>

            public static void Insert(int[] hashTable, int data)

            {

                //哈希函数,除留余数法

                int hashAddress = Hash(hashTable,data);

     

                //如果不为0,则说明发生冲突

                while (hashTable[hashAddress] != 0)

                {

                    //利用开放定址的线性探测法解决冲突

                    hashAddress = (++hashAddress) % hashTable.Length;

                }

     

                //将待插入值存入字典中

                hashTable[hashAddress] = data;

            }

     

            /// <summary>

            /// 哈希表查找

            /// </summary>

            /// <param name="hashTable">哈希表</param>

            /// <param name="data">待查找的值</param>

            /// <returns></returns>

            public static int Search(int[] hashTable, int data)

            {

                //哈希函数,除留余数法

                int hashAddress = Hash(hashTable,data);

     

                //冲突发生

                while (hashTable[hashAddress] != data)

                {

                    //利用开放定址的线性探测法解决冲突

                    hashAddress = (++hashAddress) % hashTable.Length;

     

                    //查找到了开放单元或者循环回到原点,表示查找失败

                    if (hashTable[hashAddress] == 0 || hashAddress==Hash(hashTable,data)) return -1;

                }

                //查找成功,返回值的下标

                return hashAddress;

            }

     

            /// <summary>

            /// 哈希函数(除留余数法)

            /// </summary>

            /// <param name="hashTable">待操作哈希表</param>

            /// <param name="data"></param>

            /// <returns>返回数据的位置</returns>

            public static int Hash(int[] hashTable, int data)

            {

                return data % hashTable.Length;

            }

        }

    }

    (2)   链地址法

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








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

    千次阅读 2018-04-11 19:14:30
    今天面试中遇到一个查找问题,典型的属于哈希查找算法可以解决,我居然懵逼了很尴尬 ̄□ ̄||,之前在数据结构中学过Hash表,后来有没有复习,现在在这里再总结归纳一下吧。 没有复习之前提到Hash我一直以为是IPFS...

    今天面试中遇到一个查找问题,典型的属于哈希查找算法可以解决,我居然懵逼了很尴尬 ̄□ ̄||,之前在数据结构中学过Hash表,后来有没有复习,现在在这里再总结归纳一下吧。
    没有复习之前提到Hash我一直以为是IPFS里面的Hash校验算法,算是理解比较片面吧。

    使用哈希表快速查找字符串

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    哈希表hashtable(key,value) 的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。
    而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位

    解决哈希(HASH)冲突的主要方法

    使用哈希表快速查找字符串的一种解决方案

    看了之后明明是之前考研学过的东西,要被自己气死了。。。

    从两个文件(各含50亿个url)中找出共同的url、不同的url

    问题:
    给定a、b两个文件,各存放50亿个url,每个url各占用64字节,内存限制是4G,如何找出a、b文件共同的url?
    解法一:

    可以估计每个文件的大小为5G*64=300G (50亿是5000000000,即5G),远大于4G。

    所以不可能将其完全加载到内存中处理,考虑采取分而治之的方法。
    遍历文件a,对每个url求取hash(url)%1000,然后根据所得值将url分别存储到1000个小文件(设为a0,a1,…a999)当中。这样每个小文件的大小约为300M。

    遍历文件b,采取和a相同的方法将url分别存储到1000个小文件(b0,b1….b999)中。

    这样处理后,所有可能相同的url都在对应的小文件(a0 vs b0, a1 vs b1….a999 vs b999)当中,不对应的小文件(比如a0 vs b99)不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
    比如对于a0 vs b0,我们可以遍历a0,将其中的url存储到hash_map当中。然后遍历b0,如果url在hash_map中,则说明此url在a和b中同时存在,保存到文件中即可。
    如果分成的小文件不均匀,导致有些小文件太大(比如大于2G),可以考虑将这些太大的小文件再按类似的方法分成小小文件即可。

    展开全文
  • 1.二分查找 二分查找就是折半查找,其基本思想是:首先选取表中间位置的记录,将其关键字与给定的关键字key进行比较,若相等,则查找成功;若key值比该关键字值大,则要找的元素一定在右子表中,则继续对右子表...
  • 哈希查找效率及应用场景

    千次阅读 2017-10-26 18:19:22
    哈希查找效率及应用场景
  • 也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含...
  • 哈希函数的定义3.哈希表 1.哈希函数的定义 一般情况下,需在关键字与记录在表中的存储位置之间建立一个函数关系,以 H(key) 作为关键字为key 的记录在表中的位置,通常称这个函数 h(key) 为哈希函数。 哈希函数...
  • 顺序查找也叫线性查找,是按照序列原有顺序对数组进行遍历比较查询的基本查找算法,顺序查找是最简单的搜索算法,其实现如下: def seq_search(li,val): for ind,v in enumerate(li): if v == val: return ind # ...
  • 一、顺序查找 顺序查找适合于存储结构为顺序存储或链接存储的线性表。 基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若...
  • 二分查找二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。首先,假设表中元素是按升序排列,将表中间位置记录...
  • 哈希查找

    2020-02-01 10:43:23
     哈希表可以以极快的速度查找、添加或删除元素(只需要数次的比较操作。)由于查找的时候不需要比较,所以它比二分查找、红黑树、二叉搜索树都要快得多。但是哈希表没有排序功能,类似的,如寻找最大值、最小值、...
  • 顺序查找是最普通的一种查找方式,它的基本原理:将要查找的元素与从线性表的开始到最后的每个元素进行逐个比较,看是否有匹配的 话不多说上代码: public class Demo4 { //顺序查找 static ArrayList<Integer...
  • 先看数组存储数据是怎么样的。 现在有一个数组,它里面每个单元存储的是数据的地址 ...是一种乱放,既然是乱放,那么查找起来就比较耗时。 哈希表是怎么存储数据的呢? 哈希表同样是一个指针数组。 ...
  • Hash函数与算法、哈希查找、哈希冲突解决方法总结

    千次阅读 多人点赞 2019-09-01 22:02:57
    Hash哈希 1.基本概念   Hash,也叫哈希或散列,就是把任意长度的输入(也叫预映射),通过散列算法,变换成固定长度的输出,该输出就是散列值。   若结构中存在和关键字key相等的记录,则必定在H(key)的存储位置...
  • python数据结构与算法 29-1 哈希查找

    千次阅读 2014-04-22 08:20:16
    前面的章节中,我们利用数据集中元素的相对位置信息来提高查找算法的性能。比如知道列表是有序的,可以使用二分查找。本节我们走得更远一些,创建一个数据结构,使得查找性能提高到O(1),称为哈希查找
  • 链地址法的基本思想是:将所有哈希地址为i 的元素构成一个称为同义词链的链表,并将链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。  该散列方法首先对关键码集合用某一个...
  • java实现顺序查找、二分查找哈希查找、二叉排序树查找
  • 本题中,我们需要一种数据结构可以让我们通过读取字符从而查找到对应的出现次数,并且我们要尽可能的提高查找速度 所以我们就会考虑到一种数据结构——哈希表,详情请点击点击打开链接 我们都知道,通过哈希表,...
  • 查找可以分为静态查找和动态查找。 静态查找 定义: 在查找过程中,只是对数据元素执行查找操作,而不对其执行其他操作。 顺序查找 折半查找 索引查找 通常用线性表来表示静态查找表,线性表有顺序存储结构和...
  • 先看数组存储数据是怎么样的。 现在有一个数组,它里面每个单元存储的是数据的地址 ...是一种乱放,既然是乱放,那么查找起来就比较耗时。 哈希表是怎么存储数据的呢? 哈希表同样是一个指针数组。 同样需要...
  • 这种基本思想:将所有哈希地址为i 的元素构成一个称为同义词链的链表,并将链表的头指针存在哈希表的第i个单元中,因而查找、 插入和删除主要在同义词链中进行。  该散列方法首先对关键码集合用某一个散列函数...
  • 常见的数据查找算法主要有顺序查找,二分查找,深度优先遍历,广度优先遍历,哈希查找. 顺序查找是最简单的查找方式,需要对数据注意匹配,所以...哈希查找由于查找速度快,查询、插入、删除操作简单等原因而被广泛使用。 ...
  • 哈希查找也是一种查找方式,在此之前,如果了解其它查找方法,然后对比该方法最好 本篇文章主要从两个方面介绍哈希表,一是哈希表的构造方法,另一个是哈希表的处理冲突方法。 同时,本篇文章介绍元素类型为数字...
  • 终于下定决心把查找和排序好好整一整,今天就弄了一个对分查找,也成为对半查找。原理十分简单,话不多说,直接上源代码。未完待续,持续更新中。。。 1、对半查找,要求输入有序序列。 // sort.cpp : 定义控制台...
  • 哈希表及其查找

    万次阅读 2011-02-27 21:14:00
     哈希查找的基本思想是:根据当前待查找数据的特征,以记录关键字为自变量,设计一个哈希函数,依该函数按关键码计算元素的存储位置,并按此存放;查找时,由同一个函数对给定值key计算地址,将key与地址...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 79,692
精华内容 31,876
关键字:

哈希查找速度