映射Map抽象数据类型及python实现

    python中的数据类型字典可以保存key-value键值对的数据类型，根据关键字key可以查询关联的数据值data，这种键值关联的方法称为“映射Map”。ADT Map的结构是键-值关联的无序集合，关键码具有唯一性。

    ADT Map定义的操作如下：

Map()：创建一个空映射，返回空映射对象

put(key,val)：将key-val关联对加入映射中，如果key已存在，将val替换旧关联值

get(key)：返回给定key关联的val，如不存在返回None

del：删除key-val关联

len()：返回映射中key-val关联的数目

in：返回key是否存在关联中，布尔值

    使用字典的优势，给定key可以很快得到关联的data。但为了快速查找的目标，可以采用列表数据结构加快速查找或者二分查找。当然更为合适的是使用散列表实现，这样查找可以达到最快O(1)的性能。

    因此下面我们用一个HashTable类来实现ADT Map。该类包含了两个列表作为成员，其中一个slot列表用来保存key，另一个平行的data列表用于保存数据项。

    在slot列表查找到一个key的位置以后，在data列表相同位置的数据项即为关联数据。

哈希表实现映射

    如上图，保存key的列表就作为散列值来处理，这样可以迅速查找到指定的key。但是要注意散列表的大小，虽然可以是任意数，但考虑到要让冲突解决算法能有效工作，应该选择为素数。

散列表大小

    hashfunction方法采用了简单求余方法来实现散列函数，而冲突解决方法采用线性探测“+1”再散列函数。

hashfunction方法

Map的put方法代码如下：

Map的put方法代码

    若key不存在则没冲突，若key存在，则替换val。有散列冲突则再散列直到找到空槽或key。

    Map的get方法代码如下，跟put类似：

Map的get方法代码

    Map附加代码，通过特殊方法实现对于下标式索引值[]的访问：

附加代码

    散列算法分析：

1、散列在最好的情况下，可以提供O(1)常数级时间复杂度的查找性能，但有散列冲突的存在，查找次数就没有这么简单。

2、评估散列冲突的最重要信息就是负载因子，如果较小，散列冲突的几率就小；如果较大，意味着散列表填充较慢，冲突会越来越多，冲突解决也越复杂，也就需要更多的比较来找到空槽；如果采用数据链的话，意味着每条链上的谁项增多。

散列算法分析