什么是哈希表哈希表也叫做散列表，这种表提供了键（key)与值(value)的映射关系。只要给出key，就可以快速找到它所匹配的value,时间复杂度接近为O(n^2^)哈希函数在Python中，哈希表的实现方法为字典（dict）,键(key)通过哈希函数得到一个哈希值，然后哈希值进行位运算（或者说是取模）运算得到一个下标，然后将value存入这个下标。从示意图来看，key与value并非线性关系，所以哈希表也叫散列哈希。补充说明：哈希函数不可逆，即不可以通过value反推出key。代码示意（简单演示，后面有优化版）：

import hashlibclass MyDict:    def __init__(self, length):        """        :param length: 空列表长度        """        self.hash_table_value = [None]*length  # 构建空列表用于储存哈希表的值        self.length = length        self.hash_table_key = []  # 构建空列表用于储存哈希表的键    def hash_convert(self, key):        """        此函数用于求哈希值并取余        :param key: 键值        """        h1 = hashlib.md5(key.encode()).hexdigest()  # 得到16进制的一堆数字        h2 = eval(str('0x') + str(h1))  # 16进制转10进制        remain = h2 % self.length  # 求余数        print('本次取模为', remain)        return remain    def insert(self, key, value):        """        用于插入新数据到哈希表        :param        """        index = self.hash_convert(key)        self.hash_table_value[index] = value  # 插入值到哈希表        self.hash_table_key.append(key)  # 这里用append添加，就不自己造轮子了        print(self.hash_table_value)    def get(self, key):        """        此方法用于根据key获取value        :param key:键        """        index = self.hash_convert(key)        if  key in self.hash_table_key:            return self.hash_table_value[index]        else:            return '没有找到你的key'my_dict = MyDict(4)my_dict.insert('wowo', 1)my_dict.insert('wx', 2)print('==' * 10)print('key:wowo的value为：', my_dict.get('wowo'))print('key:wx的value为：', my_dict.get('wx'))print('key:wxxg的value为：', my_dict.get('wxxg'))"""本次取模为 2[None, None, 1, None]本次取模为 3[None, None, 1, 2]====================本次取模为 2key:wowo的value为： 1本次取模为 3key:wx的value为： 2本次取模为 0key:wxxg的value为： 没有找到你的key"""

哈希冲突使用哈希运算然后取模时，可能会出现不同的key取模得到相同的余数，这样就会导致索引重复，也就是所谓的哈希冲突。解决方式有两种，一种是开放选址法，一种是链表法。开放寻址法如果出现哈希冲突，则后面的冲突的key所对应的索引往后移动，如果发现空位就占用。代码演示(下面还有一个Bug，待会再解决)

import hashlibclass MyDict:    def __init__(self, length):        """        :param length: 空列表长度        """        self.hash_table_key = [None] * length  # 构建空列表储存哈希表的键        self.hash_table_value = [None] * length  # 构建空列表用于储存哈希表的值        self.length = length    def hash_convert(self, key):        """        此函数用于求哈希值并取余        :param key: 键值        """        h1 = hashlib.md5(key.encode()).hexdigest()  # 得到16进制的一堆数字        h2 = eval(str('0x') + str(h1))  # 16进制转10进制        remain = h2 % self.length  # 求余数        return remain    def insert(self, key, value):        """        用于插入新数据到哈希表        :param        """        index = self.hash_convert(key)        print('本次取模为：', index)        # --开放寻址法插入--#        for i in range(index, len(self.hash_table_value)):            if self.hash_table_value[i] is None:                self.hash_table_value[i] = value  # 插入值到哈希表                self.hash_table_key[i] = key  # 为了方便后面寻址，这里也将key储存在相同位置                print('当前最新value表为：', self.hash_table_value)                print('当前最新key表为：', self.hash_table_key)                print('')                break  # 插入成功则退出循环        else:  # 遍历右边都没有空值，那只能放最后面了            raise Exception('由于哈希冲突以及右边空列表不够，本次插入失败，建议初始化时增加空列表数量')    def get(self, key):        """        此方法用于根据key的索引位置获取value        :param key:键        """        value_index = self.hash_convert(key)        for i in range(value_index, self.length):            if self.hash_table_key[i] == key:                return self.hash_table_value[i]        else:            return '没有找到你的key'my_dict = MyDict(5)my_dict.insert('wowo', 1)my_dict.insert('wx', 2)my_dict.insert('wxx', 3)print('==' * 10)print('key:wowo的value为：', my_dict.get('wowo'))print('key:wx的value为：', my_dict.get('wx'))print('key:wxx的value为：', my_dict.get('wxx'))print('key:wxxg的value为：', my_dict.get('wxxg'))"""本次取模为： 2当前最新value表为： [None, None, 1, None, None]当前最新key表为： [None, None, 'wowo', None, None]本次取模为： 2当前最新value表为： [None, None, 1, 2, None]当前最新key表为： [None, None, 'wowo', 'wx', None]本次取模为： 1当前最新value表为： [None, 3, 1, 2, None]当前最新key表为： [None, 'wxx', 'wowo', 'wx', None]====================key:wowo的value为： 1key:wx的value为： 2key:wxx的value为： 3key:wxxg的value为： 没有找到你的key"""

链表法如果出现哈希冲突，则前面先进入哈希表的元素，其key的指针指向后进入的元素。一般来说，Java使用链表法解决哈希冲突，python使用开放寻址法解决哈希冲突。有兴趣的可以试试使用链接表构建一个哈希表。从示意图来看，链表法更加灵活，不会存在空间不够的情况。开放寻址法如果空间不够了怎么办？其实可以通过扩容来解决。而且上面存在一个Bug,就是如果出现重复的key，那么似乎也能插入共存，没有去重与数据更新功能开放寻址最终版本代码演示

