Python数据结构与算法-哈希map的实现及原理

Python022

Python数据结构与算法-哈希map的实现及原理,第1张

1-collections.MutableMapping

1.1 概念：这是什么？

大家可能想知道这一串英文是什么意思？其实只需要了解在collections库当中有一个非常重要的抽象基类MutableMappin

g，专门用于实现map的一个非常有价值的工具。后边我们会用到它。

2-我们的map基类

2.1 实现这个类

这个基类其实也就是确定了键值对的属性，并且存储了基本的比较方法。它的对象就是一个键值对咯。这个很好理解。有点类似object的感觉。

3-通过map基类实现的无序映射

给大家看一个上边的例子，这个例子来源于网络，自己改了改，能用，更加详细而已，凑合看.

4-Python哈希表的实现的基类

4.1 咱有话直说：上才（代）艺（码）

如果还不知道哈希表概念的同xio，请参考 python进阶之数据结构与算法–中级-哈希表（小白piao分享） 。废话不多说，咱们撸代码：

OK了，基本的哈希表就实现了，其实仔细想想很容易，但是自己要能实现还是要理解哈希表的本质哦，外加一定量的练习才可以熟练掌握，练习的目的就是为了熟练而已。

5-分离链表实现的具体哈希map类

说明：这玩意只是一种降低冲突的手段，上一节提过，降低冲突最好的地方是发生在元组进入桶的时候，所以想必大家猜到了，接下来的分离链表也就是为了self._bucket_xxxxxxx系列方法做准备。这里之所以在上边使用@abstractmethod就是为了继承实现，目的可以实现多种将冲突的哈希表。分离链表的概念上一节也有的。

“见码入面”（借鉴：见字如面这个电视节目，有兴趣可以看看，还不错的）：

6-用线性探测处理冲突的哈希map类

这种方式的好处不需要再去借助其他额外的赋值结构来表示桶。结构更加简单。不会再像上一种方法还要让桶是一个UnsortedTableMap的对象。

代码如下：

思路：

1、首先采用命A=0,C=1,G=2,T=3. 就相当于4进制数字，然后采用karp-Rabin算法转换成唯一十进制数字。由于用此算法的哈希函数为：hash(value)=value*(4^(k-q-1))

value是该字符对应的值，k是kmer长度,q是此字符在字符串的位置范围在[0-(q-1)]。然后把一个kmer里面所有字符的hash值求和就行了。

2、那么很容易看出来，对于连续的下害常愤端莅得缝全俯户一个Kmer，就有推理公式了 hashNew=addValue+(hashOld-deleteValue*(4^(k-1)))*4hashNew就是往右平移一个字符的kmer hash值，hashOld就是平移之前的值，addValue就是平移后右边多的一个字符，deleteValue就是平移后左边少的一个字符。这样整个hash表建立的时间复杂度约为O（m+k）,m是整个文本长度。

3、由于kmer长度如果过长，其hash值过大，会造成内存不够溢出的现象，所以kmer内部定死为10 。那么问题就来了，如何应对不同的kmer值。分三种情况。

第一种：q>10

这种可以将kmer以10为单位，将hash表中对应值取出，然后对结果进行分析，这边分析方法为建立两个数组一个二维数组unionName储存位置关系，一个一维数组unionScore,计数用。 思路就是首先第一轮初始化unionName[Name][Pos]全部赋值Pos 并初始化unionScore，然后再第二轮匹配如果unionName[Name][Pos-cycle]=Pos-1则将其赋值为当前Pos，cycle为当前循环次数。并将当前循环数存入unionScore[NAME]中。最后当unionScore[NAME]值也就是循环数为k-1，即我们需要的交集了。

第二种：q=10

直接求出hash值，取出相应的值即可。

第三种：q<10

可以用前缀种子+后缀种子交集产生。

前缀种子：在字符串后面补字符直到长度等于K，这个很容易看出来 最小是全补A，最大是全补T，然后将最小值到最大值之间的hash值即为所求。

后缀种子：后缀种子和前缀种子不同就是在字符串左边补齐字符。所以此时需要进行变换。只要对前置种子产生的值变化下就行了。(preValue-minValue)*(4^(K-q))+hash(p) 。其中preValue就是对应的前置种子的hash值，minValue就是前置种子中最小值也就是全补A的情况，hash（p）就是字符串长度为p时候的hash值。

交集就是先求后缀种子所有的值，再加上 前缀种子中起始位置在[0-(k-1)]中的值。

将以上 C 语言代码转换为 Python 语言可能需要对哈希表和其他数据结构进行重新实现。但是可以提供一个类似的实现方式

def search_hash(hash_table, name):

collisions = 0 # to keep track of number of collisions

index = hash_function(name)

while hash_table[index] is not None and hash_table[index]['name'] != name:

collisions += 1

index = collision_resolution(index)

if hash_table[index] is not None:

print("Search successful! Number of collisions:", collisions)

print("Name: ", hash_table[index]['name'])

print("ID: ", hash_table[index]['id'])

print("Phone: ", hash_table[index]['phone'])

else:

print("Search unsuccessful.")

这个例子使用了字典来存储联系人的信息，其中 'name'，'id' 和 'phone' 是字典的键。hash_function() 和 collision_resolution() 函数可以用 Python 中的内置函数来实现，或者自己实现。

注意，这只是一种类似的实现方式，并不能完全替代原来的代码，还需要根据实际需求进行修改。

另外,在 Python 中可以使用字典或字典组成的列表来存储哈希表,可以使用字典中的 get() 方法或者列表中的 in 关键字来查找一个元素是否在字典或列表中，如果要实现类似 C 语言中的冲突解决方式，可以在字典中使用链表或线性探测法来实现。

这里只是给出了一种可能的实现方式，具体实现还需要根据具体需求进行调整。