数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。最近浏览了52-58，主要内容是散列算法（即哈希算法）的Python实现，也涉及到区块链算法的基础知识。

Hashing散列

查找复杂度为O(1)。哈希表（散列表）是一种数据结构，其中数据项的存储方式尤其有利于查找定位。每一个存储位置称为槽slot，每个槽有唯一的名称。在插入数据项之前，值为空。实现从数据项到存储槽名称的转换的，成为散列函数 hash function。
散列函数接受数据项作为参数，返回整数值0-10，表示数据项存储的槽号（名称）。假设数据项为54.26.93.17.77.31，一种常见的散列方法是求余数，将数据项除以散列表的大小，得到的余数作为槽号。起因是：返回槽号必需在散列表大小范围内。

def a1(item):    return item%11

占据了6个位.
要查找就无比简单：使用同一个哈希函数，看一下返回槽号中能否有数据项就可，这就是O(1)复杂度的查找算法。

【冲突collision】，求到同一个余数怎样办？

完美散列函数，定义：给定一组数据项，假如一个散列函数能把每个数据项映射到不同的槽中，那么这个散列函数就是【完美的哈希函数】。但假如数据项经常变动，则很难有一个系统性方法来设计完美的散列函数。得到完美散列函数的方法：
一种方法使扩大散列表的容量，大到所有可能出现的数据项都能够占据不同的槽-这方法对于可能数据项范围。
过大的情况并不适用，11位手机号要求百亿个槽-impossible。
退而求其次：冲突尽量少，计算难度低、充分分散数据项。
散列技术还用在信息解决的很多领域，因为完美散列函数能够对于任何不同的数据生成不同的散列值
假如将散列值当作数据的指纹或者者摘要，这种特性被广泛应用在数据的一致性校验上
【完美散列函数】特征：由任意长度的数据生成【唯一】长度固定的指纹，在肯定数量范围内是可能的
【压缩性】：无穷大的数据也是这个
【易计算性】：得到哈希值容易，而反推元数据不可能
【抗修改性】：对原数据的微小变动，都会引起哈希值的极大改变
【抗冲突性】：找到对应同一个哈希的两个元数据是非常困难的
MD5函数：Message Digest将任何长度的数据变换为固定长为128位-16字节的摘要。
SHA 函数：Secure Hash Algorithm是另一组散列函数 SHA-0/1输出哈希值160位。SHA-256/224 输出256位，224位，还有512.384等。160位二进制相当于10的48次方，水分子数量是10的47次方，宇宙所有基本例子大约是72-87次方。
Python自带hashlib，包括了md5，sha1，sha224，sha256，sha384，sha512等6种哈希函数。

import hashlibprint(hashlib.md5("Hello world!".encode("utf-8")).hexdigest())#用update方法对任意长的数据分部分来计算m=hashlib.md5()m.update("hello world".encode("utf-8"))m.update("sasd".encode("utf-8"))m.update("22".encode("utf-8"))print(m.hexdigest())#这样不论多大的数据都不会有内存不足问题

应用1
完美哈希函数用于文件一致性判断，为每个文件计算哈希值，比照哈希值可知文件能否一致。用于网络文件下载完整性校验，用于文件分享系统，网盘中相同文件不需要存储屡次。
应用2
加密形式保存密码，仅保存密码的哈希值，客户输入密码后计算哈希值并比对
无需保存密码的明文就可判断客户能否输入了正确的密码。
应用3 防文件篡改； 4 彩票投注结果提前公布；

Blockchain

区块Blocks由头head和体body组成，每一个区块头记录了生成时间，前一个block的哈希值。
因为hash抗修改，对某个区块数据的改动必然引起散列值的变化，就需要修改之后所有的区块。
Bitcoin的工作量证实机制下，51%算力才可以执行这种攻击。Bitcoin是10分钟一个区块。
矿工不惜耗费算力计算新区块的hash，最先找到的才能得到新区块。
BItcoin算法设计成有难度系数的问题，矿工需要找到一个数值Nonce，把它跟整个区块数据一起计算哈希，这个哈希值必需小于target才是有效的散列值。
每4年奖励的比特币减半。

哈希函数设计

