精华内容
下载资源
问答
  • 该题目来自58同城二面,用最快速度求两个数组之交集算法。 比如A={6,2,4,1},B={2,9,4,3},那么A&B={2,4}。   算法一:在大多数情况,也就是一般情况下,大家都能想出最暴力解法,通常也...

    一个题目

    该题目来自58同城的二面,用最快速度求两个数组之交集算法。

    比如A={6,2,4,1},B={2,9,4,3},那么A&B={2,4}。

     

    算法一:在大多数情况,也就是一般的情况下,大家都能想出最暴力的解法,通常也就是采用遍历或者枚举的办法来解决问题。

    该题需要找出两个数组的交集,最简单的一个办法就是用A数组里面的所有数去匹配B数组里面的数。假设两个数组的大小都是n,那么这种遍历的时间复杂度为O(n^2)。这个也是最复杂的情况了。

     

    算法二:通常下,除了用暴力枚举的问题,还有另外一种外万金油的解法----预处理。其实思想和C语言中的预处理一样,对数据记性归一化处理。说白了,在这里就是对数组排序。我们知道数组排序的算法时间复杂度最低是O(nlogn),可以看到数量级已经低于算法一的时间复杂度。

    那么在排好序好,怎么得到数组的交集呢?

    假设我们已经有了两个排好序的数组:

    A={1,2,4,6}

    B={2,3,4,9}

    那么我们只要分别对A和B设置两个指针i,j(或者直接说是下标),进行循环,伪代码如下:

    int count()

    {

    total=i=j=0;

    while(i<n && j<n)

    {

    if(a[i]<b[j]) i++;

    else if(a[i]>b[j])j++

    else

        total++;

    }

        return total;

    }

    时间复杂度为O(n)

    综合排序的时间复杂度则整体复杂度为:O(nlogn)

     

     

    算法三:如果只是会了上面两种,还只能说是计算机的菜鸟,而且一般面试或者笔试题也不会这么简单。那么比O(nlogn)时间复杂度更低的是多少呢?一般就是O(n)。我们可以思考一下计数排序的算法。也就是把两个数组A和B都遍历到一个新的数组里,然后在统计重复的数字即可,这个时间复杂度就是O(n)。当然,计数排序是有条件的,也就是要求数组内数字的范围是已知并且不是很大。

     

     

    算法四:上面的算法实现简单,也很容易达到题目的要求,但是还是有一些瑕疵,也就是非完美方案,同样根据算法三我们可以想出用哈希函数或者哈希表来解决问题。也就是将数组A哈希到哈希表中,然后继续将数组B哈希到哈希表中,如果发生哈希碰撞则统计加1,最后可以得出数组的交集。时间复杂度也就是哈希所有元素的复杂度O(n)。

     

    那么什么是哈希呢?

     

     Hash ,一般翻译做“ 散列” ,也有直接音译为“ 哈希” 的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不 同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

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

    例如字符串 hello 的哈希算法

    char* value = "hello"; int key = (((((((27* (int)'h'+27)* (int)'e') + 27)  * (int)'l') + 27) * (int)'l' +27) * 27 ) + (int)'o' ; 。

     

      数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易 的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“ 链表 的数组” ,如图:


     

     

     

    HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

     

        1.首先HashMap里面实现一个静态内部类Entry 其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基 础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

         2.既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

     

    Java代码  收藏代码

    1. 存储时:  
    2.   
    3. int hash = key.hashCode();--> 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值  
    4.   
    5. int index = hash % Entry[].length;  
    6.   
    7. Entry[index] = value;  
    8.   
    9. 取值时:  
    10.   
    11. int hash = key.hashCode();  
    12.   
    13. int index = hash % Entry[].length;  
    14.   
    15. return Entry[index]  

     

    到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理

        3.疑问:如果两个key通过hash % Entry[].length得到的index相同,会不会有覆盖的危险?

    这里HashMap里面用到链式数据结构的一个概念.上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A.一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。

    到这里为止,HashMap的大致实现,我们应该已经清楚了。

    当然HashMap里面也包含一些优化方面的实现,这里也啰嗦一下。

    比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?

    HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。

     

     

    解决hash冲突的办法

    1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)

    2)再哈希法

    3)链地址法

    4)建立一 公共溢出区

     

    java 中hashmap的解决办法就是采用的链地址法。

    展开全文
  • php的hash算法介绍

    2020-10-26 06:54:23
    PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法...对于字符串而言这是目前所知道的最好的哈希算法,原因在于该算法速度非常,而且分类非常好(冲突小,分布均匀)
  • Hash算法

    2010-07-17 16:58:15
    据说,Hash的优劣顺序为:BKDRHash, APHash, DJBHash, JSHash, RSHash, ...因为BKDRHash最快(据说也最好背),ELFHash最准确(冲突率最低)。   public static int BKDRHash(String str) { // BKDR Hash Fu...

     

    据说,Hash的优劣顺序为:BKDRHash, APHash, DJBHash, JSHash, RSHash, SDBMHash, PJWHash, ELFHash。应该是从速度区分吧。因为BKDRHash最快(据说也最好背),ELFHash最准确(冲突率最低)。

     

    	public static int BKDRHash(String str) { // BKDR Hash Function
    
    		int seed = 31; // 31 131 1313 13131 131313 etc..
    
    		int hash = 0;
    
    		int i = 0;
    
    		while (i < str.length()) {
    
    			hash = hash * seed + str.charAt(i);
    
    			i++;
    
    		}
    		//return (hash & 0x7FFFFFFF);
    		return hash;
    
    	}

     

    一个HashMap的简单实现:

     

    package com.hash.test;
    
    public class TestHash {
    
    	public static int BKDRHash(String str) { // BKDR Hash Function
    
    		int seed = 31; // 31 131 1313 13131 131313 etc..
    		int hash = 0;
    		int i = 0;
    		while (i < str.length()) {
    			hash = hash * seed + str.charAt(i);
    			i++;
    		}
    		// return (hash & 0x7FFFFFFF);
    		return hash;
    	}
    
    	public static String[] data = new String[20];
    
    	public static void put(String str) {
    		int key = BKDRHash(str) % 20;
    		System.out.println(key);
    		data[key] = str;
    	}
    
    	/**
    	 * Test
    	 */
    	public static void main(String[] args) {
    
    		String str = "key";
    		for (int i = 0; i < 20; i++) {
    			put(str + i);
    		}
    		System.out.println(data[BKDRHash(str + 1) % 20]);
    
    	}
    
    }
    
     

     

     

    附:各种哈希函数的C语言程序代码

     

    unsigned int SDBMHash(char *str)
    
    
    {
    	unsigned int hash = 0;
     
    	while (*str)
    	{
    		// equivalent to: hash = 65599*hash + (*str++);
    		hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // RS Hash 
    unsigned int RSHash(char *str)
    {
    	unsigned int b = 378551;
    	unsigned int a = 63689;
    	unsigned int hash = 0;
     
    	while (*str)
    	{
    		hash = hash * a + (*str++);
    		a *= b;
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // JS Hash 
    unsigned int JSHash(char *str)
    {
    	unsigned int hash = 1315423911;
     
    	while (*str)
    	{
    		hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // P. J. Weinberger Hash 
    unsigned int PJWHash(char *str)
    {
    	unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    	unsigned int ThreeQuarters	= (unsigned int)((BitsInUnignedInt  * 3) / 4);
    	unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);
    	unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt 
    
                                                   - OneEighth);
    	unsigned int hash	= 0;
    	unsigned int test	= 0;
     
    	while (*str)
    	{
    		hash = (hash << OneEighth) + (*str++);
    		if ((test = hash & HighBits) != 0)
    		{
    			hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
    		}
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // ELF Hash 
    unsigned int ELFHash(char *str)
    {
    	unsigned int hash = 0;
    	unsigned int x	= 0;
     
    	while (*str)
    	{
    		hash = (hash << 4) + (*str++);
    		if ((x = hash & 0xF0000000L) != 0)
    		{
    			hash ^= (x >> 24);
    			hash &= ~x;
    		}
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // BKDR Hash 
    unsigned int BKDRHash(char *str)
    {
    	unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    	unsigned int hash = 0;
     
    	while (*str)
    	{
    		hash = hash * seed + (*str++);
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // DJB Hash 
    unsigned int DJBHash(char *str)
    {
    	unsigned int hash = 5381;
     
    	while (*str)
    	{
    		hash += (hash << 5) + (*str++);
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     
    // AP Hash 
    unsigned int APHash(char *str)
    {
    	unsigned int hash = 0;
    	int i;
     
    	for (i=0; *str; i++)
    	{
    		if ((i & 1) == 0)
    		{
    			hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
    		}
    		else
    		{
    			hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
    		}
    	}
     
    	return (hash & 0x7FFFFFFF);
    }
     

     

     

    展开全文
  • 思路:使用数组hash。index代表集合中数。value为代表集合。 class DSU { int[] parent; //可初始化大小 public DSU() { parent = new int[10001]; for (int i = 0; i <= 10000; ++i)

    1. DSU(并查集)

    1. 条件:需要查询小范围的数据集合,不包含特殊数字。同时数字>=1。

    思路:使用数组hash。index代表集合中的数。value为代表集合。

      class DSU {
            int[] parent;
    		//可初始化大小
            public DSU() {
                parent = new int[10001];
                for (int i = 0; i <= 10000; ++i)
                    parent[i] = i;
            }
    
            /**
             * 找到x的父类
             *
             * @param x
             * @return
             */
            public int find(int x) {
    
                if (parent[x] != x) parent[x] = find(parent[x]);
                return parent[x];
            }
    
            public void union(int x, int y) {
                parent[find(x)] = find(y);
            }
        }
          public void findUnion(int[] a, int[] b) {
            DSU dsu = new DSU();
            for (int i = 0; i < a.length; i++) {
                dsu.union(a[i], 0);
            }
            for (int i = 0; i < b.length; i++) {
                if (dsu.find(b[i]) == 0) {
                    System.out.println(b[i]);
                }
            }
        }
    

    时间复杂度O(m+n)空间复杂大为a中最大数字。所以说存在限制条件。只能处理最多(1->正无穷的数字),我们需要0作为并查集的父。

    2. 排序指针移动

    //排好序后比较移动指针
    public int[] findUnion(int[] nums1, int[] nums2) {
    		Arrays.sort(nums1);
    		Arrays.sort(nums2);
    		int len1=nums1.length;
    		int len2=nums2.length;
    		ArrayList<Integer> al=new ArrayList<Integer>();
    		for(int i=0,j=0;i<len1 && j<len2;) {
    			if(nums1[i] == nums2[j]) {
    				al.add(nums1[i]);
    				i++;
    				j++;
    			}
    			else if(nums1[i] > nums2[j]) {
    				j++;
    			}
    			else {
    				i++;
    			}	
    		}
     
    		int[] in = new int[al.size()];
    		int e=0;
    		for(int i:al)
    			in[e++] = i;
    		return in;
    	}
    

    3. Hash算法

    可用HashSet,或者HashMap进行完成。
    Hash的快速查找通过key的hashcode进行完成,可快速定位到桶,O(1)。
    可做之前放入个数比较小的数组,然后遍历另外一个数组来查找,是否在Hash的数据结构中。完成交集算法。

    展开全文
  • 今天做的模块又用到了Hash函数,突然想起Hash函数可能会比较占CPU资源,所以希望使用一种速度最快的摘要函数。但是PHP中的Hash函数很多,MD4、MD5、SHA-1、SHA-256、SHA-384以及SHA-512,都是比较常见的安全领域...

    今天做的模块又用到了Hash函数,突然想起Hash函数可能会比较占CPU资源,所以希望使用一种速度最快的摘要函数。但是PHP中的Hash函数很多,MD4、MD5、SHA-1、SHA-256、SHA-384以及SHA-512,都是比较常见的安全领域的HASH应用。于是写了个程序对比了一下PHP支持的各种Hash函数:

     

    <?php
    define('testtime', 50000);
    $algos = hash_algos();
    foreach($algos as $algo) {
        $st = microtime();
        for($i = 0; $i < testtime; $i++) {
            hash($algo, microtime().$i);
        }
        $et = microtime();
        list($ss, $si) = explode(' ', $st);
        list($es, $ei) = explode(' ', $et);
        $time[$algo] = $ei + $es - $si - $ss;
    }
    asort($time, SORT_NUMERIC);
    print_r($time);
    ?>

     

    此程序测试每种hash函数支持的算法,对50000个字符串执行hash计算,然后将耗时按从低到高排序,结果如下:

    Array
    (
        [crc32b] => 1.14942403926
        [crc32] => 1.15080493481
        [adler32] => 1.17250810205
        [md4] => 1.21484698894
        [md5] => 1.25582505324
        [sha256] => 1.31992111638
        [ripemd256] => 1.34005199425
        [ripemd128] => 1.34174097336
        [sha1] => 1.34424093234
        [ripemd160] => 1.36161398381
        [haval128,3] => 1.37490507759
        [haval160,3] => 1.37925811601
        [haval192,3] => 1.37971906387
        [haval224,3] => 1.38690299403
        [haval256,3] => 1.38968507692
        [tiger128,3] => 1.40321999939
        [tiger192,3] => 1.42025405684
        [tiger160,3] => 1.42113689062
        [ripemd320] => 1.42461802158
        [haval128,4] => 1.4465580045
        [haval160,4] => 1.44935391309
        [haval192,4] => 1.45606506625
        [haval224,4] => 1.4650528846
        [tiger128,4] => 1.47951410777
        [tiger192,4] => 1.49081709387
        [haval256,4] => 1.50713596634
        [haval160,5] => 1.51613600436
        [haval224,5] => 1.51645894888
        [haval192,5] => 1.51678603177
        [haval256,5] => 1.51900808377
        [tiger160,4] => 1.52507308815
        [haval128,5] => 1.53689793875
        [whirlpool] => 1.82801189377
        [snefru] => 1.85931909387
        [gost] => 1.89863007236
        [sha384] => 1.95804009064
        [sha512] => 1.97130295938
        [md2] => 4.99702701607
    )

    CRC是冗余验证算法,不适合用来做唯一标识符Hash计算,MD4是最快的摘要算法,MD5次之,SHA系列算法居然是SHA-256最快,比SHA-1还快一些。由此得出结论:要把唯一标识符转换成定长字串可以考虑使用MD4,而密码加密则SHA-1或SHA-256更合适。MD5就没有多少使用的必要了,速度比不过MD4,安全性比不过SHA,还是趁早放弃的好。

     

    转载于:https://www.cnblogs.com/wicub/p/6269112.html

    展开全文
  • 2.要求缓存速度快 3.用lru算法控制内存大小 **LRU是什么?**按照英文直接原义就是Least Recently Used,最近久未使用法,它是按照一个非常著名计算机操作系统基础理论得来:最近使用页面数据会在未来一段...
  • 10)个自然数,每个数的范围为 1 - 100,用最快的速度判断某个数是否在这N个数内。 二分(前提是数据有序) 排序+顺序查找 哈希查找(利用数组下标映射要查找的值) 散列表即HashTable ,也就是我们常说的哈希表...
  • 算法介绍(hash,MD5)

    2019-10-02 15:10:04
    基本概念:hash,也称作散列、杂凑或者哈希,能把任意长度输入,通过hash算法转化为固定长度输出,是一种压缩映射。打的特点就是从无法从结果推算出输入内容,所以称之为不可逆算法。 哈希特性: 过程不...
  • 1. hash表需求: 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...
  • Blizzard哈希算法

    2009-05-02 23:32:35
    是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢,答案是,远远不够,要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题,哈希表是一个大数组,这个数组的...
  • 算法介绍】哈希排序算法

    千次阅读 2019-09-25 01:21:14
    哈希排序算法(Hash),是目前我认为速度最快的排序算法之一,时间复杂度为O(n),而且我认为很简单。它的主体思路是:定义一个数组,每个元素表示它的下标在数列中的个数,最后用循环完成排序。 例如给你一个上限不...
  • STL中map与hash_map比较 map : C++STL中map是使用树来做查找算法;...总体来说:hash_map 比 map 查找速度快,而且查找速度基本和数据量大小无关,属于常数级别,节省一定内存,如果没有必要...
  • hash查找

    千次阅读 2015-07-20 17:14:46
    查找算法hash查找是最快的.但是它需要先构造hash表,构造hash表之后利用hash函数在hash表中查找的速度是非常迅速的 所以时间复杂度是O(1) 最常用的构造散列函数的方法是: 除留余数法 F(key) = key mod P (P )...
  • HASH表原理

    2019-10-03 18:21:56
    HASH表原理大家都知道,在所有线性数据结构中,数组定位速度最快,因为它可通过数组下标直接定位到相应数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据结构解决以上问题。 ...
  • 趣谈 Hash

    2018-04-10 16:36:16
    答: 这就得从hash算法说起了。查找速度的困扰算法国自建立起,就以快速为至高荣誉,O(n^2) 时间复杂度设计常常被人嫌弃,一般都想着弄个O(logn)算法国最近遇到了一个问题,就是随着处理数据逐步增大,查找...
  • dHash速度快,判断效果也要好。 实现过程 缩小尺寸。将图片缩小为9*8大小,此时照片有72个像素点。 灰度化处理。 计算差异值,获得最后哈希值(与aHash主要区别处)。比较每行左右两个像素,如果左边像素比右边...
  • 最新kali之hashcat

    2021-01-21 21:38:56
      Hashcat是世界上最快的基于CPU的密码恢复工具。   尽管它的速度不及其GPU同类产品oclHashcat,但通过良好的字典和对命令开关的一点了解,可以轻松地将大型列表一分为二。   Hashcat是自称为世界上最快的基于...
  • hashcat是世界上速度最快,最先进密码恢复工具,支持五种独特攻击模式,支持200多种高度优化哈希算法hashcat目前支持Linux,Windows和macOS上CPU,GPU和其他硬件加速器,并且具有帮助实现分布式密码破解...
  • HASH表原理(装)

    2014-05-20 22:18:00
    HASH表原理大家都知道,在所有线性数据结构中,数组定位速度最快,因为它可通过数组下标直接定位到相应数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据结构解决以上问题。 ...
  • 基于Hash的数据类型有哪些4.1 为什么字典查询速度快,且基本不受字典大小影响4.2 集合为什么能去重 1. 什么是哈希 Hash,一般翻译为散列、杂凑,或者音译为哈希,是把任意长度输入(又叫做预映射pre-image)...
  • 显然C++STL默认使用树结构来实现map,树查找,在总查找效率上比不上hash表,...假若你在开发一个供外部调用接口,其内部有关键字查找,但是这个接口调用并不频繁,你是会希望其调用速度快、但不稳定呢,还是希
  • 哈希表据说对于数据库处理,存储和搜索来说是非常快的。现在我必须说它们是! 这是一个固定的列表数组。 每个键都散列到一个索引中,我们试图使其尽可能唯一。 如果运气不好(或错误的哈希算法)使两个键最终具有...
  • 针对上述问题,提出了一种面向海量电子凭据分层可扩展存储架构,结合hash取模算法和一致性hash算法实现快速数据定位,设计了基于hash取模算法横向扩展方案,减少了节点增删时迁移数据量。此外,设计并实现了...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 124
精华内容 49
关键字:

速度最快的hash算法