精华内容
下载资源
问答
  • 散列函数
    千次阅读
    2018-04-28 22:19:34

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

        散列函数:一个把查找表中的关键字映射成该关键字对应的地址函数,记为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);
        }
    }


    更多相关内容
  • 散列函数hash-sha1

    2019-05-05 17:39:47
    散列函数hash 基于SHA-1。MATLAB可运行实现。
  • 利用统计分析、生日攻击等方法,针对一类基于混沌系统的带密钥散列函数进行了分析,给出了针对这些算法的伪造攻击和等价密钥恢复攻击。同时,研究了上述攻击奏效的原因,并由此总结了基于混沌技术设计带密钥散列函数时...
  • 单向散列函数

    2022-03-05 17:40:42
    4.单向散列函数的实际应用 1.检查软件是否被篡改 2.基于口令的加密(PBE) 3.消息认证码 4.数字签名 5.伪随机数生成器 6.一次性口令 5.单项散列函数的具体例子 1.MD4和MD5(MD是消息摘要的缩写) MD5 2....

    目录

    1.概念:

    2.特点:

    1.根据任意长度的消息计算出固定长度的散列值:

    2.能够快速计算出散列值

    3.消息不同散列值也不同

    4.单向性

    3.专有名词

    4.单向散列函数的实际应用

    1.检查软件是否被篡改

    2.基于口令的加密(PBE)

    3.消息认证码

    4.数字签名

    5.伪随机数生成器

    6.一次性口令

    5.单项散列函数的具体例子

    1.MD4和MD5(MD是消息摘要的缩写)

    MD5

    2.SHA-1、SHA-256、SHA-384、SHA-512

    SHA-1


    1.概念:

    单向散列函数有一个输入和一个输出,其中输入的称为消息,输出的称为散列值。单项散列函数可以根据消息的内容计算出散列值,而散列值就可以被用来检查消息的完整性。

    2.特点:

    1.根据任意长度的消息计算出固定长度的散列值:

    首先,单项散列函数的输入必须是任意长度的消息。其次,无论输入多长的消息,单项散列函数必须能够生成长度较短且固定的散列值。

    2.能够快速计算出散列值

    3.消息不同散列值也不同:

    为了能够确认完整性,消息中哪怕只有1比特的改变,也必须有很高的概率产生不同的散列值

    4.单向性:

    无法通过散列值反算出消息

    提醒:尽管单向散列函数所产生的散列值是和原来的消息完全不同的比特序列,但是单项散列函数并不是一种加密,因此无法通过解密将散列值还原位原来的消息

    3.专有名词

    1.碰撞:两个不同的消息产生同一个散列值的情况称为碰撞

    2.抗碰撞性:难以发生碰撞的性质

    3.弱抗碰撞性:要找到和该消息具有相同的散列值的另一条消息是非常困难的,这一性质称为弱抗碰撞性

    4.强抗碰撞性:要找到散列值相同的两条消息是非常困难的,在这里,散列值可以是任意值

    (密码技术中使用的单向散列函数,不仅要具备弱抗碰撞性,还必须具备强抗碰撞性)

    5.单向散列函数也称为消息摘要函数、哈希函数或者杂凑函数,输入单向散列函数的消息也称为原像,输出的散列值也称为消息摘要或者指纹

    4.单向散列函数的实际应用

    1.检查软件是否被篡改

    很多软件,都会把通过单向散列函数计算出的散列值公布在自己的官方网站上,用户下载完之后,可以自行计算散列值,然后与官方网站上公布的散列值进行比对,进而判断软件是否被篡改

    2.基于口令的加密(PBE)

    3.消息认证码

    消息认证码是将“发送者和接收者之间的共享密钥”和“消息”进行混合后计算出的散列值

    4.数字签名

    5.伪随机数生成器

    6.一次性口令

    5.单项散列函数的具体例子

    1.MD4和MD5(MD是消息摘要的缩写)

    MD4是由Rivest于1990年设计的单向散列函数,能够产生128比特的散列值,不过由于Dobbertin提出寻找MD4散列碰撞的方法,因此现在它已经不安全了

    MD5是由Rivest于1991年设计的单向散列函数,能够产生128比特的散列值,比MD4更复杂,更安全

    MD5码

    以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位

    按位补充数据

    在MD5算法中,首先需要对信息进行填充,这个数据按位(bit)补充,要求最终的位数对512求模的结果为448。也就是说数据补位后,其位数长度只差64位(bit)就是512的整数倍。即便是这个数据的位数对512求模的结果正好是448也必须进行补位。补位的实现过程:首先在数据后补一个1 bit; 接着在后面补上一堆0 bit, 直到整个数据的位数对512求模的结果正好为448。总之,至少补1位,而最多可能补512位

    扩展长度

    在完成补位工作后,又将一个表示数据原始长度的64 bit数(这是对原始数据没有补位前长度的描述,用二进制来表示)补在最后。当完成补位及补充数据的描述后,得到的结果数据长度正好是512的整数倍。也就是说长度正好是16个(32bit) 字的整数倍 。

    初始化MD缓存器

    MD5运算要用到一个128位的MD5缓存器,用来保存中间变量和最终结果。该缓存器又可看成是4个32位的寄存器A、B、C、D,初始化为  :

    A : 01 23 45 67

    B: 89 ab cd ef

    C: fe dc ba 98

    D: 76 54 32 10

    处理数据段

    首先定义4个非线性函数F、G、H、I,对输入的报文运算以512位数据段为单位进行处理。对每个数据段都要进行4轮的逻辑处理,在4轮中分别使用4个不同的函数F、G、H、I。每一轮以ABCD和当前的512位的块为输入,处理后送入ABCD(128位) 。

    输出

    信息摘要最终处理成以A, B, C, D 的形式输出。也就是开始于A的低位在前的顺序字节,结束于D的高位在前的顺序字节 。

    2.SHA-1、SHA-256、SHA-384、SHA-512

    SHA-1是由NIST设计的一种能够产生160比特的散列值的单项散列函数,SHA-1的消息长度存在上限,但这个值接近2^64比特

    SHA-256、SHA-384、SHA-512都是由NIST设计的单向散列函数,他们的散列值长度分别为256比特、384比特、512比特。这些单向散列函数合起来统称SHA-2,他们的消息长度也存在上限,分别为2^64、2^128、2^128比特

    SHA-1

    SHA-1是一种能够根据上限为2^64比特的消息计算出160比特的散列值的单向散列函数

    整体流程

    1.填充:对消息进行填充处理,使其长度为512比特的整数倍。这里的512比特被称为一个输入分组

    填充是指在消息的末尾添加多余的数据,使其长度成为512比特的整数倍

    例如,要对长度为6字节(48比特)的消息进行填充,将消息改写成二进制的形式:

    01001000   01100101   01101100   01101100   01101111   00101110

     添1

    01001000   01100101   01101100   01101100   01101111   00101110   1

     添0

    在消息末尾添加0,直到消息的长度达到512比特的整数倍,但是,最后一个分组的最后64比特需要空出来以便保存原始的消息长度

    01001000   01100101   01101100  01101100   01101111  00101110   10000000    00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    添加消息长度

    原始的消息长度为48比特,因此将48这个数字转换成二进制并添加在消息末尾

    01001000   01100101   01101100  01101100   01101111  00101110   10000000    00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00000000

    00000000   00000000  00000000  00000000   00000000  00000000  00000000   00110000

    2.计算W0~W79

    根据输入分组的512比特计算出80个32比特的值(W0~W79)

     3.分组处理

    对输入的分组依次进行80个步骤的处理,计算5个32比特的值(A~E)作为SHA-1的内部状态

     80个步骤

     160比特的内部状态是通过名为A、B、C、D、E的5个32比特的缓冲区来表示的,这一操作就是将输入分组的512比特的数据,于SHA-1所保持的160比特的内部状态(5个缓冲区)进行混合

    4.单步处理

     

    展开全文
  • 针对等级角色的权限管理和访问控制,形式化地定义与分析了等级密钥管理问题,提出了一个基于单向散列函数的实用的等级密钥管理方案。该方案允许各等级角色自主选择主密钥,并利用安全的单向散列函数和公开的辅助参数...
  • 散列、散列函数

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

    1.散列表(Hash table)

    散列表(又称哈希表)是一种数据集,其中数据项的存储方式尤其有利于将快速的查找定位。
    散列表中的每一个存储位置,称为槽(slot),可以用来保存数据项,每个槽有一个唯一的名称
    例如:一个包含11个槽的散列表,槽的名称分别为0~10。在插入数据项之前,每个槽的值都是None,表示空槽。
    在这里插入图片描述

    散列函数

    实现从数据项到存储槽名称的转换的,称为散列函数(Hash function)。
    下面示例中,散列函数接受数据项作为参数,返回整数值0~10,表示数据项存储的槽号。
    有一种常用的散列方法是**“求余数”**,将数据项除以散列表的大小,得到的余数作为槽号。实际上,“求余数”方法会以不同形式出现在所有散列函数里,因为散列函数返回的槽号必须在散列表大小范围之内,所以一般会对散列表大小求余。
    :将数据项54,26,93,17,77,31保存到散列表中,使用的散列函数是最简单的求余:h(item)=item%11
    按照散列函数h(item),为每个数据项计算出存放的位置之后就可以将数据项存入相应的槽中。
    在这里插入图片描述
    例子中的6个数据项插入后,占据了散列表11个槽中的6个。槽被数据项占据的比例称为散列表的“负载因子”,这里负载因子为6/11。
    数据项都保存到散列表后,查找就无比简单。要查找某个数据项是否存在于表中,我们只需要使用同一个散列函数,对查找项进行计算,测试下返回的槽号所对应的槽中是否有数据项即可,实现了O(1)时间复杂度的查找算法。

    2.完美散列函数

    给定一组数据项,如果一个散列函数能把每个数据项映射到不同的槽中,那么这个散列函数就可以称为“完美散列函数”。
    对于固定的一组数据,总是能想办法设计出完美的散列函数。但如果数据项经常性的变动,很难有一个系统的方法来设计对应的完美散列函数。

    2.1获得完美散列函数的方法

    获得完美散列函数的一种方法是扩大散列表的容量,大到所有可能出现的数据项都能够占据不同的槽。但这种方法对于可能数据项范围过大的情况并不适用。假如,要保存手机号(11位数字),完美散列函数得要求散列表具有百亿个槽!会浪费很多存储空间。

    2.2好的散列函数需要具备的特性

    冲突最少(近似完美)、计算难度低(额外开销小)、充分分散数据项(节约空间)

    2.3 完美散列函数的更多用途

    除了用于在散列表中安排数据项的存储位置,散列技术还用在信息处理的很多领域。

    • 由于完美散列函数能够对任何不同的数据生成不同的散列值,如果把散列值当做数据的“指纹”或者“摘要”,这种特性被广泛应用在数据的一致性校验上。

    作为一致性校验的数据“指纹”函数需要具备如下特性

    (1)压缩性:任意长度的数据,得到的“指纹”长度是固定的
    (2)易计算性:从原始数据计算“指纹”很容易(从指纹计算原始数据是不可能的)
    (3)抗修改性:对元数据的微小变动,都会引起“指纹”的大改变
    (4)抗冲突性:已知原数据和“指纹”,要找到相同指纹的数据(伪造)是非常困难的

    散列函数MD5/SHA

    最著名的近似完美散列函数是MD5和SHA系列函数。
    **MD5(Message Digest)**将任何长度的数据变换为固定场为128位(16字节)的“摘要”
    SHA(Secure Hash Algorithm)是另一组散列函数

    • SHA-0/SHA-1输出散列值160位(20字节)
    • SHA-256/SHA-224分别输出256位、224位
    • SHA-512/SHA-384分别输出512位和384位
      160位二进制相当于10的48次方,地球上水分子水量估计是47次方
      256位二进制相当于10的77次方,已知宇宙所有基本粒子大约是72~87次方
      python自带MD5和SHA系列的散列函数库:hashlib。包括了md5/sha1/sha224/sha256/sha384/sha512等6中散列函数。具体使用方法如下:
      在这里插入图片描述
      除了对单个字符串进行散列计算之外,还可以用update方法对任意长的数据分部分来计算。这样不管多大的数据都不会有内存不足的问题。如:
      在这里插入图片描述

    完美散列函数用于数据一致性校验

    • 数据文件一致性判断
    • 为每个文件计算其散列值,金对比其散列值即可得知文件内容是否相同
    • 用于网络文件下载完整性校验
    • 用于文件分享系统:网盘中相同的文件(尤其是电影)可以无需存储多次
    • 加密形式保存密码,仅保存密码的散列值,用户输入密码后,计算散列值并比对。无需保存密码的明文即可判断用户是否输入了正确的密码
    • 防文件篡改:原理同数据文件一致性判断
    • 彩票投注应用
      彩民下注前,机构将中奖的结果散列值公布,然后彩民投注,开奖后,彩民可以通过公布的结果和散列值对比,验证机构是否作弊。

    3.散列函数的最酷应用:区块链技术

    区块链是一种分布式数据库。

    • 通过网络的连接的节点
    • 每个节点都保存着整个数据库所有数据
    • 任何地点存入的数据都会完成同步
      区块链最本质特征是“去中心化”
      不存在任何控制中心、协调中心节点,所有节点都是平等的,无法被控制

    区块链组成

    区块链由一个个区块(block)组成,区块分为头(head)和体(body)。区块头记录了一些元数据和链接到前一个区块的信息(生成时间、前一个区块的散列值)。区块体记录了实际数据。
    在这里插入图片描述

    区块链不可修改性

    由于散列值具有抗修改性,任何对某个区块数据的改动必然引起散列值的变化。为了不导致这个区块脱离链条,就需要修改所有后续的区块。由于有“工作量证明”的机制,这种大规模修改不可能实现的,除非掌握了全网51%的计算力。

    4. 散列函数的设计

    (1)折叠法

    折叠法设计散列函数的基本步骤:

    首先将数据项按照位数分为若干段,再将几段数字相加,最后对散列表大小求余,得到散列值。
    例如,对电话号码62767255
    可以两位两位分成4段(62、76、72、55),然后相加(62+76+72+55=265),散列表包括11个槽,那么就是265%11=1,所以h(62767255)=1
    有时候折叠法还会包括一个隔数反转的步骤
    比如(62、76、72、55)隔数反转为(62、67、72、55),再累加(62+67+72+55=256),对11求余(256%11=3),所以h(62767255)=3
    虽然隔数反转从理论上看来毫无必要,但这个步骤确实为折叠法得到散列函数提供了一种微调手段,以便更好符合散列特性。

    (2)平方取中法

    首先将数据项做平方运算,然后取平方数的中间两位,再对散列表的大小求余
    例如,对44进行散列
    首先44*44=1936,然后取中间的93,对散列表大小11求余,93%11=5
    下表示两种散列函数的对比
    在这里插入图片描述
    两个都是完美散列函数,分散度都很好,平方取中法计算量稍大

    对于非数项

    我们也可以对非数字的数据项进行散列,把字符串中的每个字符看做ASCII码,再将这些整数累加,对散列表大小求余。
    如cat,ord(‘c’)==99,ord(‘a’)==96,ord(‘t’)==116
    99+96+116=312
    321%11=4
    python代码实现

    def hash(astring,tablesize):
        sum=0
        for pos in range(len(astring)):
            sum=sum+ord(astring[pos])
        return sum%tablesize
    

    当然,这样的散列函数对所有的变位词(如head和deah)都返回相同的散列值。为了防止这一点,可以将字符串所在的位置作为权重因子,乘以ord值
    在这里插入图片描述
    我们还可以设计出更多的散列函数方法,但要坚持的一个基本出发点是,散列函数不能成为存储过程和查找过程的计算负担。如果散列函数设计太多复杂,去花费大量的计算资源计算槽号失去了散列本身的意义。

    5.冲突解决方案

    如果两个数据项被散列映射到同一个槽,需要一个系统化的方法在散列表中保存第二个数据项,这个过程称为**“解决冲突”**
    前面提到,如果说散列函数是完美的,那么就不会有散列冲突,但完美散列函数常常是不现实的。解决散列冲突称为散列方法中很重要的一部分。

    (1)线性探测

    解决散列的一种发发就是为冲突的数据项再找一个开放的空槽来保存。最简单的就是从冲突的槽开始往后扫描,直到碰到一个空槽。如果到散列表尾部还未找到,则从首部开始扫描。这种寻找空槽的技术成为**“开放定址(open addressing)”向后逐个寻找的方法则是开放定址技术中的“线性探测linear probing”**
    例,我们把44、55、20逐个插入到散列中
    h(44)=0,但发现0#槽已经被77占据,向后找到第一个空槽1#,保存
    h(55)=0,同样0#槽已经被占据,向后找到第一个空槽2#,保存
    h(20)=9,发现9#槽已经被31占据了,向后,在从头开始找到3#槽保存
    在这里插入图片描述
    采用线性探测方法来解决散列冲突的话,则散列表的查找也遵循同样的规则。如果在散列位置没有找到查找项的话,就必须向后做顺序查找,直到找到查找项,或者碰到空槽(查找失败)

    (2)线性探测的改进——再散列(rehashing)

    线性探测的一个缺点是有聚集(clustering)的趋势。即,如果同一个槽冲突的数据项较多的话,这些数据项就回在槽附近聚集起来,从而连锁式影响其它数据项的插入。
    在这里插入图片描述
    避免聚集的一种方法就是将线性探测扩展,从逐个探测改为跳跃式探测
    下图是“+3”探测插入44、55、20
    在这里插入图片描述
    重新寻找空槽的过程可以用一个更为通用的“再散列”来概括
    newhashvalue=rehash(oldhashvalue)
    对于线性探测来说,rehash(pos)=(pos+1)%sizeoftable
    "+3"跳跃式探测:rehash(pos)=(pos+3)%sizeoftable
    跳跃式探测的再散列通式:rehash(pos)=(pos+skip)%sizeoftable
    跳跃式探测中,需要注意的是skip的取值,不能被散列表大小整除,否则会产生周期,造成很多空槽永远无法探测到。一个技巧是,把散列表的大小设为素数,如11
    还可以将线性探测变为“二次探测(quadratic probing)”
    不再固定skip的值,而是逐步增加skip值,如1、3、5、7、9。这样槽号就会是原散列值以平方数增加:h、h+1、h+4、h+9、h+16…

    (3)数据项链(Chaining)

    除了寻找空槽的开放地址技术之外,另一种解决散列冲突的方案是将容纳单个数据项的槽扩展为容纳数据项集合(或者对数据项链表的引用)。这样,散列表中的每个槽就可以容纳多个数据项,如果有散列冲突发生,只需要简单地将数据项添加到数据项集合中。查找数据项时则需要查找同一个槽中的整个集合,当然,随着散列冲突的增加,对数据项的查找时间也会相应增加。
    在这里插入图片描述

    6.抽象数据类型“映射”:ADT Map及散列表实现

    “字典”是python最有用的数据类型之一,是一种可以保存key-data键值对的数据类型,其中关键码key可用于查询关联的数据值data,这种键值关联的方法称为“映射Map
    ADT Map的结构是键-值关联的无序集合,关键码具有唯一性,通过关键码可以唯一确定一个数据值。

    ADT Map定义的操作如下:

    • Map():创建一个空映射,返回空映射对象;
    • put(key,val):将key-val关联对加入映射中,如果key已存在,将val替换旧关联值;
    • get(key):给定key,返回关联的数据值,如果不存在,则返回None;
    • del:通过del map[key]的语句形式删除key-val关联;
    • len():返回映射中key-val关联的数目;
    • in:通过key in map的语句形式,返回key是否存在于关联中,布尔值

    ADT Map实现

    使用字典的优势在于,给定关键码key,能够很快得到关联的数据值data。为了达到快速查找的目标,需要一个支持高效查找的ADT实现。
    可以采用列表数据结构加顺序查找或二分查找。当然,更为合适的是使用前述的散列表来实现,这样查找可以达到最快O(1)的性能。
    下面,我们用一个HashTable类来实现ADT Map,该类包含了两个列表作为成员,其中一个slot列表用于保存key,另一个平行的data列表用于保存数据项。
    在slot列表查找到一个key的位置以后,在data列表对应相同位置的数据项即为关联数据。

    class HashTable():
        def __init__(self):
            self.size=11
            self.slots=[None]*self.size
            self.data=[None]*self.size
    

    保存key的列表作为散列表来处理,这样可以迅速查找到指定的key。注意散列表的大小,虽然可以使任意数,但考虑到要让冲突解决算法能有效工作应该选择为素数。

    ADT Map:put方法代码

    hashfunction方法才用了简单求余方法来实现散列函数,而冲突解决则采用线性探测“加1”再散列函数

    class HashTable():
        def __init__(self):
            self.size=11
            self.slots=[None]*self.size
            self.data=[None]*self.size
            
        def hashfunction(self,key):
            return key%self.size
        def rehash(self,oldhash):
            return (oldhash+1)% self.size
        def put(self,key,data):
            hashvalue=self.hashfunction(key)
            #key不存在,未冲突
            if self.slots[hashvalue]==None:
                self.slots[hashvalue]=key
                self.data[hashvalue]=data
            else:#key已经存在,替换val
                if self.slots[hashvalue]==key:
                   self.data[hashvalue]=data#replace
                else:#散列冲突,再散列,知道找到空槽或者key
                    nextslot=self.rehash(hashvalue)
                    while self.slots[nextslot]!=None and self.slots[nextslot]!=key:
                        nextslot=self.rehash(nextslot)
                    if self.slots[nextslot]==None:
                        self.slots[nextslot]=key
                        self.data[nextslot]=data
                    else:
                        self.data[nextslot]=data
                      
    

    ADT Map:get方法代码

        def get(self,key):
            #标记散列值为查找起点
            startslot=self.hashfunction(key)
            data =None
            stop=False
            found=False
            position=startslot
            #找到key,直到空槽或者回到起点
            while self.slots[position]!=None and not found and not stop:
                if self.slots[position]==key:
                    found=True
                    data=self.data[position]
                else:
                    position=self.rehash(position)#未找到key,再散列继续找
                    if position ==startslot:
                        stop=True#回到起点,停
            return data
    

    通过特殊方式实现[]访问

    def __getitem__(self,key):
            return self.get(key)
        def __setitem__(self,key,data):
            self.put(key,data)
    

    7.散列算法分析

    • 散列在最好的情况下,可以提供O(1)常数级时间复杂度的查找性能。由于散列冲突的存在,查找比较次数就没有这么简单
    • 评估散列冲突的最重要信息就是负载因子lamda,一般来说:如果lamda较小,散列冲突的几率小,数据项通常会保存在其所属的散列槽中;如果lamda比较大,意味着散列表填充较满,冲突会越来越多,冲突解决也越复杂,也就需要更多的比较来找到空槽。如果采用数据链的话,意味着每条链上的数据项增多。
    • 如果采用线性探测的开放定址法来解决冲突(lamda在0-1之间)
      成功的查找,平均需要比对的次数为:在这里插入图片描述
      不成功的查找,平均比对次数为:在这里插入图片描述
    • 如果采用数据链解决冲突(lamda可大于1)
      成功的查找,平均需要比对次数为:1+lamda/2
      不成功的查找,平均比对次数为:lamda
    展开全文
  • 漫谈散列函数

    千次阅读 2020-07-30 16:59:32
    简介:说到散列,一般对应于散列表(哈希表)和散列函数。 我们今天不谈哈希表,仅谈下散列函数。 说到散列,一般对应于散列表(哈希表)和散列函数。我们今天不谈哈希表,仅谈下散列函数。定义引一段百度百科关于...
    简介:说到散列,一般对应于散列表(哈希表)和散列函数。 我们今天不谈哈希表,仅谈下散列函数。

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

    定义

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

    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 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
    展开全文
  • 一种新的基于混沌理论和散列函数的图像加密算法,杨玉军,杨夷梅,为了实现对数字图像的加密,介绍了混沌理论和散列函数的特点,提出了一种基于混沌理论和散列函数的彩色图像加密算法。该算法首先��
  • 首先,先说明一个问题,大部分人都会混淆的概念,那就是散列函数和散列表的概念。其实,散列函数和散列表是两种东西,我本人之前一直认为散列函数和散列表是一种东西,所以我想应该有很多人也这样认为,所以先来澄清...
  • 密码学入门(5):单向散列函数

    千次阅读 2022-02-08 19:16:07
    什么是单向散列函数 单向散列函数(one-way hash function)有一个输入和一个输出,其中输入称为消息(message),输出称为散列值(hash value)。它可以根据消息的内容计算出散列值,而散列值可以用来检查消息的...
  • 散列函数和消息鉴别 鉴别服务是用来提供对通信中实体和数据原发(数据源)的鉴别。鉴别服务是能使通信双方证实对方身份或数据来源。 散列函数的概念 也称为杂凑函数,哈希函数(Hash函数) Hash函数H将可变长度的...
  • 什么是单向散列函数(哈希函数) 单向散列函数就是一种特殊的函数,无论输入的内容的长度多少,它的输出长度都是固定的,而且其输出内容会随着输入内容的改变而改变,而且输入内容小小的改变就会引起输出内容的巨大...
  • 实现原理是:通过散列函数(也叫哈希函数)将元素的键(key)映射为数组下标(转化后的值叫做散列值或哈希值),然后在对应下标位置存储记录值(value)。当我们按照键值查询元素时,就是用同样的散列函数,将键值转化...
  • 单向散列函数 (Hash)

    2021-01-10 15:48:39
    单向散列函数1.1 什么是单向散列函数1.2 术语1.3 单向散列函数的特性1.4 单向散列函数的实际应用1.4.1 检测软件是否被篡改1.4.2 消息认证码1.4.3 数字签名1.4.4 伪随机生成器1.4.5 一次性口令1.5 常用的单向散列...
  • 散列函数、散列算法的Python语言实现
  • 一文搞懂单向散列函数

    千次阅读 2021-09-27 09:50:28
    单向散列函数(one-way hash function)是指对不同的输入值,通过单向散列函数进行计算,得到固定长度的输出值。这个输入值称为消息(message),输出值称为散列值(hash value)。 单向散列函数也被称为消息摘要...
  • 智能卡的散列函数

    2020-11-14 14:53:53
    能否将压缩逆转是没有关系的,因为签名`总可由原来的文件复制出来,用于这种类型计算的函数被称为单向散列函数。  一般而言,单向散列函数是从可变长度的文档导出固定长度值的函数,这个值以压缩的形式代表了文档...
  • 散列函数的设计散列查找的基本思想散列函数的设计原则三种常见的散列函数1. 直接定址法2. 除留余数法3. 平方取中法处理冲突的方法1. 开放定址法2. 拉链法(链地址法) 散列查找的基本思想 在记录的存储位置和它的关键...
  • 平方取中法二、散列函数设计:非数项总结 一、散列(哈希)函数设计方法 1. 折叠法 折叠法设计散列函数的基本步骤: 将数据项按照位数分为若干段; 将几段数字相加; 对散列表大小求余,得到散列值。 例如:对于...
  • 常见数据类型散列函数的简介
  • 单向散列函数-指纹-哈希函数

    千次阅读 2019-11-07 22:51:09
    单向散列函数-指纹-哈希函数1. 什么是单向散列函数2.单向散列函数的性质2.1. 根据任意长度的消息计算出固定长度的散列值2.2. 能够快速计算出散列值2.3. 消息不同散列值也不同2.4. 具备单向性3.术语4. 单向散列函数的...
  • 这个新模块可用于根据中国国家密码管理局发布的规范 GM/T 004-2012 密码哈希算法 SM3 计算文件或内存块的 SM3 消息摘要。
  • 散列表--散列函数

    2022-01-01 17:12:41
    一般想法 理想的散列表数据结构只不过是一个含有关键字的具有固定大小的数组。典型情况下,一个关键字就是一个...这个映射叫作散列函数(hash function),理想情况下它应该运算简单并且应该保证任何两个不同的关键...
  • 常见散列函数

    千次阅读 2020-11-02 16:44:49
    MD5(Message Digest Algorithm 5):是RSA数据安全公司开发... MAC(Message Authentication Code):消息认证代码,是一种使用密钥的单向函数,可以用它们在系统上或用户之间认证文件或消息,常见的是HMAC(用于消..
  • 在负载均衡的解决方法中,散列函数起到了关键作用。 原始散列函数解决负载均衡 散列函数的性质,就是均匀分布在原始散列区间。然后,通过取余操作,再均匀分布到分布式集群的区间内,这样,每台服务器就能实现负载...
  • 散列函数是一个函数,它接受一些输入(对于这个 repo,我们将处理字符串),并输出指定范围内的整数。 散列函数有四个主要属性要符合: 决定论 给定相同的输入,散列函数应始终返回相同的输出,而不管该函数何时或...
  • 国标GB-T 18238对信息技术、安全技术、散列函数的规定
  • 常见散列函数及冲突解决方案

    千次阅读 2020-04-10 21:35:40
    哈希 哈希(Hash)也称为散列,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,这个输出值就是散列值。 哈希算法 哈希表 ...这个映射函数叫做散列函数,存放记录的数组叫做散列表。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 114,317
精华内容 45,726
关键字:

散列函数