Author | 王平安 |
---|---|
pingan8787@qq.com | |
博 客 | www.pingan8787.com |
微 信 | pingan8787 |
每日文章推荐 | https://github.com/pingan8787/Leo_Reading/issues |
微信公众号 | 前端自习课 |
这是第五周的练习题,上周忘记发啦,这周是复习 Dictionary 和 HashTable。
下面是之前分享的链接:
本周练习内容:数据结构与算法 —— Dictionary 和 HashTable
这些都是数据结构与算法,一部分方法是团队其他成员实现的,一部分我自己做的,有什么其他实现方法或错误,欢迎各位大佬指点,感谢。
一、字典和散列表的概念
字典是什么?
字典和集合有什么异同?
什么是散列表和散列函数?
散列表的特点是什么?
解析:
- 字典是什么?
字典是一种以 键-值对 形式存储数据的数据格式,其中键名用来查询特定元素。
- 字典和集合有什么异同?
相同:都是用来存储不同元素的数据格式;
区别:集合是以 值-值 的数据格式存储,而字典是以 键-值 的数据格式存储。
- 什么是散列表和散列函数?
哈希表(Hash table
,也叫散列表),是根据关键码值(·Key value·)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
- 散列表的特点是什么?
特点:数组和链接优点的结合,查询速度非常的快,几乎是O(1)的时间复杂度,并且插入和删除也容易。
二、请实现一个字典
set(key,value)
:向字典中添加新元素。delete(key)
:通过使用键值从字典中移除键值对应的值。has(key)
:如果某个键值存在于这个字典中,则返回 true,否则返回 false。get(key)
:使用键值查找对应的值并返回。clear()
:删除字典中的所有元素。size()
:返回字典包含的元素数量,与数组的 length 属性类似。keys()
:将字典的所有键名以数组的形式返回。values()
:将字典包含的所有数值以数组形式返回。
使用示例:
1 | let dictionary = new Dictionary(); |
提示:Web 端优先使用 ES6 以上的语法实现。
解析:
1 | // 二、请实现一个字典 |
三、请实现一个散列表
put(key,value)
:向散列表增加/更新一个新的项。remove(key)
:根据键值从散列表中移除值。get(key)
:根据键值检索到特定的值。print()
:打印散列表中已保存的值。
散列表内部的散列算法:
1 | function hashCode(key) { |
使用示例:
1 | const hashTable = new HashTable(); |
解析:
1 | // 三、请实现一个散列表 |
四、请利用之前已实现的链表,实现一个分离链接的散列表
分离链接是为散列表的每一个位置创建一个链表储存元素的方式来处理散列表中的冲突:
请实现新的散列表方法:
put(key,value)
:将 key 和
value存在一个
ValuePair对象中(即可定义一个包含
key和
value属性的
ValuePair` 类),并将其加入对应位置的链表中。
get(key)
:返回键值对应的值,没有则返回 undefined
。
remove(key)
:从散列表中移除键值对应的元素。
print()
:打印散列表中已保存的值。
提示:先找到元素储存位置所对应的链表,再找到对应的值。
1 | const hashTable = new HashTable(); |
解析:
1 | // 链表的实现代码省略 可以查看之前的代码 |
五、实现一个线性探查的散列表
线性探查是解决散列表中冲突的另一种方法,当向表中某一个位置加入新元素的时候,如果索引为 index
的位置已经被占据了,就尝试 index+1
的位置。如果 index+1
的位置也被占据,就尝试 index+2
,以此类推。
请实现散列表:
put(key,value)
:将 key
和 value
存在一个 ValuePair
对象中(即可定义一个包含 key
和 value
属性的 ValuePair
类)并分配到散列表。
get(key)
:返回键值对应的值,没有则返回 undefined
。
remove(key)
:从散列表中移除键值对应的元素。
提示:移除一个元素,只需要将其赋值为 undefined。
使用示例:
1 | const hashTable = new HashTable(); |
解析:
1 | let ValuePair = function (key, value){ |
下周预告
下周将练习 Tree 的题目。