精华内容
下载资源
问答
  • 散列函数

    2018-04-28 22:19:34
     散列函数:一个把查找表中的关键字映射成该关键字对应的地址函数,记为Hash(key)=Addr。这里的地址可以是数组下标,索引,或内存地址等。散列函数可能将两个或两个以上的不同关键字映射到同一个地址,称这种情况为...

        在线性表和树表中的查询中,记录在表的位置跟记录的关键字之间不存在确定关系,也就是说在线性表和树表中查询通常要依托关键字比较,查找的效率取决于比较次数。

        散列函数:一个把查找表中的关键字映射成该关键字对应的地址函数,记为Hash(key)=Addr。这里的地址可以是数组下标,索引,或内存地址等。散列函数可能将两个或两个以上的不同关键字映射到同一个地址,称这种情况为“冲突”。(假若这个函数是f(x)=x^2,-无穷<x<+无穷,则当x=+-1时,函数值相同,这种情况就成为冲突)这种冲突最好减少,但是这种冲突是避免不了的,所以要设计好解决冲突的方法。

        散列表:根据关键字而直接进行访问的数据结构,散列表建立了关键字和存储地址之间的直接映射关系。理想情况下,散列表的查找时间复杂度为O(1),及与表中的元素个数无关。


    散列函数的构造方法:

    [注意]

    • 散列函数定义域必须包含全部需要存储的关键字,而值域的范围则依赖散列表的大小或地址范围。
    • 散列函数计算出来的地址应该能等概率、均匀分布在整个地址空间,从而减少冲突的发生。
    • 散列函数应尽简单,能够在较短时间内就计算出任一个关键字对应的散列地址。

    常用的散列函数:

    1. 直接定址法:直接取关键字的某个线性函数值为散列地址,散列函数为:H(key)=a*key+b,其中a,b是常数。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。这种方式最简单,并且不会冲突,适用于关键字的分布基本连续的情况,若关键字分布不连续,空位比较多,将造成空间浪费。
    2. 除留余数法:假定散列表表长为m,取一个不大于m但最接近或等于m的质数p,利用以下公式把关键字转换成散列地址,散列函数为H(key)=key%p。[注]关键是选好p,使得每一个关键字通过该函数转换后等概率地映射到散列空间上的任意地址,从而尽可能减少冲突的可能性。
    3. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。
    4. 平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。

            例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址。


            5.随机数法:选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。

            6.折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    冲突解决方法:

    1. 开放寻址法:指的是客村放心表象的空闲地址既向它的同义词表项开放,又向它的非同义表项开放。数学递归公式为:Hi=(H(key) + di)     MOD m , i=0,1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列四种取法:

    • di=0,,1,2,3,…,m-1,称线性探测(特点:冲突发生时,顺序查看表中下一个单元,直到找出一个空闲单元或查遍全表);
    • di=0^2,1^2,-1^2,2^2,-2^2,⑶^2,…,±(k)^2,(k<=m/2)称二次探测(平方探测法)(特点:散列表长度m必须是一个可以表示成4k+3的素数,此方法可避免“堆积问题”,不能探测到散列表的所有单元,但是至少能探测一般);
    • di=伪随机数序列,称伪随机序列散列。
    • 再散列法:当di=Hash2(key),又称为双散列表。需要使用两个散列函数,当通过第一个散列函数H(key)得到的地址发生冲突,则利用第二散列函数Hash2(key)计算该关键字的地址增量。它的具体函数形式为:Hi=(H(key)+i*Hash2(key))%m,i=0,1,2,…,k ,i是冲突次数。即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。

    2. 链接法(拉链法)

    为了避免不同关键字映射到同一地址,可以把所有的同义词存储在一个线性表中,这个线性链表尤其散列地址唯一标识。散列地址为i的同义词链表的头指针存放在散列表的第i个单元中,因而查找、插入和删除操作,主要在同义词链中进行。拉链法适用于进行插入和删除的情况。

    例如,关键字序列为{19,14,23,01,68,20,84,27,55,11,10,79},散列函数为H(key)=key%13,用拉链法处理冲突。如图:

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    1
    01
    14
    27
    79
    3
    55
    68
    6
    19
    84
    7
    20
    10
    10
    23
    11
    11

    实例

    1.两数之和

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

    你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    示例:

    给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
    

     不用Hash的c++算法:

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
             vector<int> res;
            int n = nums.size();
            for(int i = 0;i<n;++i)
            {
                for(int j = i+1;j<n;++j)
                {
                    if(nums[i]+nums[j]==target)
                    {
                        res.push_back(i);
                        res.push_back(j);
                        break;
                    }
                }
                if(!res.empty())
                    break;
            }
            return res;
        }
    };

    用HashMap的Java算法:

    class Solution {
        public int[] twoSum(int[] a, int target) {
            int[] res = new int[2];
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < a.length; i++) {
                if(map.containsKey(a[i])){
                    res[0] = map.get(a[i]);
                    res[1] = i;
                }
                map.put(target - a[i], i);
            }
            return res;
        }
    }

    15. 三数之和

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

    注意:答案中不可以包含重复的三元组。

    例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
    
    满足要求的三元组集合为:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]
    
    class Solution {
       public List<List<Integer>> threeSum(int[] nums) {
            if(nums == null){
                return null;
            }
            if(nums.length < 3){
                return new ArrayList<>();
            }
            
            Arrays.sort(nums);
            HashSet<List<Integer>> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                int j = i + 1;
                int k = nums.length - 1;
                while(j < k){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        set.add(list);
                        while(j < k && nums[j] == nums[j + 1]){
                            j++;
                        }
                        while(j < k && nums[k] == nums[k - 1]){
                            k--;
                        }
                        j++;
                        k--;
                    }else if(nums[i] + nums[j] + nums[k] < 0){
                        j++;
                    }else{
                        k--;
                    }
                }
            }
            return new ArrayList<>(set);
        }
    }


    展开全文
  • 散列函数和文件比较

    2020-03-01 12:06:49
    散列函数和文件比较 目录 一、散列函数 2 1.散列函数(Hash function)=散列算法、哈希函数 2 2.散列碰撞(collision) 2 二、MD5 2 1.MD5是什么?128位散列值[16字节]一般使用32位16进制表示 2 2. 在...

    散列函数 和 文件比较

    目录

    一、散列函数 

    1.散列函数(Hash function)=散列算法、哈希函数 

    2.散列碰撞(collision) 

    二、MD5 

    1.MD5是什么?128位散列值[16字节]一般使用32位16进制表示

    2. 在Windows的DOS命令方式下计算机MD5 

    三、SHA系列 

    1.什么是SHA系列?SHA0、SHA1、SHA2、SHA3 

    2.在Windows的DOS命令下计算SHA 

    四、散列函数对比表 


    一、散列函数

    1.散列函数(Hash function)=散列算法、哈希函数

    散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。

    2.散列碰撞(collision)

    所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。但另一方面,散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,这种情况称为“散列碰撞(collision)”,这通常是两个不同长度的输入值,刻意计算出相同的输出值。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

    典型的散列函数都有非常大的定义域,比如SHA-2最高接受(264-1)/8长度的字节字符串。同时散列函数一定有着有限的值域,比如固定长度的比特串。在某些情况下,散列函数可以设计成具有相同大小的定义域和值域间的单射。在密码学中,散列函数必须具有不可逆性。

     

    二、MD5

    1.MD5是什么?128位散列值[16字节]一般使用32位16进制表示

    MD5信息摘要算法(英语:MD5 Message-Digest Algorithm)

    来源:https://baike.baidu.com/item/MD5 此网址有C、Java等程序的实现源代码

    一种被广泛使用的密码散列函数,可以产生出一个128位的散列值(hash value)(16字节,MD5值通常的呈现为32十六进制数),eg:581b65637825ed2778b93dd05a03be14。它确保信息传输完整一致,是由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)1992年公开,取代MD4算法。1996年该算法被证实存在弱点,可以被加以破解,对于需要高度安全性的数据,专家一般建议改用其他算法,如SHA-2。2004年,证实MD5算法无法防止碰撞(collision在对两个不同的内容使用 MD5算法运算的时候,有可能得到一对相同的结果值),因此不适用于安全性认证,如SSL公开密钥认证或是数字签名等用途。MD5算法因其普遍、稳定、快速的特点,仍广泛应用于普通数据的加密保护领域

     

    用于密码管理当我们需要保存某些密码信息以用于身份确认时,如果直接将密码信息以明码方式保存在数据库中,不使用任何保密措施,系统管理员就很容易能得到原来的密码信息,这些信息一旦泄露, 密码也很容易被破译。为了增加安全性,有必要对数据库中需要保密的信息进行加密,这样,即使有人得到了整个数据库,如果没有解密算法,也不能得到原来的密码信息。

    MD5算法可解决这个问题,它可将任意长度的输入串经过计算得到固定长度的输出,而且只有在明文相同的情况下,才能等到相同的密文,并且这个算法是不可逆的,即便得到了加密以后的密文,也不可能通过解密算法反算出明文。

    这样就可以把用户的密码以MD5值(或类似的其它算法)的方式保存起来,用户注册的时候,系统是把用户输入的密码计算 MD5 值,然后再去和系统中保存的 MD5 值进行比较,如果密文相同,就可密码是正确的,否则密码错误。通过这步骤,系统在并不知道用户密码明码的情况下就可以确定用户登录系统的合法性。这样不但可以避免用户的密码被具有系统管理员权限的用户知道,而且还在一定程度上增加了密码被破解的难度

     

    电子签名使用 MD5算法就可为任何文件(不管其大小、格式、数量)产生一个独一无二的“数字指纹”,借助这个“数字指纹”,通过检查文件前后 MD5 值是否发生了改变,就可以知道源文件是否被改动。

    有时,在下载软件的时会发现,软件的下载页面上除了会提供软件的下载地址以外,还会给出一串长长的字符串。这串字符串其实就是该软件的MD5 值,它的作用就在于下载该软件后,对下载得到的文件用专门的软件(如 Windows MD5 check 等)做一次 MD5 校验,以确保我们获得的文件与该站点提供的文件为同一文件。利用 MD5 算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。

     

    网盘文件的管理:在使用网盘时,我们发现一些超大文件。这其实利用MD5比如百度云盘服务器只认MD5码,不认文件名。你上传的文件大小和上传速度无关,只要你上传的文件MD5码和云盘服务器里的某个文件相同,就会默认为服务器里存储的那个文件,所需的上传时间不过是校检MD5码的过程,当然能实现秒传。如果你自己随便拍个小视频再去上传一下试试,速度慢到让你想砸电脑。


    垃圾邮件筛选电子邮件使用越来越普遍的情况下,可以利用 MD5 算法在邮件接收服务器上进行垃圾邮件的筛选,以减少此类邮件的干扰,具体思路如下:

    1.建立一个邮件 MD5 值资料库,分别储存邮件的 MD5 值、允许出现的次数(假定为 3)和出现次数(初值为零)。

    2.对每一封收到的邮件,将它的正文部分进行MD5 计算,得到 MD5 值,将这个值在资料库中进行搜索。

    3.如未发现相同的 MD5 值,说明此邮件是第一次收到,将此 MD5 值存入资料库,并将出现次数置为1,转到第五步。

    4.如发现相同的 MD5 值,说明收到过同样内容的邮件,将出现次数加 1,并与允许出现次数相比较,如小于允许出现次数,就转到第五步。否则中止接收该邮件。结束。

    5.发送邮件。

     

    1. 在Windows的DOS命令方式下计算机MD5

    假如Linux,md5sum是默认的用来计算和校验文件报文摘要的程序。

    我们复制两个完成一样的文件,做如下的实验:

    C:\Users\DeepBlue>certutil -hashfile .\1.txt MD5

    MD5 的 .\1.txt 哈希:

    581b65637825ed2778b93dd05a03be14

    CertUtil: -hashfile 命令成功完成。

     

    C:\Users\DeepBlue>certutil -hashfile .\2.txt MD5

    MD5 的 .\2.txt 哈希:

    581b65637825ed2778b93dd05a03be14

    CertUtil: -hashfile 命令成功完成。

    假如我们修改一个文件中的一个字符,就会看到计算出的md5值是不一样的。


    三、SHA系列

    1.什么是SHA系列?SHA0、SHA1、SHA2、SHA3

    SHA0、SHA1、SHA2、SHA3美国国家安全局(National Security Agency,NSA)设计。

    SHA-1可以生成一个被称为消息摘要的160(20字节)散列值,散列值通常的呈现形式为40个十六进制1995年发布,SHA-1在许多安全协议中广为使用,包括TLSSSLPGPSSHS/MIMEIPsec,曾被视为是MD5(更早之前被广为使用的散列函数)的后继者。但SHA-1的安全性在2000年以后已经不被大多数的加密场景所接受。

    SHA-1已经不再视为可抵御有充足资金、充足计算资源的攻击者。2005年,密码分析人员发现了对SHA-1的有效攻击方法,这表明该算法可能不够安全2017年荷兰密码学研究小组CWI 与Google宣布了一个成功的SHA-1碰撞攻击,发布了两份内容不同但SHA-1散列值相同的PDF文件作为证明这代表SHA-1算法已被正式攻破。MicrosoftGoogle以及Mozilla旗下的浏览器在2017年停止接受使用SHA-1算法签名的SSL证书

    SHA-2:2001年发布,包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。虽然至今尚未出现对SHA-2有效的攻击【2020年】SHA2的算法跟SHA-1基本上仍然相似;因此有些人开始发展其他替代的散列算法。

    SHA-3:2015年正式发布,SHA-3并不是要取代SHA-2,因为SHA-2当前并没有出现明显的弱点。由于对MD5出现成功的破解,以及对SHA-0和SHA-1出现理论上破解的方法,NIST感觉需要一个与之前算法不同的,可替换的加密散列算法,也就是现在的SHA-3。

     

    2.在Windows的DOS命令下计算SHA

    C:\Users\DeepBlue>certutil -hashfile .\1.txt SHA1SHA1为默认值,可以省略

    SHA1 的 .\1.txt 哈希:

    2af8c4d88ca28b30dcd952910cee2360c2c04fa4

    CertUtil: -hashfile 命令成功完成。

    C:\Users\DeepBlue>certutil -hashfile .\2.txt SHA1

    SHA1 的 .\2.txt 哈希:

    2af8c4d88ca28b30dcd952910cee2360c2c04fa4

    CertUtil: -hashfile 命令成功完成。

     

    C:\Users\DeepBlue>certutil -hashfile .\1.txt SHA256

    SHA256 的 .\1.txt 哈希:

    5b319761f561582e4021b03b7fc6582fbdcb088620b0ba090325e6c69759cb72

    CertUtil: -hashfile 命令成功完成。

    C:\Users\DeepBlue>certutil -hashfile .\2.txt SHA256

    SHA256 的 .\2.txt 哈希:

    5b319761f561582e4021b03b7fc6582fbdcb088620b0ba090325e6c69759cb72

    CertUtil: -hashfile 命令成功完成。

     

    C:\Users\DeepBlue>certutil -hashfile .\1.txt SHA512

    SHA512 的 .\1.txt 哈希:

    52c2f32aca5a97065134d907b01acc173c5383d45696fac020d60a2707917e7d32da946684553196c3b6b25556ae42be344dd351128e2dbcfd5a3ba3e20bc130

    CertUtil: -hashfile 命令成功完成。

    C:\Users\DeepBlue>certutil -hashfile .\2.txt SHA512

    SHA512 的 .\2.txt 哈希:

    52c2f32aca5a97065134d907b01acc173c5383d45696fac020d60a2707917e7d32da946684553196c3b6b25556ae42be344dd351128e2dbcfd5a3ba3e20bc130

    CertUtil: -hashfile 命令成功完成。

     


    四、散列函数对比表

    算法和变体

    输出散列值长度

    中继散列值长度

    数据区块长度

    最大输入消息长度

    循环次数

    碰撞攻击

    性能示例[3]

    bits

    bits

    bits

    bits

    bits

    (MiB/s)

    MD5(作为参考)

    128

    128

    512

    无限[4]

    64

    ≤18

    335

    (4 × 32)

    发现碰撞

    SHA-0

    160

    160

    512

    264 − 1

    80

    <34

    -

    (5 × 32)

    发现碰撞

    SHA-1

    160

    160

    512

    264 − 1

    80

    <63[5]

    192

    (5 × 32)

    发现碰撞

    SHA-2

    SHA-224

    224

    256

    512

    264 − 1

    64

    112

    139

    SHA-256

    256

    (8 × 32)

    128

    SHA-384

    384

    512

    1024

    2128 − 1

    80

    192

    154

    SHA-512

    512

    (8 × 64)

    256

    SHA-512/224

    224

     

    112

    SHA-512/256

    256

     

    128

    SHA-3

    SHA3-224

    224

    1600

    1152

    无限[7]

    24[8]

    112

    -

    SHA3-256

    256

    (5 × 5 × 64)

    1088

    128

    SHA3-384

    384

     

    832

    192

    SHA3-512

    512

     

    576

    256

    SHAKE128

    d (arbitrary)

     

    1344

    min(d/2, 128)

    -

    SHAKE256

    d (arbitrary)

     

    1088

    min(d/2, 256)

     

    此表来源于维基百科,

    免翻网址:https://wikipediam.hk.wjbk.site/wiki/SHA%E5%AE%B6%E6%97%8F

    展开全文
  • 漫谈散列函数

    千次阅读 2020-07-30 16:59:32
    定义引一段百度百科关于散列函数定义。Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,...
    简介:说到散列,一般对应于散列表(哈希表)和散列函数。 我们今天不谈哈希表,仅谈下散列函数。

    说到散列,一般对应于散列表(哈希表)和散列函数。
    我们今天不谈哈希表,仅谈下散列函数。

    定义

    引一段百度百科关于散列函数的定义。

    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。
    这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。

    简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

    关于散列函数的定义有很多表述,大同小异,理解其概念和内涵即可。

    性质

    查看维基百科百度百科,两者关于散列的性质都提到了几点:

    1、确定性

    如果两个散列值是不相同的,那么这两个散列值的原始输入也是不相同的;

    2、冲突(碰撞)

    散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同;

    3、不可逆性

    最后一个是关于是否可逆的,两者表述有所出入:
    维基百科-散列函数

    百度百科-散列函数

    维基百科中,很明确地提出“散列函数必须具有不可逆性”,而百度百科的表述则模棱两可,相比之下,后者显得太不严谨了。
    笔者比较倾向于维基百科提到的不可逆性。

    4、混淆性

    在“散列函数的性质”一节,维基百科还提到一点:

    输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

    该表述中有两个词:“强混淆”, “完全不同”。就是什么含义呢?

    先来了解一个概念:雪崩效应
    其精髓在于“严格雪崩准则”:当任何一个输入位被反转时,输出中的每一位均有50%的概率发生变化。

    再了解一个概念:Hamming distance
    有的译作“海明距离”,有的则是“汉明距离”。名字不重要,重要的内涵。

    两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。举例如下:10101和00110从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。

    对应于散列,如果“部分改变输入值”, 前后两个两个散列的海明距离为散列长度的一半(也就是有一半的bit不相同),则为“50%的概率发生变化”。
    这样的散列函数,就是“具有强混淆特性的散列函数”。

    散列函数举例

    常见的散列函数有MD5SHA家族等加密散列函数,CRC也该也算是散列。
    两者都有用于数据校验,而前者还用于数字签名,访问认证等安全领域。
    不过我们今天不对加密散列做太多展开,主要讲讲下面两个散列:

    BKDRHash

    这个散列函数大家应该见过,可能有的读者不知道它的名字而已。
    JDK中String的hashCode()就是这个散列函数实现的:

        public int hashCode() {
            int h = hash;
            final int len = length();
            if (h == 0 && len > 0) {
                for (int i = 0; i < len; i++) {
                    h = 31 * h + charAt(i);
                }
                hash = h;
            }
            return h;
        }

    定义一个类,如果让IDE自动生成hashCode()函数的话,其实现也是类似的:

        public static class Foo{
            int a;
            double b;
            String c;
            
            @Override
            public int hashCode() {
                int result;
                long temp;
                result = a;
                temp = Double.doubleToLongBits(b);
                result = 31 * result + (int) (temp ^ (temp >>> 32));
                result = 31 * result + (c != null ? c.hashCode() : 0);
                return result;
            }
        }

    为什么总是跟“31”过不去呢?为什么要这样迭代地求积和求和呢?
    这篇文章讲到了其中一些原理:哈希表之bkdrhash算法解析及扩展
    而知乎上也有很多大神做了分析:hash算法的数学原理是什么,如何保证尽可能少的碰撞
    从第二个链接给出的评分对比可以看出,BKDRHash虽然实现简单,但是很有效(冲突率低)。

    低冲突,使得BKDRHash不仅仅用于哈希表,还用于索引对象。
    这样的用法,最常见的还是MD5,有的网站可能会用文件的MD5作为检索文件的key,
    DiskLruCache也是用MD5作为key, 不过通常不是对文件本身计算MD5,而是对url做MD5(例如OkHttp, Glide)。
    MD5生成的消息摘要有128bit, 如果要标识的对象不多,冲突率会很低;
    当冲突率远远低于硬件损坏的概率,那么可以认为用MD5作为key是可靠的。
    对于网站,如果要存储海量文件,不建议用MD5作为key。
    顺便提一下,UUID其实也是128bit的精度,只是其为了方便阅读多加了几个分割线而已。

    扯远了, 回归正题~
    之所以看到BKDRHash用来索引对象,主要是看到这篇文章(笔者没有研究过Volley源码):
    Android Volley 源码解析(二),探究缓存机制
    里面提到Volley缓存的key的设计:

    private String getFilenameForKey(String key) {
           int firstHalfLength = key.length() / 2;
           String localFilename = String.valueOf(key.substring(0, firstHalfLength).hashCode());
           localFilename += String.valueOf(key.substring(firstHalfLength).hashCode());
           return localFilename;
    }

    由于JDK的hashCode()返回值是int型,这个函数可以说是64bit精度的。
    不能说它是散列函数,因为其返回值长度并不固定,按照定义,不能称之为散列函数,虽然思想很接近。
    其等价写法如下:

        public static String getFilenameForKey(String key) {
            byte[] bytes = key.getBytes();
            int h1 = 0, h2 = 0;
            int len = bytes.length;
            int firstHalfLength = len / 2;
            for (int i = 0; i < firstHalfLength; i++) {
                byte ch = bytes[i];
                h1 = 31 * h1 + ch;
            }
            for (int i = firstHalfLength; i < len; i++) {
                byte ch = bytes[i];
                h2 = 31 * h2 + ch;
            }
            long hash = (((long) h1 << 32) & 0xFFFFFFFF00000000L) | ((long) h2 & 0xFFFFFFFFL);
            return Long.toHexString(hash);
        }

    效果大约等价于64bit精度的BKDRHash。
    64bit的BKDRHash如下:

        public static long BKDRHash(byte[] bytes) {
            long seed = 1313; // 31 131 1313 13131 131313 etc..
            long hash = 0;
            int len = bytes.length;
            for (int i = 0; i < len; i++) {
                hash = (hash * seed) + bytes[i];
            }
            return hash;
        }

    笔者编了程序比较其二者的冲突率,前者比后者要高一些(篇幅限制,不贴测试代码了,有兴趣的读者可自行测试)。

    32bit的散列,无论哪一种,只要数据集(随机数据)上10^6, 基本上每次跑都会有冲突。
    64bit的散列,只要性能不是太差,如果数据的长度是比较长的(比方说20个字节的随机数组),即使千万级别的数据集也很难出现冲突(笔者没有试过上亿的,机器撑不住)。

    笔者曾经也是BKDRHash的拥趸,并在项目中使用了一段时间(作为缓存的key)。
    直到看到上面那篇知乎的讨论,的一个回答:

    看了知乎心里一惊,回头修改了下测试用例,构造随机数据时用不定长的数据,比方说1-30个随机字节,
    测试于上面写的64bitBKDRHash, 其结果是:
    数据集上5万就可以看到冲突了。

    之前是知道BKDRHash的混淆性不足的(比方说最后一个字节的值加1,hash值也只是加1而已,如果未溢出的话);
    但是由于其实现简单,以及前面那个不合理的测试结果,就用来做缓存的key了,毕竟Volley也这么干了。
    实际上也没有太大的问题,因为用的地方输入通常比较长,而且要缓存的文件也不是很多(几百上千的级别),所以应该不会有冲突。
    但是心里面还是不踏实,最终还是很快换了另一个散列函数。

    MurmurHash

    初次看到这个散列函数,也是被它的名字雷到了。
    不过也有觉得这个名字很“萌”的:

    不过有道是“人不可貌相”,算法也不可以名字来评判,还是要看其效果。
    如截图所示,很多大名鼎鼎的开源组件都用到这个散列,那其究竟是何方神圣呢?让我们来一探究竟。
    先看源码:https://sites.google.com/site/murmurhash/
    源码是用C++写的:

    uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed )
    {
        const uint64_t m = 0xc6a4a7935bd1e995;
        const int r = 47;
    
        uint64_t h = seed ^ (len * m);
    
        const uint64_t * data = (const uint64_t *)key;
        const uint64_t * end = data + (len/8);
    
        while(data != end)
        {
            uint64_t k = *data++;
    
            k *= m; 
            k ^= k >> r; 
            k *= m; 
            
            h ^= k;
            h *= m; 
        }
    
        const unsigned char * data2 = (const unsigned char*)data;
    
        switch(len & 7)
        {
        case 7: h ^= uint64_t(data2[6]) << 48;
        case 6: h ^= uint64_t(data2[5]) << 40;
        case 5: h ^= uint64_t(data2[4]) << 32;
        case 4: h ^= uint64_t(data2[3]) << 24;
        case 3: h ^= uint64_t(data2[2]) << 16;
        case 2: h ^= uint64_t(data2[1]) << 8;
        case 1: h ^= uint64_t(data2[0]);
                h *= m;
        };
     
        h ^= h >> r;
        h *= m;
        h ^= h >> r;
    
        return h;
    } 

    总的来说也不是很复杂,BKDHHash相比,都是一遍循环的事。
    而且C++可以将int64的指针指向char数组,可以一次算8个字节,对于长度较长的数组,运算更快。
    而对于java来说,就相对麻烦一些了:

    public static long hash64(final byte[] data) {
            if (data == null || data.length == 0) {
                return 0L;
            }
            final int len = data.length;
            final long m = 0xc6a4a7935bd1e995L;
            final long seed = 0xe17a1465;
            final int r = 47;
    
            long h = seed ^ (len * m);
            int remain = len & 7;
            int size = len - remain;
    
            for (int i = 0; i < size; i += 8) {
                long k = ((long) data[i+7] << 56) +
                        ((long) (data[i + 6] & 0xFF) << 48) +
                        ((long) (data[i + 5] & 0xFF) << 40) +
                        ((long) (data[i + 4] & 0xFF) << 32) +
                        ((long) (data[i + 3] & 0xFF) << 24) +
                        ((data[i + 2] & 0xFF) << 16) +
                        ((data[i + 1] & 0xFF) << 8) +
                        ((data[i] & 0xFF));
                k *= m;
                k ^= k >>> r;
                k *= m;
                h ^= k;
                h *= m;
            }
    
            switch (remain) {
                case 7: h ^= (long)(data[size + 6] & 0xFF) << 48;
                case 6: h ^= (long)(data[size + 5] & 0xFF) << 40;
                case 5: h ^= (long)(data[size + 4] & 0xFF) << 32;
                case 4: h ^= (long)(data[size + 3] & 0xFF) << 24;
                case 3: h ^= (data[size + 2] & 0xFF) << 16;
                case 2: h ^= (data[size + 1] & 0xFF) << 8;
                case 1: h ^= (data[size] & 0xFF);
                    h *= m;
            }
    
            h ^= h >>> r;
            h *= m;
            h ^= h >>> r;
    
            return h;
        }

    以上实现参考:
    https://github.com/tnm/murmurhash-java
    https://github.com/tamtam180/MurmurHash-For-Java/

    做了一下测试,随机数组,个数10^7,长度1-30, 结果如下:

    散列函数冲突个数运算时间(毫秒)
    BKDRHash16731121
    CRC6416731331
    MurmurHash01119

    该测试把另一个64bit的hash, CRC64掺和进来了。
    很神奇的是,CRC64和BKDRHash的冲突率是一样的(测了很多次,都是一样),可能是都存在溢出问题的原因。
    至于运算时间,差别不大。
    如果把随机数组的长度调整为1-50,则前者(BKDRHash & CRC64)的冲突率会相对降低,而后者的运算效率会稍胜于前者。

    我想MurmurHash之所以应用广泛,应该不仅仅是因为其冲突率低,还有一个很重要的特性:
    前面提到的“强混淆性”。
    编写一个计算码距的函数如下:

       private static int getHammingDistance(long a, long b) {
           int count = 0;
           long mask = 1L;
           while (mask != 0) {
               if ((a & mask) != (b & mask)) {
                   count += 1;
               }
               mask <<= 1;
           }
           return count;
       }

    构造随机数组,每次改变其中一个bit,计算MurmurHash,码距在31-32之间。
    对于64bit的散列,正好在50%左右,说明该散列函数具备雪崩效应。
    或者从另一个角度看,MurmurHash算出的散列值比较“均匀”,这个特点很重要。
    比如如果用于哈希表,布隆过滤器等, 元素就会均匀分布。

    生日悖论

    最后了解一下冲突概率的估算: 生日悖论
    生日悖论讲的是给定一群人,其中有至少有两个人生日相同的概率。
    以一年365天算,23人(及以上),有两人生日相同的概率大约50%;而如果到了60人以上,则概率已经大于99%了。
    同样的,给定一组随机数,也可以算出有相同数值(冲突)的概率。
    根据维基百科生日攻击中的描述,其冲突分布如下表:

    如果随机数是32位,那么可能性有约43亿种,但是只要数量达到50000个,其冲突概率就有25%。
    我们常看到MD5作为文件索引,SHA,MD5用于文件校验,就是因为其冲突概率很低,想要篡改文件还保持Hash不变,极其困难。
    不过困难不意味着不可能,例如,Google建议不要使用SHA-1加密了,
    参见:为什么Google急着杀死加密算法SHA-1

    扯远了,回到前面说的缓存key,64bit的MurmurHash, 当缓存数量在10^4这个级别时,
    有两个缓存的key冲突的概率是10^-12(万亿份之一)的量级,应该是比较可靠的。
    如果觉得还不够,可以用128bit的MurmurHash,仅做索引的话,应该比MD5要更合适(运算快,低碰撞,高混淆)

    结语

    散列广泛应用于计算机的各个领域,了解散列函数的一些性质,对于解决工程问题或有帮助,
    故而有了这篇“漫谈”,希望对读者有所启发。

    原文链接:https://developer.aliyun.com/article/769240?

    版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
    展开全文
  • 散列函数和数字签名

    2019-10-17 14:35:24
    散列函数作用不是完成数据的加密解密,而是用于验证数据的完整性。散列值通常是一个短的随机字母数字组成的字符串。 上述流程中收发双方通信前已经协商了具体的散列算法,并且该算法是公开的,如果消息...

    散列函数:也称作哈希函数,消息摘要函数,单向函数或杂凑函数。散列函数的作用不是完成数据的加密和解密,而是用于验证数据的完整性。散列值通常是一个短的随机字母和数字组成的字符串。

     

            上述流程中收发双方通信前已经协商了具体的散列算法,并且该算法是公开的,如果消息在传递过程中被篡改,则不能以已获得的数字指纹相匹配。签名即变相的使用摘要算法获得数字指纹。

            对于加密散列算法的最重要的因素是他们产生不可逆的和独特的哈希值。不可逆性,数据一旦产生哈希值,那么就不可能通过单一的哈希值解出原始的数据。独特性,两个不懂的数据是不能产生同样的哈希值

            散列函数的特性:

            1、消息长度不受限制

            2、对于给定的消息,其散列值的计算很容易

            3、如果两个散列值不同,则这两个散列值的原始输入消息也不同。

            4、散列函数的运算是不可逆的

            5、对于一个一直的消息和其散列值,要找到另一个消息使其获得相同的散列值是不可能的

            6、任意两个不同消息的散列值一定不同

     

            散列函数的常用算法有:

            MD消息摘要算法 (MD2、MD4、MD5),通过MessageDigest类完成。如果需要以流的形式处理完成消息摘要,则需要使用DigestInputStream和DigestOutputStream。其特点是对同一段数据做多次摘要处理后,其摘要值完全一致(判断摘要结果是否一致:assertArrayEquals(data1,data2))。摘要长度为128字节

           JAVA实现(SUN):

                  MessageDigest md = MessageDigest.getInstance("MD5");

                  byte[] b = md.digest(data);

     

            SHA:安全散列算法(SHA-1, SHA-224, SHA-256, SHA-384, SHA-512,后四种并称SHA-2)。与MD算法相比,摘要长度更长,安全性更高。SHA-1可以生成一个被称为消息摘要的160位(20字节)散列值,散列值通常的呈现形式为40个十六进制数。SHA-2以摘要信息字节长度命名,其中SHA-224是为了符合3DES所需的密钥长度定义的。SHA后缀的256等即摘要结果长度的位数。

     

            MAC:消息认证码算法, 带秘密密钥的哈希函数,消息的散列值由只有通信双方知道的秘密密钥K来控制。此时Hash值称作MAC。

           MD分支:Hmac-MD2、Hmac-MD4、Hmac-MD5;

           SHA分支:Hmac-SHA1、Hmac-SHA256、Hmac-SHA384、Hmac-           SHA512、Hmac-SHA224等;

           |算法|摘要长度(位)|备注|

           |Hmac-MD5|128|JDK 6提供|
           |Hmac-SHA1|160|JDK 6提供|
           |Hmac-SHA256|256|JDK 6提供|
           |Hmac-SHA384|384|JDK 6提供|
           |Hmac-SHA512|512|JDK 6提供|
           |Hmac-MD2|128|Bouncy Castle实现|
           |Hmac-MD4|128|Bouncy Castle实现|
           |Hmac-SHA224|224|Bouncy Castle实现|

    算法支持:SUN、Bouncy Castle、Commons Codec

     

    数字签名:带密钥的消息摘要算法。通过散列函数确保数据内容的完整性并不够,还需要确保数据来源的可认证(鉴别)性和不可否认性。完整性、认证性、不可否认性正是数字签名的主要特征。也就是说,数字签名是非对称加密和债市要算法的合体。包含签名和验签,遵循“私钥签名,公钥验签”

    展开全文
  • 散列函数,(也叫哈希函数,台湾称杂凑函数)是一个将(通常)较大的定义域内容映射到一个(通常)较小的值域内的函数,散列函数是一个公开的函数,它将任意长的信息映射到一个固定长度的信息的函数。 构造散列函数的目标是...
  • 加密散列函数。加密散列函数H(⋅)是一种确定性数学算法,它将任意长度的字符串映射到固定长度的比特串,即。H(m)=ℎ,其中m是消息,ℎ是哈希值。在理论密码学中,密码散列函数的安全性是使用以下属性定义的(Rogaway&...
  • 散列表的英文叫“Hash Table”,平时也叫它“哈希表”或“Hash表...定义为hash(key),其中key表示元素的键值,hash(key)的值表示经过散列函数计算得到的散列值。 散列函数设计的基本要求: 1 散列函数计算得...
  • 散列、散列函数

    2020-07-12 20:46:02
    1.散列表(Hash table) ...实现从数据项到存储槽名称的转换的,称为散列函数(Hash function)。 下面示例中,散列函数接受数据项作为参数,返回整数值0~10,表示数据项存储的槽号。 有一种常用的散列
  • 散列函数算法

    千次阅读 2019-04-16 14:28:35
    即H(key)=key或H(key) = a•key + b,其中ab为常数(这种散列函数叫做自身函数) 2.数字分析法 分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率...
  • 构造散列函数

    2014-03-02 00:09:44
    一、散列函数的选择有两条标准:简单均匀。  简单指散列函数的计算简单快速;  均匀指对于关键字集合中的任一关键字,散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说,散列函数能将子集K随机...
  • hash散列值/散列函数

    2020-04-22 15:36:40
    **散列值(hash value,hash codes,hash sums,hashes):**散列函数(散列算法,哈希函数【hash function】)可以将数据压缩成摘要,将格式固定下来。把数据打乱,重新创建一个叫散列值的指纹,好的散列函数中输入域...
  • 散列表之散列函数

    千次阅读 2015-06-26 13:38:20
    全域散列法散列表之散列函数我们在之前的文章《散列表之链接法》中已经提到过,散列函数是散列表的一个难点,一个好的散列可以很大程度上提升散列表的查找删除操作的速度,而一个设计差劲的散列表的,查找删除...
  • 散列函数(哈希函数)是一种大集合到小集合的映射。这种映射肯定会出现不同的关键码被映射到同一个位置的情况,称为冲突。关于冲突有一个重要的度量值:负载因子。 负载因子越大,出现冲突的可能性就越大。扩大散...
  • 单向散列函数

    千次阅读 2018-08-30 10:01:00
    单向散列函数(Hash) 0. Hash函数的性质 常用Hash函数:MD5(128bit)、SHA-1(160bit)等。1. 使用Hash函数进行完整性验证的模型   2. 使用Hash函数进行口令验证(1)    3. 使用Hash函数进行口令验证(2)   ...
  • 散列函数、散列表、冲突 散列函数 散列函数构造方法 直接定址法 除留取余法 数字分析法 平方取中法 折叠法 处理冲突方法 开放定址法 拉链法 开放定址法 计算增量序列方法 线性探测法会产生堆积现象 ...
  • 散列技术-散列函数的构造方法

    千次阅读 2014-08-24 20:37:45
    1、散列函数的选择有两条标准:简单均匀。  简单指散列函数的计算简单快速;  均匀指对于关键字集合中的任一关键字,散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说,散列函数能将子集K随机...
  • C/C++ 基于对勾函数双曲线实现高效率散列函数,实现真正意义上的减少冲突!! 本散列函数基于对勾函数双曲线函数实现。 对勾函数图像: 双曲线函数图像: 散列函数分析 通过以上两个函数我们可以制造一个散列...
  • 散列函数的应用及其安全性 一、 散列函数 散列函数、即曾在数据结构中接触到的哈希函数,这里引用wiki对其的介绍:“散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要...
  • 散列、散列函数、冲突处理

    千次阅读 2017-08-04 17:20:03
    2、散列的基本思想:以关键字key为自变量,通过一个确定的函数 h(散列函数),计算出对应的函数值h(key),作为数据对象的存储地址。3、冲突:可能不同的关键字会映射到同一个散列地址上, 即h(keyi) = h(keyj)(当...
  • 散列函数的输出应该在 0 范围值之间,不包括范围值。 例如,如果范围是 20,则该函数应始终返回 0 到 19 之间的值。 均匀度 函数返回任何给定输出的概率应该相等。 这意味着如果范围是 10,那么输入返回特定值的...
  • 2. 散列函数的构造方法2.1 数字关键词的散列函数构造2.2 字符关键词的散列函数构造 2. 散列函数的构造方法   一个 “好”的散列函数一般应考虑下列两个因素: 1. 计算简单,以便提高转换速度;          ...
  • 散列函数的构造方法

    千次阅读 2018-12-09 09:59:28
    一个“好”的散列函数一般应考虑下列两个因素: 计算简单,以便提高转换速度; 关键词对应的地址空间分布均匀,以尽量减少冲突。 数字关键词的散列函数构造 1 直接定址法 取关键词的某个线性函数值为散列地址,即 ...
  • 单向散列函数算法

    千次阅读 2020-01-01 16:33:46
    单向散列函数算法也称Hash(哈希)算法,是一种将任意长度的消息压缩到某一固定长度(消息摘要的)的函数(该过程不可逆)。 特性: 根据任意长度的信息计算固定长度的散列值; 具备单向性(通过散列值不能反...
  • 若不同的关键字通过散列函数映射到同⼀个值,则称它们为“同义词” 通过散列函数确定的位置已经存放了其他元素,则称这种情况为“冲突” (二)处理冲突的方法——拉链法 用拉链法(又称链接法、链地址法)处理...
  • 1.单向散列函数One-way hash function 1.1 定义 1.2 术语 1.3 特性 1.3.1 散列值长度固定 1.3.2 散列值计算快速 1.3.3 散列值抗碰撞性极强 1.3.4 散列值计算是单向不可逆 1.4 应用 1.5 常见类型 2.go语言...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,315
精华内容 23,726
关键字:

散列函数的定义和作用