计算文件的hash值,python中的hash函数

　　1.你可以简单的把哈希值理解为一段数据(某个文件，或者某个字符串)的DNA，或者身份证；

　　2.通过某种哈希算法(MD5，SHA-1等。都是典型的)，一个长的数据映射成一个短的数据，就是大数据的哈希值。他有这样一个特点，他是独一无二的。一旦大数据发生变化，哪怕是微小的变化，他的哈希值都会发生变化。另一方面，既然是DNA，就保证了没有两个数据的哈希值是完全一样的。

　　3.正是因为这个特点，所以经常用来判断两个文件是否相同。比如你从网络上下载一个文件，你只需要比较文件的原始哈希值和下载文件的哈希值。如果相同，说明两个文件完全一致，文件在下载过程中没有被破坏。如果不是，说明下载的文件与原文件不同，文件在下载过程中被损坏。

　　大蟒

　　参考翻译自：《复杂性思考》和相应的在线版本：http://greenteapress.com/complexity/html/thinkcomplexity 004.html。

　　哈希表可以用于非常快速的查找操作，查找时间是常数，元素不需要按顺序排列。

　　Python内置的数据类型：dictionary，用哈希表实现。

　　为了解释哈希表是如何工作的，让我们尝试不使用字典来实现哈希表结构。

　　我们需要定义一个包含键值映射的数据结构，并同时实现以下两个操作：

　　add(k, v):

　　添加从keykto映射到valuev的新项目。

　　对于Python字典d，这个操作被写成[k]=v。

　　get(target)

　　查找并返回对应于keytarget的值。

　　用Python字典d，这个操作就是written[target]ord . get(target)。

　　一种简单的方法是建立线性表，用元组实现键和值的映射关系。

　　Class LinearMap(object): 线性表结构 def _ _ init _ _(self):self . items=[]def Add(self，K，v): #添加元素self.items.append ((k，v)) def get (self，K): #在self中查找key，val的元素。线性项：如果key==k: # key存在，返回值，否则抛出异常返回值抛出KeyError。我们在使用add添加元素时可以保持条目列表的有序，而在使用get时采用二分搜索法，时间复杂度为O(log n)。但是，在链表中插入一个新元素实际上是一个线性操作，所以这种方法并不是最好的。同时，我们仍然没有达到恒定搜索时间的要求。

　　我们可以做如下改进，将整个查询表分成几个更小的列表，比如100个子段。通过hash函数，得到一个键的hash值，然后通过计算，添加或者查找哪个分段。相比从零开始搜索列表，时间会大大缩短。虽然get操作的增长仍然是线性的，但BetterMap类使我们离哈希表更近了一步：

　　Classmap (object): 建立更快的查询表 def __init__(self，N=100): self.maps=[] #范围内I的通用表(n): #建立N个空的子表self . maps . append(linear map())def Find _ map(self，K): #计算索引值index=hash (k)% len (self.maps)返回self.maps [index] #返回索引子表的引用#查找合适的子表(linear map对象)，add和find def add(self，K，V): m=self。

　　if _ _ name _ _= _ _ main _ _ :table=better map()price data=[( hohner 257 ，257)，( SW1664 ，280)，( SCX64 ，1090)，( SCX48 ，830)，( Super64 ，2238)，( CX12 ，1130)，( Hohner270 ，620)，( F64C ，9720)，( S48 ，1988)] for item，price

　　当n=100时，BetterMap的搜索速度是LinearMap的100倍左右。

　　显然，BetterMap的搜索速度受到了参数n的限制，每个LinearMap的长度都不是固定的，所以仍然是对分段中的元素进行线性搜索。如果我们可以限制每个子段的最大长度，使得在单个子段中搜索的时间责任有一个固定的上限，那么LinearMap.get方法的时间复杂度就变成了常数。因此，我们只需要跟踪元素的数量。每当LinearMap中的元素数量超过阈值时，我们将重新排列整个哈希表，并添加更多的线性映射，这将确保搜索操作是一个常数。

　　下面是hashtable的实现：

　　class hashmap(object):def _ _ init _ _(self):#将总表初始化为，容量为2的表(包括两个子表)self . maps=better map(2)self . num=0 #表中的数据个数def get(self，K):return self . maps . get(K)def add(self，K，v): #如果当前元素个数达到临界值(子表总数)，重新排列#扩展总表，将子表个数增加到当前元素个数的两倍！if . num==len(self . maps . maps):self . resize()#添加新元素self.maps.add (k，v) self.map=1defresize (self): 重排操作，添加新表，注意重排需要线性时间 #首先构建新表，子表个数=2 *元素个数new _ maps=better map(self . num * 2)for m in self . maps . maps:#检索每个旧的子表for k， V m.items: #将子表的元素复制到新的子表new _ maps.add (k，v) self.maps=new _ maps #使当前表成为新表。 重点是添加部分。这个函数检查元素的数量和BetterMap的大小。如果相等，则为“平均每个LinearMap中的元素个数为1”，然后调用resize方法。

　　Resize创建一个新表，其大小是原始表的两倍，然后遍历旧表中的元素“rehashes 再哈希”，并将它们放入新表中。

　　调整大小的过程是线性的，这听起来很糟糕，因为所需的哈希表有一个常数时间。但是要知道，我们并不需要经常重排，所以加法运算大部分时间是常数，偶尔也是线性的。由于添加到n个元素的总时间与n成正比，所以每次添加的平均时间是一个常数！

　　假设我们要添加32个元素。流程如下：

　　1.因为初始长度为2，所以前两次加法不需要重排，第一次和第二次加法的总时间为2。

　　2.第三次添加，重排为4，用了2个小时，第三次是3个小时。

　　3.第4次添加用了1次。到目前为止，总时间是6。

　　4.第5次加法，重排为8，耗时4小时，第5次为5小时。

　　5.第6 ~ 8次一共拍了3张。到目前为止，总时间是6 5 3=14。

　　6.第9次相加，重排16，用了8个小时，第9次是9个小时。

　　7.第10 ~ 16次，耗时7小时。到目前为止，总时间是14 9 7=30。

　　加32次后，总时间为62单位时间。从上面的过程中，可以发现一个规律。n个元素相加后，当n是2的幂时，当前总单位时间是2n-2，所以平均相加时间肯定小于2个单位时间。

　　当n是2的幂时，是最合适的量。当n变大时，平均时间略有上升，但重要的是，我们达到O(1)。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。