哈希表(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()