1. 映射数据结构的定义

将数据项以关键码key和数据值data的方式存储，其中关键码key可用于查询关联的数据值data，这种数据结构称为映射数据结构。

2.映射数据结构的特性

（1）关键码唯一

（2）通过关键码确定一个数据值

3.映射结构的子结构---散列结构

3.1 散列结构的定义

把任意数据通过散列函数压缩映射成一个固定范围的整数下标直接定位存储位置，即在规定范围内存储带坐标的数据，这种数据结构称为散列，最常见的散列结构就是散列表。

映射结构是在散列结构的基础上额外添加了一个数据结构存储所谓的‘任意数据’，字典结构就是典型的映射数据结构。

3.2 散列结构的属性

（1）散列函数

（2）散列地址

（3）散列槽

4.映射结构的python实现

下面的代码实现中规定了固定的映射长度，且采用的探测方法为线性探测法，因此具有很大的局限性。

# 映射数据结构的实现
class MapStructure:
    def __init__(self):
        # 映射数据结构包括长度、关键码列表和数据值列表属性
        self.size = 11  # 规定起始长度
        self.slots = [None] * self.size  # 扩充关键码列表
        self.data = [None] * self.size  # 扩充数据值列表
    def hashfunction(self,key):
        # 定义hash函数
        return key% self.size  # 使用%避免地址超出范围
    def rehash(self,old_hash):
        # 线性探测法，给定旧hash地址返回新hash地址
        return (old_hash +1)% self.size
    def put(self,key,data):
        hash_value = self.hashfunction(key)  # 哈希地址
        if self.slots[hash_value] is None:
            # 如果哈希地址对应关键码列表中的值为空
            self.slots[hash_value] = key
            self.data[hash_value] = data
        else:
            # 哈希地址对应关键码列表中的值不为空
            if self.slots[hash_value] == key:
                # 关键码列表对应值是key
                self.data[hash_value] = data  # 直接修改关键码对应的数据值
            else:
                # 关键码列表对应值不是key，原hash地址被占用需向前探测
                next_slot = self.rehash(hash_value)  # 用线性探测创建一个新的hash地址
                while self.slots[next_slot] != None and self.slots[next_slot] != key:
                    # 如果新hash地址依旧被占用则反复执行线性探测步骤
                    next_slot = self.rehash(next_slot)
                if self.slots[next_slot] == None:
                    # 如果新hash地址对应关键码列表中的值为None，则直接占用
                    self.slots[next_slot] = key
                    self.data[next_slot] = data
                else:
                    # 如果新hash地址对应关键码列表中的值不为None，则修改数据值列表中对应hash地址的数据值
                    self.data[next_slot] = data
    def get(self,key):
        start_slot = self.hashfunction(key)  # 起始hash地址
        data = None
        stop = False
        found = False
        position = start_slot
        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 == start_slot:
                    # 探测回到原位置时停止循环
                    stop = True
        return data