精华内容
下载资源
问答
  • HASH排序

    千次阅读 2019-03-21 17:11:54
    HASH排序原理: 将Value值作为下标,存放在一个conut数组里面。以count数组对应下标的值为计重复次数。遍历count数组。对有值的进行打印下标。完成排序。整体的时间复杂度取决于数组最大数字。 代码如下: int...

    HASH排序原理:

    将Value值作为下标,存放在一个conut数组里面。以count数组对应下标的值为计重复次数。遍历count数组。对有值的进行打印下标。完成排序。整体的时间复杂度取决于数组最大数字。

    代码如下:

        	int a[9] = {123,122,345,678,123,568,122,122,122};
    	int count[1000] = {};
    	for (int i = 0; i < 9; i++)
    	{
    		count[a[i]]++;
    	}
    	for (int i = 0; i < 1000; i++)
    	{
               for(int j = 0; j < count[i]; j++)
               {
                    cout<<i<<endl;
               }
    	}
    	system("pause");

     

    展开全文
  • 目前,大多数Hash排序算法通过比较数据在欧氏空间和海明空间的排序一致性来构造损失函数,然而,在海明空间的排序过程中,因为海明距离是离散的整数值,可能存在多个数据点共享相同的海明距离,这样就无法准确地排序...
  • hash排序的实现

    2016-12-17 16:22:48
    hash排序与插入排序相比,把相差每个间隔进行排序,变为相差increment的个数进行排序,这样的复杂读度会有一定的降低。 #include using namespace std; void hashsort(int a[],int num) { int i,j,increment,temp;...
    hash排序与插入排序相比,把相差每个间隔进行排序,变为相差increment的个数进行排序,这样的复杂读度会有一定的降低。
    #include <iostream>
    using namespace std;
    void hashsort(int a[],int num)
    {
    int i,j,increment,temp;
    for(increment=num/2;increment>0;increment=increment/2)
    for(int i=increment;i<num;i++)
      { temp=a[i];
       for(j=i;j>=increment;j-=increment)
       if(a[j-increment]>temp)
         a[j]=a[j-increment];
       else
         break;
      a[j]=temp;
      }
     }
    
    int main()
    {
    int a[10]={10,9,8,7,6,5,4,3,2,1};
    hashsort(a,10);
    for(int i=0;i<10;i++)
    cout<<a[i]<<" ";
    return 0;
    }


    展开全文
  • 请问hash索引还需要维护hash的顺序么?hash排序和数据排序哪个检索的效率比较高呢?
  • hash排序和hash索引到底在vb代码中怎么用?有用hash制成控件调用的思路是什么呢?怎么对dat文件进行检索?
  • 怎么使用hash排序代替二分查找排序呢?二分排序是不是比hash排序需要的时间多?dat怎么查找数据效率最高?
  • 请问在hash查找和hash排序之中,如果要精确查找dat中的数据,是使用什么方法?是索引算法还是排序算法呢?
  • ruby hash排序

    2017-12-12 14:45:00
    a={a:1,b:20,c:3,d:0,e:7 } 逆序 a.sort{ |k,v| v[1]<=>k[1]} ...执行sort时hash被转为一个二维数组,进行的比较是对这个二维数组的比较 转载于:https://www.cnblogs.com/znsongshu/p/8027719.html

    参考文章:http://blog.csdn.net/ppp8300885/article/details/49933305

    a={a:1,b:20,c:3,d:0,e:7}
    逆序 a.sort{
    |k,v| v[1]<=>k[1]}

    输出 [[:b, 20], [:e, 7], [:c, 3], [:a, 1], [:d, 0]] 
    正序
    a.sort_by{|k,v| v}
    输出 [[:d, 0], [:a, 1], [:c, 3], [:e, 7], [:b, 20]]
    执行sort时hash被转为一个二维数组,进行的比较是对这个二维数组的比较

    转载于:https://www.cnblogs.com/znsongshu/p/8027719.html

    展开全文
  • 桶排序(hash排序

    万次阅读 2017-06-17 16:17:29
    让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(NlgN)。 排完序之后我们...

    第一部分:Top K 算法详解
    问题描述

    百度面试题:

    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。

    假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

    必备知识:
    什么是哈希表?

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。(常用的数组就是一个哈希表)

    哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

    而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位(文章第二、三部分,会针对Hash表详细阐述)。
    问题解析:

    要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。

    即,此问题的解决分为以下俩个步骤:
    第一步:Query统计

    Query统计有以下俩个方法,可供选择:
    1、直接排序法

    首先我们最先想到的的算法就是排序了,首先对这个日志里面的所有Query都进行排序,然后再遍历排好序的Query,统计每个Query出现的次数了。

    但是题目中有明确要求,那就是内存不能超过1G,一千万条记录,每条记录是225Byte,很显然要占据2.55G内存,这个条件就不满足要求了。

    让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(NlgN)。

    排完序之后我们再对已经有序的Query文件进行遍历,统计每个Query出现的次数,再次写入文件中。

    综合分析一下,排序的时间复杂度是O(NlgN),而遍历的时间复杂度是O(N),因此该算法的总体时间复杂度就是O(N+NlgN)=O(NlgN)。
    2、Hash Table法

    在第1个方法中,我们采用了排序的办法来统计每个Query出现的次数,时间复杂度是NlgN,那么能不能有更好的方法来存储,而时间复杂度更低呢?

    题目中说明了,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里,Hash Table绝对是我们优先的选择,因为Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度。

    那么,我们的算法就有了:维护一个Key为Query字串,Value为该Query出现次数的HashTable,每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。

    本方法相比算法1:在时间复杂度上提高了一个数量级,为O(N),但不仅仅是时间复杂度上的优化,该方法只需要IO数据文件一次,而算法1的IO次数较多的,因此该算法2比算法1在工程上有更好的可操作性。

    第二步:找出Top 10
    算法一:普通排序

    我想对于排序算法大家都已经不陌生了,这里不在赘述,我们要注意的是排序算法的时间复杂度是NlgN,在本题目中,三百万条记录,用1G内存是可以存下的。
    算法二:部分排序

    题目要求是求出Top 10,因此我们没有必要对所有的Query都进行排序,我们只需要维护一个10个大小的数组,初始化放入10个Query,按照每个Query的统计次数由大到小排序,然后遍历这300万条记录,每读一条记录就和数组最后一个Query对比,如果小于这个Query,那么继续遍历,否则,将数组中最后一条数据淘汰,加入当前的Query。最后当所有的数据都遍历完毕之后,那么这个数组中的10个Query便是我们要找的Top10了。

    不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。
    算法三:堆

    在算法二中,我们已经将时间复杂度由NlogN优化到NK,不得不说这是一个比较大的改进了,可是有没有更好的办法呢?

    分析一下,在算法二中,每次比较完成之后,需要的操作复杂度都是K,因为要把元素插入到一个线性表之中,而且采用的是顺序比较。这里我们注意一下,该数组是有序的,一次我们每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降到了logK,可是,随之而来的问题就是数据移动,因为移动数据次数增多了。不过,这个算法还是比算法二有了改进。

    基于以上的分析,我们想想,有没有一种既能快速查找,又能快速移动元素的数据结构呢?回答是肯定的,那就是堆。

    借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。

    思想与上述算法二一致,只是算法在算法三,我们采用了最小堆这种数据结构代替数组,把查找目标元素的时间复杂度有O(K)降到了O(logK)。

    那么这样,采用堆数据结构,算法三,最终的时间复杂度就降到了N‘logK,和算法二相比,又有了比较大的改进。
    总结:

    至此,算法就完全结束了,经过上述第一步、先用Hash表统计每个Query出现的次数,O(N);然后第二步、采用堆数据结构找出Top 10,N*O(logK)。所以,我们最终的时间复杂度是:O(N) + N’*O(logK)。(N为1000万,N’为300万)。如果各位有什么更好的算法,欢迎留言评论。第一部分,完。

    第二部分、Hash表 算法的详细解析
    什么是Hash

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

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

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

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

    根据人口普查结果,知道目前淄博市大约500万人口,你的任务是帮助人口普查办公室按年龄递增的顺序输出每个年龄有多少人,其中不满1周岁的按0岁计算,1到2周岁的按1岁计算,依次类推,大于等于100岁的老人全部按100岁计算。
    输入
    10
    16 71 17 16 18 18 19 18 19 20
    输出
    16 2
    17 1
    18 3
    19 2
    20 1
    71 1

    package com;
    
    import java.util.Scanner;
    
    public class maopao {
    
    
        public static void main(String[] args) {
    
            Scanner scanner = new Scanner(System.in);
            int num = scanner.nextInt();
            int a[] = new int[150];
            int age = 0;
            for(int i = 0;i < num;i++)
            {
                age = scanner.nextInt();
                if(age >= 100)
                    a[100]++;
                else
                ++a[age];
            }
            for(int k = 0;k < 150;k++)
            {
                if(a[k]!=0)
                {
                System.out.println(k+" "+a[k]);
                }
            }
        }
    }
    展开全文
  • T最大100,n最大5e5,O(n)的方法才能勉强卡过去,因此,快速排序也不行,需要一种更快的非交换类排序方法,hash排序。因为数最大为5e5,我们用hash表来统计每个数出现的次数,将数字当成下标,那么从最大的数遍历到...
  • perl hash 排序

    千次阅读 2011-04-26 21:51:00
    <br />对value排序,数值型 foreach my $key (sort {$hash{$b} <=> $hash{$a}} keys %hash){ push(@hash, $key); }   对value排序,字符型 <br />foreach my $key (sort {$...
  • ruby中Hash排序

    2014-11-28 16:43:00
    当values都是整形时,按照Hash的Values排序: h = {'a'=>1,'b'=>2,'c'=>5,'d'=>4} h.sort {|a,b| a[1]<=>b[1]} 输出:[["a", 1], ["b", 2], ["d", 4], ["c", 5]] 当我们需要对Hash进行排序...
  • Hash排序(JAVA)

    2018-03-12 18:03:11
    什么是hash表:哈希表(Hash table,也叫散列表),是根据key而直接进行访问的数据结构。也就是说,它通过把key映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散...
  • function hashSort(min,positive) { var result = revert(hashSortInternal(min)).concat(hashSortInternal(positive)); console.log("after sort: " + result); } function array_max( ){ var i, max = this[0]; ...
  • sort 树 hash 排序

    2013-11-17 21:55:00
    做ACM题的时候,排序是一种经常要用到的操作。如果每次都自己写个冒泡之类的O(n^2)排序,不但程序容易超时,而且浪费宝贵的比赛时间,还很有可能写错。STL里面有个sort函数,可以直接对数组排序,复杂度为n*log2(n)...
  • HDU 2523 hash排序

    2015-08-25 02:18:15
    先得数据 枚举得到 绝对值 直接hash #include #include #include using namespace std; int main() { int c=0;  scanf("%d",&c);  while(c--)  {   int n=0,k=0;   int a[2001]={0};...
  • HASH方法统计整数出现的次数 【输入形式】 以逗号分隔,#结尾的整数 【输出形式】 等式。左侧为排序好的整数,右侧为其出现的次数。 【样例输入】 2, 6, 7, 13, 18, 3, 6, 1, 3, 7# 【样例输出】 1=1 2=1 3=2 6=2...
  • Ruby:Hash 排序

    2013-04-05 13:31:00
    people = { :fred => 23, :joan => 18, :pete =>...年龄排序: people.values.sort # => [18, 23, 54] 姓名排序: people.sort_by { |name, age| age } # => [[:joan, 1...
  • 剑指offer- hash排序

    2017-03-09 20:39:26
    题目描述:我们想对公司所有员工(几万名)的年龄排序。要求时间复杂度O(n)。 分析:要排序的年龄在一个比较小的范围,假设最大的员工年龄是99。并且还可以用辅助内存。该方法用长度100的整数数组作为辅助空间换...
  • ruby中的Hash排序

    千次阅读 2013-06-24 17:16:56
    ruby API中的sort和sort_by方法可以很好的帮助我们对Hash进行排序: For example: h={'a'=>2, 'c'=>1, 'b'=>3} sort 方法: key升序: h.sort { |a, b| a[0]b[0] } [["a", 2], ["b", 3], ["c", 1]] ...
  • newLisp中的Hash排序

    2014-06-24 17:19:09
    newlisp中可以利用Hash functions 来实现某些特定数据出现次数的统计,如 (new Tree 'MyHash) (if (Myhash y) (Myhash y (+ (Myhash y) 1)) (Myhash y 1) ) 统计完成后如何根据数据出现的次数进行排序...
  • ruby array,hash排序小记

    千次阅读 2013-08-02 14:41:48
    对数组和哈希进行排序是很常见的操作,ruby提供了丰富的方法和模块支持排序,但各个拍戏效能和使用倾向却有差异。 排序方法:sort,sort_by,sort_by {|x| block} sort: sort是最常规的升序方式排序,效率高,...
  • int cmp(node a,node b) //按hash排序,同hash值按左端点坐标排序 { if (a.x!=b.x) return a.x; else return a.pos; } long long ok(long long x) { last_right_start=-1; long long i; long long hash=...
  • 什么是hash排序,什么是hash索引?使用hash算法如果只是检索数据是不是可以不需要排序就能实现?

空空如也

空空如也

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

hash排序