哈希算法

Python哈希查找，构建简单哈希表
http://blog.csdn.net/tingyun_say/article/details/51777159

def find(arr,j):
    len1=len(arr)
    hasharr=[0]*(len1+5)
    arr2=[0]*(len1+5)
    i=0
    while i<len1:
        a=arr[i]%17
        while arr2[a]!=0:
            a+=1
            if i == len1:
                i=0
        hasharr[a]=arr[i]
        arr2[a]=1
        i+=1
    print(hasharr)
    print('\n')
    print arr2
    
    
arr=[10,8,15,45,7,5,6,2,11,23,4,778,9,5,12]

len1=len(arr)
hasharr=[0]*(len1+5)
arr2=[0]*(len1+5)
i=0
while i<len1:
    a=arr[i]%17
    #print(a)
    while arr2[a]!=0:
        a+=1
        if i == len1:
            i=0
    hasharr[a]=arr[i]
    arr2[a]=1
    i+=1
print(hasharr)
print('\n')
print arr2


j=10
num=j%17
while num<(len1+5):
    if arr2[num]==1:
        if hasharr[num]==j:
            print('找到元素，在hash表位置：%s处'%num)
            num=len1+5
        else:
            num+=1
    else:
        print('不存在’)
        num=len1+5

一、数学定义中的哈希算法

由哈希算法计算出来的值，即哈希值

1、一个哈希算法的案例：
回忆小学数学，如何判断一个整数能否被3整除？（模三算法）
注意：模三算法第一次运行得到的值如果位数太多（导致仍然无法一眼判断出此值能否被三整除），可再次模三（递归），直至取得个位数，递归本身也是模三算法的一部分

2、结论：
哈希算法是一个特征算法，哈希值是一个特征值
特征值：即这个值能够反映出原始值的某个特征（比如“能否被3整除”这个特征）

3、哈希算法的特征：
1、不可逆（已知输出值，不可反向推算出输入值）
2、结果定长（在计算机里指的是所占用的字节数，在数学里指的是数字位数）
3、若算法确定，则结果唯一（数字指纹特性）

4、反例：
加一算法：f(x) = x + 1，不是哈希算法，因为可逆
加随机数算法：f(x) = x + random，不是哈希算法，因为算法确定时，结果不唯一（不是指纹）
平方算法：f(x) = x ^ 2，不是哈希算法，因为不定长

5、模三算法是一个“不好的哈希算法”，因为哈希值极易重复
好的哈希算法，重复概率小。
通过增加参数、计算逻辑复杂化等方式，可大幅减少重复率

二、计算机应用中的哈希算法

用处：
加密
验证
内存寻址（散列算法、散列值）
最开始的用处
1、加密：
用户输入密码，前端计算出hash值传递到后端，后端判断此值与数据库中保存的原密码的hash值是否一致。
若一致，则表示用户输入的是正确密码；反之是错误密码。
如此，在网络传输层和后端数据库中都不用保存原密码，而只需要保存hash值即可，确保了密码安全。即使黑客抓包或攻破后端数据库，也只能得到密码的hash值，而得不到原密码。
（根据不可逆特性，通过hash值无法计算出原密码。并且，好的hash算法重复率低，不易出现“客户输入错误密码，但hash值与正确密码一致，导致此错误密码仍能验证通过”的情况）

直接保存密码 效率高

定长，一方面计算机知道位数 提高效率 一方面要去计算降低效率

2、验证：
假设网站后端有一个文件（在计算机中，一切皆由二进制数字组成，因此可认为一切文件皆是数字）。网站管理员使用一个算法计算出此文件的hash值，并公布该hash值和该算法，当用户下载这个文件到本地之后，使用该算法重新计算一遍hash值，与网站管理员公布的hash值核对，若一致，则可认为该文件在传输过程中没有损坏、没有被黑客掉包。
（利用了哈希值的数字指纹特性）

3、内存寻址：
内存条由无数个内存颗粒组成，文件就保存在内存条的固定区域中。

3.1、住酒店的例子：
内存条就像一个酒店，每块内存区域就像酒店的一个房间，需要保存的数据就是客人，存数据的过程就是客人入住酒店，CPU就是酒店前台，负责管理所有房间。

3.1.1、传统方法：
客人张三（身份证号123456）入住酒店，酒店前台随机安排一个房间给张三。若第二天有人来酒店找张三（有一个程序需要寻找张三这个文件），只能一个一个房间找，效率低下。

3.1.2、哈希方法：
客人张三（身份证号123456）入住酒店，酒店前台根据某个hash算法，输入张三的身份证号，计算得到一个数字（假设为26），于是安排张三入住2楼第6个房间。若第二天有人来酒店找张三（有一个程序需要寻找张三这个文件），只需告知前台张三的身份证号，通过该算法直接就能找到张三的位置在2楼第6个房间，效率高。

3.2、实际应用中：
3.2.1、对于硬盘：
一个文件就是一个人，而文件名（字符串的本质是unicode编码，所以文件名也是数字）就是这个人的身份证号，根据特定算法，操作系统就可以快速找到文件在硬盘上的位置

3.2.2、对于内存条：
文件从硬盘被读入内存之后，是没有文件名的。因此操作系统会给这个文件赋予一个独一无二的值（称为key），通过key计算出hash值，通过hash值确定该文件在内存中的位置。当程序使用CPU寻址时，告知CPU所要找的key，CPU即可通过hash算法快速找到文件的确定位置。文件在内存中称之为value，一个key对应一个value。key-value，即：键值对。

要key值为何还要哈希值

单独位置存放哈希值

3.3、正因为哈希算法和哈希值可以用来排列文件、给文件定位，因此又称为散列算法、散列值。

4、需要注意的点：

4.1、键值对内存模型的实际运用中，实际上是新建了一个数组，hash值对应数组下标，该数组称为哈希表（散列表）；

4.2、由于计算出hash值并不连续，因此哈希表中的大多数位置其实是空的。这也是键值对内存模型的缺点：占用内存太大，牺牲内存容量来换取寻址速度；

4.3、hash值不一定是十进制数，例如著名的MD5算法，计算出的hash值就是十六进制数；

4.4、hash值只能尽量避免重复，无法彻底杜绝重复。所以在实际运用中，总会出现两个key拥有同一个hash值的现象；

4.5、在内存寻址中，当hash值重复时，通常有三种方法来避免冲突

4.5.1、rehash法：顾名思义，换个算法重新hash一次，实际操作中并不会更换算法，但是会更换算法中的参数，使hash值不一致。缺点是rehash后所有文件需要重新排列一次，消耗CPU；

4.5.2、进位法：通过4.1可知，哈希表中大多数位置其实是空的。所以若hash值重复，可以将文件就近放在相邻的空区域中，若相邻的空区域也有文件，则继续寻找相邻的空区域，直至找到，缺点是后期寻址时有可能不能一次成功。

4.5.3、链表法：当hash值重复，将第N个文件放在对应的数组下标区域的下方（下方指的是C语言指针向Y轴负方向偏移一位），在第一个文件上增加一个指针指向第二个文件，在第二个文件上增加一个指针指向第三个文件……，以此类推，组成一个链。缺点是当删除链表上的某个文件时，链表断裂，需重新建立指针，内存模型过于复杂。