折叠法：
将数据项按照位数分为若干段，再将几段相加，最后对【散列表大小-槽数】求余，得到散列值
隔数反转的步骤，或者可微调分布，作为补充手段
平方取中法：
平方数中间两位对槽数求余
对非数字：
字符转为ASC2码，求和再求余

def hash(astring,tablesize):    sum=0    for pos in range(len(astring)):        sum=sum+ord(astring[pos])#ord()函数返回字符的ASC2码    return sum%tablesizeprint(hash("hello",12))

对变位词输出相同哈希值-改进，加入位置权重，如+1+2+3。
基本准则：计算要简单，否则还不如用二分查找。

冲突处理solution of collisions

假如两个数据项被散列映射到同一个槽，需要一个系统化的方法在哈希表中保存第二个数据项
这个过程称为处理冲突。完美哈希函数没有此问题，根据定义。
【开放定址】
方法1：为冲突数据项再找一个空槽，从冲突槽开始向后遍历，没有的话再从头遍历-寻觅空槽-开放定址法，open addressing
一一槽寻觅-linear probing线性探测。
在查找时，也要进行顺序查找，直到碰到空槽返回失败。
缺点：clustering连锁式影响其余数据项的插入
改进：跳跃式探测，例如步长改为+3；quadratic probing +1+4+9...
再哈希rehashing；rehash(pos)=(pos+1)%sizeoftable, 跳跃则加n。注意n不能被size整除，可以取size为素数如11，13，17
【数据项链Chaining】
将槽扩大为容纳数据项集合/对数据项链表的引用
缺点：查找时需要遍历集合，查找时间会添加

映射-笼统数据类型 Map

Python最有用的数据类型之一是字典，可以保存key-data键值对的数据类型。
这种键值关联的方法成为映射Map，Map的结构是键值的无序集合，快速查找。
Python实现Map数据结构：

Map()put(key,val)get(key) return valuelen() return number of key-value connectionsin return True/False key in map

可以列表数据结构加顺序查找或者者二分查找
更合适的是使用前述的哈希表实现，这样可以达到最快O(1)的性能
接下来示例使用哈希表class实现map类：slot列表保存key，平行的data列表用于保存数据项
找到一个key的位置后，再data[key]得到对应的值。key表为哈希表

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)#注意self.def1        if self.slots[hashvalue]==None:            self.slots[hashvalue]=key            self.data[hashvalue]=data        else:            if self.slots[hashvalue]==key:                self.data[hashvalue]=data #原地升级            else:                #哈希冲突，两个不同的key值得到了同一个哈希值                nextslot=self.rehash(hashvalue)                while self.slots[nextslot]!= None and self.slots[nextslot]!=key:                    nextslot=self.rehash(nextslot)#不断再哈希运算直到找到空位置或者找到key值                if self.slots[nextslot]==None:#找到空位                    self.slots[nextslot]=key                    self.data[nextslot]=data                else:#找到key                    self.data[nextslot]=data#原衍生地升级    def get(self,key):        startslot=self.hashfunction(key)        data=None        stop=False        found=False        position=startslot        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)                if position==startslot:                    stop=True#遍历完成        return data        def __getitem__(self,key):#实现可以通过map[key]访问value        return self.get(key)    def __setitem__(self,key,data):#类上        return self.put(key,data)

在最好情况下，哈希算法提供O(1)查找性能，冲突会导致开销。使用负载因子衡量冲突大小。
假如负载因子较大，散列表填充较满，槽里数据较多。

排序与查找算法总结

【查找算法】
在有序表或者者无序表上顺序查找，时间复杂度为O(n)。
在有序表上二分查找，最差为O(logn)。
哈希表/散列表可以O(1)查找。
【排序算法】
冒泡、选择、插入排序是O(n2)，谢尔排序在插入排序基础上递增子表排序，复杂度。
在n与n2之间，归并是nlogn，需要空间开销，快排最好是nlogn，在不均衡数据上退化为n2。
冒泡中假如没有发生移位，短路，可以提前退出。-实际却更慢？！
起因：假如使用random.shuffle获取数据测试，每一个数据都不给短路算法发挥的空间，因而更慢。
shuffle会把数据打乱到最乱的程度。