Python 数据结构之哈希表的实现

哈希表（Hash table，也叫作散列表），是根据关键码值(Key value)而直接进行访问的数据结构。

• 也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
• 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
• 使用哈希表可以进行非常快速的查找操作，查找时间为常数，同时不需要元素排列有序
• 在Python中 字典(dictionary)、集合(set)、计数器(counter)、默认字典Defaut dict)、有序字典(Order dict)等都是使用哈希表实现的

# 哈希表基于Python语言的简单实现 ''' 哈希表需要实现的方法： add(key,value)  增加元素 search(key)  查找元素 travel() 遍历整个哈希表 '''  class HashTable(object):     """     哈希表类     """     def __init__(self):         """         初始化         """         self.__key_llist = []         self.__val_list = []      def add(self, key, val):         """         添加元素         """         self.__key_llist.append(key)         self.__val_list.append(val)      def get(self, key):         """         搜索元素         """         return self.__val_list[self.__key_llist.index(key)] if key in self.__key_llist else None      def travel(self):         """         遍历哈希表         """         for index in range(0, len(self.__key_llist)):             print(self.__val_list[index])   if __name__ == "__main__":     ht = HashTable()     ht.add('asd', 123)     ht.add('qwe', 456)     ht.add('zxc', 789)     print(ht.get('asd'))     print(ht.get('wer'))     ht.travel()