Python全系列 教程
3567个小节阅读:5930.2k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
xxxxxxxxxx
class Pair:
def __init__(self,key,val):
self.key = key
self.val = val
class MyHashMap:
def __init__(self):
self.size = 0 # 键值对的数量
self.capacity = 8 # 哈希表的容量
self.load_thres = 2.0/3.0 # 触发扩容的负载因子阈值
self.extend_ratio = 2 # 扩容倍数
self.data = [[] for i in range(self.capacity)] # 数组
def hash_func(self,key)->int:
'''哈希函数'''
return hash(key) % self.capacity
def load_factor(self):
'''负载因子'''
return self.size/self.capacity
def put(self,key,val):
'''添加数据'''
# 判断是否需要扩容
if self.load_factor() > self.load_thres:
# 扩容
pass
# 获取key对应的索引
index = self.hash_func(key)
# 获取对应所有的列表
tmp_list = self.data[index]
# 遍历当前索引下的列表
for i in tmp_list:
# 看列表中是否有当前的key
if i.key==key:
# 如果有替换对应的值
i.val = val
return
# 如果没有增加的key和value到列表
pair = Pair(key,val)
tmp_list.append(pair)
# size +1
self.size += 1
def get(self,key):
'''获取数据'''
# 获取key对应的索引
index = self.hash_func(key)
# 获取对应所有的列表
for i in self.data[index]:
if i.key == key:
return i.val
# 如果没有找到返回None
return None
def remove(self,key):
'''删除数据key'''
# 获取key对应的索引
index = self.hash_func(key)
# 获取对应所有的列表
tmp_list = self.data[index]
# 获取对应所有的列表
for i in tmp_list:
# 如果找到对应key
if i.key == key:
# 删除对应的key和value
tmp_list.remove(i)
# size -1
self.size -= 1
break
def extend(self):
''' 扩容'''
# 保存现有的数据
tmp_list = self.data
# 获取新的容量
self.capacity *= self.extend_ratio
# 创建新的数组
self.data = [[] for i in range(self.capacity)]
# 将数据添加到新的数组中
# 获取每个列表
for tmp in tmp_list:
# 获取列表中的每个元素
for i in tmp:
# 将元素添加到新的数组中
self.put(i.key,i.val)
def print(self):
'''打印所有的key和value'''
# 获取每个列表
for tmp in self.data:
# 获取列表中的每个元素
for i in tmp:
print(f'{i.key}=>{i.val}',end=' ')
print()
if __name__ =='__main__':
my_map = MyHashMap()
my_map.put('a',1)
my_map.put('b',2)
my_map.put('c',3)
my_map.put('bai','百')
my_map.put('zhan','站')
my_map.put('cheng','程')
my_map.put('xu','序')
my_map.put('yuan','员')
my_map.print()