目录哈希表的结构特点面向对象方法封装哈希表哈希冲突构造函数基本单元:键值对主体:哈希表增加键值对获取键值删除键值对哈希表的结构特点 相比链表繁杂的遍历处理,哈希表的作用是存储无固定
相比链表繁杂的遍历处理,哈希表的作用是存储无固定顺序的键值对。哈希表的元素查找时间复杂度为O(1)。
尝试手动构建一个哈希表。过程如下:
function HashCode(str) { // 散列函数
let address = 0
for (let i = 0; i < str.length; i++) {
address += str.charCodeAt(i)
}
return address % 37 // 生成的哈希码
}
let table = {} // 哈希表
let keyValuePair = { key: "苹果手机", value: "4999元" } // 哈希表的基本单元: 键值对
table[HashCode(keyValuePair.key)] = keyValuePair // table添加对象,属性为哈希码,值为keyValuePair
console.log(table) // 输出哈希表: table { 28: { key: "苹果手机", value: "4999元" } }
我们需要清楚哈希表、键值对、哈希码和散列函数这四者的关系。过程分析如下:
第一步:创建哈希表table
、键值对keyValuePair
和散列函数HashCode
。
第二步:基于keyValuePair.key
即"苹果手机"这个字符串特征,通过散列函数生成哈希码HashCode(keyValuePair.key)
。
第三步:执行table[HashCode(keyValuePair.key)] = keyValuePair
。即在table
对象上新增一个HashCode(keyValuePair.key)
属性,而它的值就是键值对keyValuePair
。
总结:键值对中的key可通过散列函数生成哈希码,而生成的哈希码则作为哈希表的属性存储对应的键值对。
试着考虑以下这种情况,我们需要存储的键由相同字母构成,但字母的排序不同。
console.log(HashCode('Mike')) // 20
console.log(HashCode('Meki')) // 20
console.log(HashCode('keMi')) // 20
显然,相同字符构成但排序不同的字符串会生成相同的哈希码。即在哈希表中我们原来存储的键值对可能会因为哈希冲突而产生被覆盖的情况。有很多手段可以解决哈希冲突的问题。本文采取的是链地址方法。
class keyValuePair {
key: any
value: any
constructor(key: any, value: any) {
this.key = key
this.value = value
}
}
class HashTable {
length: number
table: { [index: number]: LinkedList }
constructor() {
this.length = 0
this.table = {}
}
}
增加键值对的情况分为两种。如下分析:
set(key: any, value: any): HashTable {
if (this.table[HashCode(key)] === undefined) {
this.table[HashCode(key)] = new LinkedList()
}
this.table[HashCode(key)].insert(new keyValuePair(key, value))
this.length++
return this
}
获取键值的情况分为三种。如下分析:
key
参数对应的键值返回,否则抛出错误。get(key: any): (void | any) {
if (this.isEmpty()) {
throw new Error(`HashTable is empty`)
} else if (this.table[HashCode(key)] === undefined) {
throw new Error(`${key} is not defined`)
} else {
let current: (null | LinkedListnode) = this.table[HashCode(key)].head
while (current !== null) {
if (key === current!.element!.key) {
return current!.element!.value
}
current = current!.next
}
if (!current) { throw new Error(`${key} does not exist`) }
}
}
删除键值对的情况分为三种。如下分析:
remove(key: any): HashTable {
if (this.isEmpty()) {
throw new Error(`HashTable is empty`)
} else if (this.table[HashCode(key)] === undefined) {
throw new Error(`${key} is not defined`)
} else if (this.table[HashCode(key)].length === 1) {
delete this.table[HashCode(key)]
} else if (this.table[HashCode(key)].length > 1) {
let current: (null | LinkedListNode) = this.table[HashCode(key)].head
for (let i = 0; i < this.table[HashCode(key)].length; i++) {
if (key === current!.element!.key) {
this.table[HashCode(key)].remove(i)
break
}
current = current!.next
}
if (!current) { throw new Error(`${key} does not exist`) }
}
this.length--
return this
}
本文相关代码已放置我的GitHub仓库 ?
以上就是数据结构typescript之哈希表实现详解的详细内容,更多关于Typescript数据结构哈希表的资料请关注编程网其它相关文章!
--结束END--
本文标题: 数据结构Typescript之哈希表实现详解
本文链接: https://www.lsjlt.com/news/178735.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-01-12
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0