首先声明这仅作为我个人学习的记录,并无科普目的
如有想要继续了解相关内容可以私信
内容来源:linked_hashmap 底层实现大作业
关于List.hpp 可参考标准库,此处使用的是自主底层实现的list.hpp
hashmap功能及使用介绍:
和map相似,是用于存储数据并通过键值查询相关信息(例如是会否出现过或者与键值KEY关联的OTHER信息)
后续可以自己试着使用这个自己实现的库!
区别:hashmap实现了平均复杂度O(1)的所有操作,包括插入,删除,查询,查询是否存在等等功能
而map 底层由红黑树构成,O(logn) 的平均复杂度。
具体内容:
内嵌类:节点类Node 拉链所需类 BucketList 继承的iterator const_iterator 迭代器类
基本原理:开一个二级指针,经过哈希后实现数组+链表头式数据的存储
关于附加功能的阐述:关于为什么叫linked_hashmap 是因为它借用了list.hpp建立起哈希表并实现其基本功能,同时,借用list.hpp是为了实现对加入元素实现顺序遍历等操作,功能几乎独立于哈希表的功能,但共用空间。
具体代码图片:
类模板的初步建立
节点类
拉链所需类
BucketList 类内工具函数
resize()代码部分!遍历内容即可
注意内存泄漏问题
工具函数copy()
public函数部分,对外接口。
at and [] 重载
clear()
insert () and erase() :
count () ;查询KEY 值在哈希表中的存在情况
find() :
相信看到这里的人不多,因为没有背景语境,这些代码可能比较枯燥,不过没关系,只是我的一个记录而已。
如有建议,欢迎交流!
编辑用时 20min
2022.5.7
13.00