import hashlibclass MyDict:    def __init__(self, length):        """        :param length: 空列表长度        """        self.hash_table_key = [None] * length  # 构建空列表储存哈希表的键        self.hash_table_value = [None] * length  # 构建空列表用于储存哈希表的值        self.length = length    def hash_convert(self, key):        """        此函数用于求哈希值并取余        :param key: 键值        """        h1 = hashlib.md5(key.encode()).hexdigest()  # 得到16进制的一堆数字        h2 = eval(str('0x') + str(h1))  # 16进制转10进制        remain = h2 % self.length  # 求余数        return remain    def insert(self, key, value):        """        用于插入新数据到哈希表        :param        """        index = self.hash_convert(key)        print('本次取模为：', index, 'key为', key, '插入元素为', value)        # --开放寻址法插入--#        if key in self.hash_table_key:  # key需要去重，value需要更新            index2 = self.get(key)[1]  # 获取索引            self.hash_table_value[index2] = value  # 更新value            print('当前最新value表为：', self.hash_table_value)            print('当前最新key表为：', self.hash_table_key)            print('')            return None        for i in range(index, len(self.hash_table_value)):            if self.hash_table_value[i] is None:                self.hash_table_value[i] = value  # 插入值到哈希表                self.hash_table_key[i] = key  # 为了方便后面寻址，这里也将key储存在相同位置                print('当前最新value表为：', self.hash_table_value)                print('当前最新key表为：', self.hash_table_key)                print('')                break  # 插入成功则退出循环        else:  # 遍历右边都没有位置，需要扩容了            self.resize()            self.insert(key, value)  # 再插入一次    def resize(self):        """        哈希表自动扩容        """        self.length = self.length * 2  # 两倍扩容        hash_table_key_old = self.hash_table_key  # 临时储存老的key        hash_table_value_old = self.hash_table_value  # 临时储存老的value        self.hash_table_key = [None] * self.length        self.hash_table_value = [None] * self.length        for k, v in zip(hash_table_key_old, hash_table_value_old):            if k is not None:                self.insert(k, v)    def get(self, key):        """        此方法用于根据key的索引位置获取value        :param key:键        """        value_index = self.hash_convert(key)        for i in range(value_index, self.length):            if self.hash_table_key[i] == key:                return self.hash_table_value[i], i        else:            return '没有找到你的key', Nonemy_dict = MyDict(5)my_dict.insert('wowo', 1)my_dict.insert('wx', 2)my_dict.insert('wxx', 3)my_dict.insert('wx', 4)my_dict.insert('wxx', 5)my_dict.insert('wx1', 6)my_dict.insert('wxx2', 7)my_dict.insert('wxx3', 8)print('==' * 10)print('key:wowo的value为：', my_dict.get('wowo')[0])print('key:wx的value为：', my_dict.get('wx')[0])print('key:wxx的value为：', my_dict.get('wxx')[0])print('key:wxxg的value为：', my_dict.get('wxxg')[0])"""本次取模为： 2 key为 wowo 插入元素为 1当前最新value表为： [None, None, 1, None, None]当前最新key表为： [None, None, 'wowo', None, None]本次取模为： 2 key为 wx 插入元素为 2当前最新value表为： [None, None, 1, 2, None]当前最新key表为： [None, None, 'wowo', 'wx', None]本次取模为： 1 key为 wxx 插入元素为 3当前最新value表为： [None, 3, 1, 2, None]当前最新key表为： [None, 'wxx', 'wowo', 'wx', None]本次取模为： 2 key为 wx 插入元素为 4当前最新value表为： [None, 3, 1, 4, None]当前最新key表为： [None, 'wxx', 'wowo', 'wx', None]本次取模为： 1 key为 wxx 插入元素为 5当前最新value表为： [None, 5, 1, 4, None]当前最新key表为： [None, 'wxx', 'wowo', 'wx', None]本次取模为： 3 key为 wx1 插入元素为 6当前最新value表为： [None, 5, 1, 4, 6]当前最新key表为： [None, 'wxx', 'wowo', 'wx', 'wx1']本次取模为： 2 key为 wxx2 插入元素为 7本次取模为： 6 key为 wxx 插入元素为 5当前最新value表为： [None, None, None, None, None, None, 5, None, None, None]当前最新key表为： [None, None, None, None, None, None, 'wxx', None, None, None]本次取模为： 2 key为 wowo 插入元素为 1当前最新value表为： [None, None, 1, None, None, None, 5, None, None, None]当前最新key表为： [None, None, 'wowo', None, None, None, 'wxx', None, None, None]本次取模为： 7 key为 wx 插入元素为 4当前最新value表为： [None, None, 1, None, None, None, 5, 4, None, None]当前最新key表为： [None, None, 'wowo', None, None, None, 'wxx', 'wx', None, None]本次取模为： 3 key为 wx1 插入元素为 6当前最新value表为： [None, None, 1, 6, None, None, 5, 4, None, None]当前最新key表为： [None, None, 'wowo', 'wx1', None, None, 'wxx', 'wx', None, None]本次取模为： 7 key为 wxx2 插入元素为 7当前最新value表为： [None, None, 1, 6, None, None, 5, 4, 7, None]当前最新key表为： [None, None, 'wowo', 'wx1', None, None, 'wxx', 'wx', 'wxx2', None]本次取模为： 5 key为 wxx3 插入元素为 8当前最新value表为： [None, None, 1, 6, None, 8, 5, 4, 7, None]当前最新key表为： [None, None, 'wowo', 'wx1', None, 'wxx3', 'wxx', 'wx', 'wxx2', None]====================key:wowo的value为： 1key:wx的value为： 4key:wxx的value为： 5key:wxxg的value为： 没有找到你的key"""