`
128kj
  • 浏览: 604312 次
  • 来自: ...
社区版块
存档分类
最新评论

全排列的Hash函数(JAVA)

阅读更多
我们经常使用的数的进制为“常数进制”,即始终逢p进1。例如,p进制数K可表示为
    K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n (其中0 <= ai <= p-1),
它可以表示任何一个自然数。

   对于这种常数进制表示法,以及各种进制之间的转换大家应该是很熟悉的了,但大家可能很少听说变进制数。

这里介绍一种特殊的变进制数,它能够被用来实现全排列的Hash函数,并且该Hash函数能够实现完美的防碰撞和空间利用(不会发生碰撞,且所有空间被完全使用)。这种全排列Hash函数也被称为全排列数化技术。


一、变进制数:

我们考查这样一种变进制数:第1位逢2进1,第2位逢3进1,……,第n位逢n+1进1。它的表示形式为
    K = a1*1! + a2*2! + a3*3! + ... + an*n! (其中0 <= ai <= i),
也可以扩展为如下形式(因为按定义a0始终为0),以与p进制表示相对应:
    K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! (其中0 <= ai <= i)。
(后面的变进制数均指这种变进制数,且采用前一种表示法)

例:十进数     变进制数     十进制
    0     =         0   =    0
    1     =         1   =   1*1!
    2     =        10   =   1*2!+0*1!
    3     =        11   =   1*2!+1*1!
    4     =        20   =   2*2!+0*1!
    5     =        21   =   2*2!+1*1!
    6     =       100   =   1*3!+0*2!+0*1!
    7     =       101   =   1*3!+0*2!+1*1!
    8     =       110   =   1*3!+1*2!+0*1!
    9     =       111   =   1*3!+1*2!+1*1!
   10     =       120   =   1*3!+2*2!+0*1!
   11     =       121   =   1*3!+2*2!+1*1!
   12     =       200   =   2*3!+0*2!+0*1!
  
先让我们来考查一下该变进制数的进位是否正确。假设变进制数K的第i位ai为i+1,需要进位,而ai*i!=(i+1)*i!=1*(i+1)!,
即正确的向高位进1。这说明该变进制数能够正确进位,从而是一种合法的计数方式。 


二、n位变进制数K的性质:
(1)当所有位ai均为i时,此时K有最大值
    MAX[K] = 1*1!+2*2!+3*3!+...+ n*n!
           = 1!+1*1!+2*2!+3*3!+...+n*n!-1
           = (1+1)*1!+2*2!+3*3!+...+n*n!-1
           = 2!+2*2!+3*3!+...+n*n!-1
           =(1+2)*2!+3*3!+...+n*n!-1
           = 3!+3*3!+...+n*n!-1
             ..................
           = (n+1)!-1
    因此,n位变进制数的最大值为(n+1)!-1。

(2)当所有位ai均为0时,此时K有最小值0。
因此,n位变进制数能够表示0到(n+1)!-1的范围内的所有自然数,共(n+1)!个。
如:8位变进制数能表示0到(9!-1)内的所有自然数,有9!个.


三、全排列的Hash函数:

  在一些状态空间搜索算法中,我们需要快速判断某个状态是否已经出现,此时常常使用Hash函数来实现。
其中,有一类特殊的状态空间,它们是由全排列产生的,比如N数码问题。对于n个元素的全排列,共产生n!个不同的排列或状态。
下面将讨论如何使用这里的变进制数来实现一个针对全排列的Hash函数。

   从数的角度来看,全排列和变进制数都用到了阶乘。如果我们能够用0到n!-1这n!个连续的变进制数来表示n个元素的所有排列,
那么就能够把全排列完全地数化,建立起全排列和自然数之间一一对应的关系,也就实现了一个完美的Hash函数。
那么,我们的想法能否实现呢?答案是肯定的,下面将进行讨论。

假设我们有b0,b1,b2...bn 共 n+1 个不同的元素,假设各元素之间有一种次序关系b0 < b1 < b2 ...< bn。对它们进行全排列,
共产生(n+1)!种不同的排列。对于产生的任一排列 c0,c1,c2,..,cn,其中第i个元素ci(1 <= i <= n)与
它前面的i个元素构成的逆序对的个数为di(0 <= di <= i),那么我们得到一个逆序数序列d1,d2,...,dn(0 <= di <= i)。
这不就是前面的n位变进制数的各个位么?于是,我们用n位变进制数M来表示该排列:
   M = d1*1! + d2*2! + ... + dn*n!
因此,每个排列都可以按这种方式表示成一个n位变进制数。下面,我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。

由于n位变进制数能表示(n+1)!个不同的数,而n+1个元素的全排列刚好有(n+1)!个不同的排列,
且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的排列产生两个不同的变进制数,那么我们就可以得出结论:

定理:
   n+1个元素的全排列的每一个排列对应着一个不同的n位变进制数。

证明:
   对于全排列的任意两个不同的排列p0,p1,p2,...,pn(排列P)和q0,q1,q2,...,qn(排列Q),
从后往前查找第一个不相同的元素,分别记为pi和qi(0 < i <= n)。
(1)如果qi > pi,那么,
     如果在排列Q中qi之前的元素x与qi构成逆序对,即有x > qi,则在排列P中pi之前也有相同元素x > pi(因为x > qi且qi > pi),
即在排列P中pi之前的元素x也与pi构成逆序对,所以pi的逆序数大于等于qi的逆序数。又qi与pi在排列P中构成pi的逆序对,
所以pi的逆序数大于qi的逆序数。
(2)同理,如果pi > qi,那么qi的逆序数大于pi的逆序数。
因此,由(1)和(2)知,排列P和排列Q对应的变进制数至少有第i位不相同,即全排列的任意两个不同的排列具有不同的变进制数。
至此,定理得证。


四、计算k个元素的一个全排列对应的变进制数的算法(hash函数)
public class Test{
  //1!=1;2!=2;3!=6;4!=24;5!=120;6!=720...
  static int fac[] = {1,2,6,24,120,720,5040,40320};

  static int hash(int num,int k){num是K个元素的一个全排列
    int  n[]=new int[k];
    for(int i = k-1; i >=0; i--){
        n[i] = num % 10;
        num /= 10;
    }
   
    int key = 0;
    int c;
    for(int i = 1; i <k; i++){
         c=0;
     for(int j = 0; j < i; j++)
         if(n[j] > n[i]) c++;
     key += c * fac[i-1];
    }
    return key;
}

static int hash(String s,int k){// s是k个不同元素(数字)的一个全排列。
    int  n[]=new int[k];
    for(int i = k-1; i >=0; i--){
        int num=s.charAt(i)-48;
        n[i] = num % 10;
        num /= 10;
    }
   
    int key = 0;
    int c;
    for(int i = 1; i <k; i++){
         c=0;
     for(int j = 0; j < i; j++)
         if(n[j] > n[i]) c++;
     key += c * fac[i-1];
    }
    return key;
}
  
  public static void main(String[] args){
    int a[]={123,132,213,231,312,321};
    for(int i=0;i<a.length;i++)
      System.out.println(hash(a[i],3));

      System.out.println(hash("012345678",9));
       System.out.println(hash("876543210",9));
         System.out.println(hash(876543210,9));
 }
    
   }



运行:
D:\java>java   Test
0
2
1
4
3
5
0
362879
362879
分享到:
评论

相关推荐

    各种Hash函数(JAVA版)

    RS-Hash Function Value: " + ghl.RSHash(key)); System.out.println(" 2. JS-Hash Function Value: " + ghl.JSHash(key)); System.out.println(" 3. PJW-Hash Function Value: " + ghl.PJWHash(key)); System....

    密码学hash函数关于hash函数的ppt

    - **消息认证码(MAC)**是使用带密钥的Hash函数实现的,它结合了Hash函数的安全特性和密钥的安全性,以确保只有合法接收方才能验证消息的完整性。 2. **数字签名** - 在数字签名过程中,首先使用密码学Hash函数...

    信息安全原理与技术-第五章Hash函数和数字签名.ppt

    Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名

    Hash函数研究综述

    ### Hash函数研究综述 #### 引言 Hash函数作为一种重要的密码学组件,在现代信息安全领域扮演着关键角色。它可以用于数字签名方案、验证信息来源的真实性和完整性等方面,并且能够将任意长度的消息压缩到固定长度...

    Hash函数与消息认证

    hash函数与消息认证讲义 包括 5.1 Hash函数概述 5.1.1 Hash函数定义 5.1.2 Hash函数的安全性 5.1.3 Hash函数的迭代构造法 5.2 Hash函数MD5 5.2.1 MD5算法 5.2.2 MD5的安全性 5.3 安全Hash算法SHA-1 5.3.1 SHA-1...

    常用的hash算法(java实现)

    在计算机科学中,哈希(Hash)算法是一种用于将任意长度的数据映射为固定长度输出的函数。这种输出通常称为哈希值或消息摘要。在Java编程语言中,实现哈希算法可以方便地用于数据验证、查找表以及密码存储等多种用途...

    混沌加密算法与HASH函数构造研究_12767438.zip

    HASH函数是一种单向函数,它将任意长度的数据转化为固定长度的输出,这个输出称为哈希值。在密码学中,HASH函数通常用于数据完整性检查和密码存储。它们的特性包括:单向性(容易计算哈希,但难以反向推导输入数据)...

    密码学基础课件:第四章 Hash函数3.pdf

    "Hash函数基础知识" Hash 函数是密码学中一种基本的加密技术,它可以将任意长度的输入数据转换为固定长度的输出数据。Hash 函数的输出结果通常是固定的位数,我们称之为 Hash 值。Hash 函数的应用非常广泛,例如...

    第八讲 HASH函数1

    HASH函数 HASH 函数是密码学中的一种基本概念,用于将任意长的数据变换为定长的码。HASH 函数的定义是将输入消息 M 变换为固定大小的 Hash 码 h,记为 h = H(M) 或 h = HH(M)。HASH 函数的输出 h 称为消息摘要、...

    Java实现GeoHash算法

    Java实现GeoHash算法是一种在IT领域中用于地理位置数据存储和检索的技术。GeoHash将经纬度坐标转换为字符串,使得地理位置可以被高效地索引和查询。这种算法利用了空间分割和编码策略,使得相邻的位置在编码后具有...

    HASH函数实验指导

    在信息技术领域,哈希(Hash)函数与数字签名是两个至关重要的概念,它们在数据完整性、安全认证和密码学中发挥着基础性作用。本实验指导将深入探讨这两个概念,以及它们如何应用于验证码的实现过程。 **哈希函数**...

    Hash函数的设计优化

    Hash 函数的设计优化 Hash 函数是一种常用的数据结构,旨在提高程序的时间效率和空间效率。在信息学竞赛中,Hash 函数的设计优化尤为重要。本文对面向各种不同标本的 Hash 函数进行讨论,并对多种常用的 Hash 函数...

    hash函数 实例

    根据给定的文件信息,我们可以总结出以下关于 Hash 函数在 C 语言中的实现与应用的知识点: ### 1. Hash 函数的概念 哈希函数(Hash Function)是一种将任意长度的消息映射到固定长度的消息摘要的一种算法。这种...

    hash函数的完全解析

    Hash函数是一种将任意长度的输入通过散列算法转换成固定长度输出的函数,这种输出又被称为散列值或者哈希值。一个设计良好的Hash函数能够快速处理输入数据并尽量减少不同输入得到相同输出的情况,即碰撞。在信息存储...

    hash函数的设计优化

    在李羽修的《Hash函数的设计优化》文档中,可能详细讨论了这些优化策略,并提供了实际案例和分析,帮助读者理解如何在实践中优化哈希函数,以满足特定需求和挑战。对于IT专业人士来说,理解和掌握哈希函数的设计优化...

    HASH函数及其应用_朱全民.ppt

    在"HASH函数及其应用_朱全民.ppt"中,主要讨论了哈希函数的构造方法、冲突处理以及实际应用。 一、哈希函数构造方法 1. 直接取余法:这是最简单的哈希函数构造方式,通过将关键字k除以表长m取余数来确定哈希值。...

Global site tag (gtag.js) - Google Analytics