python中可哈希的数据类型,python的哈希函数

　　哈希表(也叫哈希表)是一种可以根据键值直接访问的数据结构。也就是说，它通过将键值映射到表中的某个位置来访问记录，以加快搜索速度。这个映射函数叫做散列函数，存储记录的数组叫做散列表。

　　python中的Dict类型就是哈希表的原理。存储方式为key-value，通过键可以快速访问值。字典访问操作的时间复杂度为O(1)。

　　用python实现一个简单的哈希表：key是一个纯数字作为索引，它存储在一个线性表中。

　　class hashtable:def _ _ init _ _(self，size):self . elem=[none for I in range(size)]#使用列表数据结构作为哈希表元素存储方法self.count=size #最大表长def hash(self，key):返回键% self.count # Hash函数采用除法并留余数的方法def insert_hash(self，Key，value): 将关键字插入哈希表 address=self.hash(key) #在self的同时查找哈希地址。ELM[地址]: #当前位置有数据，有冲突。Address=(address 1)% self.count #线性检测下一个地址是否可用。self.elem[address]=value #如果没有冲突，直接保存。DEF _ HASH (self，key): 查找关键字并返回布尔值 star=address=self . HASH(key)while self . elem[address]！=key:address=(address 1)% self . count如果不是self.elem [address]或者address==star: #表示还没有找到或者循环到起始位置返回False返回True如果关键字是k，其值存储在f(k)的存储位置。因此，不需要比较就可以直接获得搜索到的记录。这个对应关系F叫做哈希函数，按照这个思路建立的表叫做哈希表。

　　不同的关键字可能得到相同的哈希地址，即k1k2，f(k1)=f(k2)。这种现象叫做碰撞(英文：Collision)。对于这个哈希函数，具有相同函数值的关键字称为同义词。综上所述，根据哈希函数f(k)和处理冲突的方法，将一组关键字映射到一个有限的、连续的地址集(区间)，将地址集中关键字的“映像”作为记录在表中的存储位置，称为哈希表。这个映射过程称为哈希表制作或哈希，产生的存储位置称为哈希地址。

　　如果关键字集合中的任意关键字被哈希函数映射到地址集合中的任意地址的概率相等，这种哈希函数称为均匀哈希函数，就是通过哈希函数使关键字得到一个“随机地址”，从而减少冲突。

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