Yinde's Blog

Talk is cheap. Show me the code.

目录
哈希表的实现
/      

哈希表的实现

哈希表

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

哈希表的最大特性就是能使用O(1)的时间访问一个键值对。哈希表技术的重点有两点获取Key的Hash值解决冲突

获取HASH

哈希函数可以被认为是一种纯函数,接收一个字符串,返回一个Int数。字符串参数相同,返回的Int值必定相同,我这里就介绍一种名为BKDR的实现,我这里做了一些改装,这里要注意,一个Hash函数的性能是直接影响整个Hash表的性能的。

/**
 * 
 * @description 获取一个字符串对应的HashCode
 * @param {String} str 要转换的字符串
 * @returns {Number} 映射出来的整数
 * 要不是JS新增了BigInt 随便算算就超出最大IFEE754的极限了
 */
function getHash(str) {
	str = str.split('')
	let seed = BigInt(133),
		hash = BigInt(0)
	while (str.length > 0) {
		let charCode = BigInt(str[0].charCodeAt(0))
		str.shift()
		hash = BigInt(hash * seed + charCode)
	}
	return hash & BigInt(0x7fffffff)
}

一旦获取到Hash值,我们就能通过取模运算直接获取到最终的index值

// 获取index
let hash = getHash('imkey')
// 无论是Set过程中 还是Get过程中 都需要进行Index的计算
// 这个Index就代表了当前键值对象存储在表中的下标
let index = hash % table.length

解决冲突

事实上,没有一个Hash函数的实现能够彻底避免不同的Key最终生成相同的Hash,简单来讲就是会出现两个Key被映射到同一个槽位的情况。

常见的的解决方式有

  • 链接法 每个坑位里面放置一个链表 一个坑位就能放多个值
  • 开放地址法 含有多个变种,但核心思想是通过某种规则 尽可能的填向其他表格 比如向下一个个检测
  • 再散列 设立一个Hash函数的池 如果发生冲突 按序调用 直到Hash出来的Index坑位为空为止

这里我选择了链接法,直接上完整版的实现。

Code

/**
 * 
 * @description 获取一个字符串对应的HashCode
 * @param {String} str 要转换的字符串
 * @returns {Number} 映射出来的整数
 * 要不是JS新增了BigInt 随便算算就超出最大IFEE754的极限了
 */
function getHash(str) {
	str = str.split('')
	let seed = BigInt(133),
		hash = BigInt(0)
	while (str.length > 0) {
		let charCode = BigInt(str[0].charCodeAt(0))
		str.shift()
		hash = BigInt(hash * seed + charCode)
	}
	return hash & BigInt(0x7fffffff)
}

class HashTable {
	constructor() {
		// 初始表的大小设置为50 具体值要根据情况
		this.table = new Array(50).fill(null)
		// 表中元素个数
		this.tableNum = 0
		// 表的大小
		this.tableLen = 50
	}
	set(key, val) {
		// 装载因子过大 需要执行换表
		if (this._factor > 2) {
			this._moveNewTable()
		}
		let index = this._getIndex(key)
		let ele = this.table[index]
		// 空槽
		if (!ele) {
			this.table[index] = {
				prev: null,
				next: null,
				key,
				val
			}
			this.tableNum++
		} else {
			// 检查是否重复 重复直接覆盖值即可
			let node = this._find(ele, key)
			if (node) {
				node.val = val
				return
			}
			this.table[index] = {
				prev: null,
				next: ele,
				key,
				val
			}
			ele.prev = this.table[index]
			this.tableNum++
		}
	}
	get(key) {
		let index = this._getIndex(key)
		let node = this._find(this.table[index], key)
		if (node) {
			return node.val
		} else {
			return null
		}
	}
	// 删除元素
	del(key) {
		let index = this._getIndex(key)
		let node = this._find(this.table[index], key)
		if (node) {
			if (node.prev) {
				node.prev.next = node.next
			}
			if (node.next) {
				node.next.prev = node.prev
			}
			this.tableNum--
		}
	}
	// 搜寻目标 返回node引用 未找到返回Null
	_find(node, key) {
		while (node) {
			if (node.key === key) {
				return node
			}
			node = node.next
		}
		return null
	}
	_getIndex(key) {
		return Number(getHash(key) % BigInt(this.tableLen))
	}
	// 装载因子
	get _factor() {
		return this.tableNum / this.tableLen
	}
	// 进行表的扩增
	_moveNewTable() {
		let nTable = new Array(this.tableLen * 2).fill(null)
		let len = this.tableLen
		for (let i = 0; i < len; i++) {
			nTable[i] = this.table[i]
		}
		this.table = nTable
		this.tableLen = this.tableLen * 2
	}
}

const table = new HashTable()

table.set('name', 'Jack')
table.set('name', 'TOM')

for (let i = 0; i < 100; i++) {
	table.set('KEY' + i + Math.random(), i)
}

总结

哈希表是一种完美利用数组的线性内存,直接通过偏移访问的特性,再加上Hash函数的隐射,来做到KeyVal的O(1)访问的技术。

在很多语言内部都有直接的实现,但是理解其原理依旧非常重要


标题:哈希表的实现
作者:zhangzhengyi12
地址:https://blog.yinode.tech/articles/2019/04/21/1567739698258.html

评论