本系列索引
哈希表原理
哈希表是一种能够快速索引到数据的数据结构，与此类似的是数组，和数组不同的是数组是通过数字下标来索引到数据，而哈希表可以通过任意数据结构来定位。
哈希表的原理如上图所示，本质上还是需要数组，但是我们可以通过设计哈希函数来将任意数据结构来映射成数组下标。
在学习哈希表时，我们的重点工作是设计一个合适的哈希函数。设计哈希函数有很多方法，并没有一个标准答案，不同场景有不同的最佳实践方式，但是还是有很多范式可以参考的，本文先不讨论这方面。(其实是我现在也没会多少 o(￣︶￣)o)
当然这种设计方式会出现一个问题，就是“哈希冲突”，所谓“哈希冲突”就是哈希函数将超过一个元素映射到同一个位置上，而对待哈希冲突的态度应该是怎么解决而不是避免。
解决哈希冲突方法主流的有以下几种：
- 开放定址法(线性探测)
- 再哈希法
当出现哈希冲突的时候那就再换个哈希函数再哈希一遍就好了，使用这种方法的时候可以多设置几个哈希函数。
但是还是要考虑最坏情况，就是经过所有的哈希方法之后还是会有冲突，所以还是要用其他哈希方法做兜底。 - 建立公共溢出区
公共溢出区可以用其他数据结构来维护 - 链式地址法(拉链法)
这个方法是最常用的，原理是在哈希表的基础上，数组存储的是链表
这里提供一种使用拉链法处理冲突的哈希表设计范式，有很多地方可以根据具体场景进行优化
class Node<T> {
val: T
next: Node<T> | null
constructor(val: T) {
this.val = val
this.next = null
}
//* 在当前节点后面插入一个节点
insert(node: Node<T>) {
node.next = this.next
this.next = node
}
}
class HashTable<T> {
cnt: number
data: Array<Node<T> | null>
constructor(n: number) {
this.data = (new Array(n) as any).fill(null)
this.cnt = 0
}
insert(s: T) {
let ind = this.hash_func(s) % this.data.length
const node = new Node(s)
this.cnt++
if (!this.data[ind]) {
this.data[ind] = node
return
}
let p = this.data[ind] as Node<T>
while (p.next && p.next.val !== s) p = p.next
if (p.next === null) { // 走到最后还没找到
p.insert(node)
if (this.cnt > this.data.length * 3) this.expand()
}
}
find (s: T) {
const ind = this.hash_func(s) % this.data.length
let p = this.data[ind]
while (p && p.val !== s) p = p.next
return p !== null
}
private expand() {
//* 开辟新的哈希表
const n = this.data.length * 2
const h = new HashTable<T>(n)
//* 数据迁移
let p: Node<T> | null
this.data.forEach(d => {
p = d
while (p) {
h.insert(p.val)
p = p.next
}
})
this.data = h.data
}
//* 计算哈希值
private hash_func(s: T): number {
let str = JSON.stringify(s), hash: number = 0, seed = 131
for (let i = 0; i < str.length; i++) {
hash = hash * seed + str[i].charCodeAt(0)
}
return hash & 0x7fffffff
}
}
//* 测试
const h = new HashTable<string>(5) // string -> number
h.insert('aaa')
h.insert('bbb')
h.insert('ccc')
h.insert('ddd')
h.insert('eee')
h.insert('fff')
h.insert('ggg')
console.log(h.data)
console.log(h.find('ggg'))
布隆过滤器
布隆过滤器原理和哈希表类似，但它主要是用来判定某数据是否不存在。
当一组哈希函数映射的位置都是1时，说明这个数据 可能 存在，但是但凡出现一个0就可以肯定这个数据 肯定 不存在。
哈希表题目
leetCode 705 设计哈希集合
class N<T> {
val: T | undefined
next: N<T> | null
constructor(val?: T) {
this.val = val
this.next = null
}
insert(node: N<T>) {
node.next = this.next
this.next = node
}
}
class MyHashSet {
data: Array<N<number>>
cnt: number
constructor(n?: number) {
const num = n || 100
this.data = new Array(num).fill(0).map(_ => new N())
this.cnt = 0
}
add(key: number): void {
const ind = this.hashFn(key)
const node = new N(key)
let p = this.data[ind]
while (p.next && p.next.val !== key) p = p.next
if (p.next === null) { // 重复的就不添加了
p.insert(node)
this.cnt++
if (this.cnt > this.data.length * 2) this.expand()
}
}
remove(key: number): void {
const ind = this.hashFn(key)
let p = this.data[ind]
while (p.next && p.next.val !== key) p = p.next
if (p.next?.val === key) {
const q = p.next
p.next = q.next
q.next = null
this.cnt--
}
}
contains(key: number): boolean {
const ind = this.hashFn(key)
let p = this.data[ind]
while (p.next && p.next.val !== key) p = p.next
return p.next?.val === key
}
private hashFn(key: number) {
const str = key.toString(), seed = 131
let hash = 0
for (let i = 0; i < str.length; i++) {
hash = hash * seed + str[i].charCodeAt(0)
}
return hash % this.data.length
}
private expand() {
const n = this.data.length * 2
const h = new MyHashSet(n)
this.data.forEach(d => {
while (d) {
if (d.val !== undefined) h.add(d.val)
if (d.next) d = d.next
else break
}
})
this.data = h.data
}
}
leetCode 706 设计哈希映射
type DataType = number[]
class N {
val: DataType | undefined
next: N | null
constructor(val?: DataType) {
this.val = val
this.next = null
}
insert(node: N) {
node.next = this.next
this.next = node
}
update(val: DataType) {
this.val = val
}
}
class MyHashMap {
data: Array<N>
cnt: number
constructor(n?: number) {
const num = n || 100
this.data = new Array(num).fill(null).map(_ => new N())
this.cnt = 0
}
put(key: number, value: number): void {
const ind = this.hashFn(key), node = new N([key, value])
let p = this.data[ind]
while (p.next && p.next.val![0] !== key) {
p = p.next
}
//* 以前没有，直接在链表后面新增
if (!p.next) {
p.insert(node)
this.cnt++
} else if (p.next.val![0] === key) {
//* 以前有的话就更新
p.next.update([key, value])
}
if (this.cnt > this.data.length * 2) this.expand()
}
get(key: number): number {
const ind = this.hashFn(key)
let p = this.data[ind]
while (p.next && p.next.val![0] !== key) p = p.next
if (p.next && p.next.val![0] === key) return p.next.val![1]
return -1
}
remove(key: number): void {
const ind = this.hashFn(key)
let p = this.data[ind]
while (p.next && p.next.val![0] !== key) p = p.next
if (p.next && p.next.val![0] === key) {
const q = p.next
p.next = q.next
q.next = null
this.cnt--
}
}
private hashFn(key: number) {
const s = key.toString(), seed = 131
let hash = 0
for (let i = 0; i < s.length; i++) {
hash = hash * seed + s[i].charCodeAt(0)
}
return hash % this.data.length
}
private expand() {
const n = this.data.length * 2
const h = new MyHashMap(n)
let p: N | null
this.data.forEach(d => {
p = d.next
while (p) {
h.put(p.val![0], p.val![1])
p = p.next
}
})
this.data = h.data
}
}
面试题16.25 LRU缓存
更新数据的排序，最好的数据结构是用链表，因为链表的插入、取出操作都相对方便。
所以要解这道题，可以将哈希表中映射到数组改成映射到链表，而为了能映射到链表上，需要用到 Map 来管理节点的映射。
为了更好地管理链表，可以设定虚拟头和虚拟尾，相关操作参考链表篇
class N {
key: number | null
val: number | null
next: N | null
pre: N | null
constructor(key: number | null, val: number | null) {
this.key = key
this.val = val
this.next = null
this.pre = null
}
insert(node: N) {
node.next = this.next
node.pre = this
this.next = node
if (node.next) {
node.next.pre = node
}
}
remove() {
if (this.pre) {
this.pre.next = this.next
}
if (this.next) {
this.next.pre = this.pre
}
this.next = null
this.pre = null
return this
}
}
class HashTable {
max: number
cnt: number
data: Map<number, N>
vh: N
vt: N
constructor(max: number) {
this.max = max
this.cnt = 0
this.data = new Map()
this.vh = new N(null, null)
this.vt = new N(null, null)
this.vh.next = this.vt
this.vt.pre = this.vh
}
put(key: number, val: number) {
//* 以前存在这个数据就更新它的值并移到最后一位
if (this.data.has(key)) {
const p = this.data.get(key) as N
p.val = val
p.remove()
this.vt.pre!.insert(p)
return
}
//* 新增数据 先在虚拟尾之前添加结点，再判断是否溢出
const node = new N(key, val)
this.vt.pre!.insert(node)
this.data.set(key, node)
this.cnt++
//* 溢出时进行删除操作
if (this.cnt > this.max && this.vh.next !== this.vt) {
const removedNode = this.vh.next!.remove()
this.data.delete(removedNode.key as number)
this.cnt--
}
}
get(key: number) {
//* 如果存在数据，则需要把该节点移动到链表的最后一位
if (this.data.has(key)) {
const p = this.data.get(key)
p!.remove()
this.vt.pre!.insert(p as N)
return this.data.get(key)!.val as number
}
return -1
}
}
class LRUCache {
h: HashTable
constructor(capacity: number) {
this.h = new HashTable(capacity)
}
get(key: number): number {
return this.h.get(key)
}
put(key: number, value: number): void {
this.h.put(key, value)
}
}
leetCode 535 TinyURL的加密与解密
function ch(x: number) {
x %= 62
if (x < 26) return String.fromCharCode(x + 'a'.charCodeAt(0))
if (x < 52) return String.fromCharCode(x - 26 + 'A'.charCodeAt(65));
return String.fromCharCode(x - 52 + '0'.charCodeAt(0))
}
function genRandString() {
let s = ''
for (let i = 0; i < 5; i++) s += ch(Math.floor(Math.random() * 1000))
return s
}
const dataMap = new Map<string, string>()
/**
* Encodes a URL to a shortened URL.
*/
function encode(longUrl: string): string {
let hashUrl = genRandString()
// 去重
while (dataMap.has(hashUrl)) hashUrl = genRandString()
dataMap.set(hashUrl, longUrl)
return `http://tinyurl.com/${hashUrl}`
}
/**
* Decodes a shortened URL to its original URL.
*/
function decode(shortUrl: string): string {
const key = shortUrl.slice(-5)
return dataMap.get(key) as string
}
leetCode 187 重复的DNA序列
这道题的解法可以参考哈希映射和数据存储的思想
function findRepeatedDnaSequences(s: string): string[] {
const res: string[] = [], dataMap = new Map<string, number>()
let str = '', val: number | undefined = 0
for (let start = 0, end = s.length - 10; start <= end; start++) {
str = s.substr(start, 10), val = dataMap.get(str)
dataMap.set(str, val ? val + 1 : 1)
}
dataMap.forEach((times, s) => {
if (times > 1) res.push(s)
})
return res
}
318 最大单词长度乘积
这道题可以借鉴布隆过滤器的设计思想，把每个单词映射成长度为26的向量，每个位置用1和0表示
function markStr(str: string) {
const a = 'a'.charCodeAt(0)
let res = 0
for (let i = 0; i < str.length; i++) {
res |= 1 << (str[i].charCodeAt(0) - a)
}
return res
}
function maxProduct(words: string[]): number {
let res = 0
const binaryMarks: number[] = []
words.forEach(word => binaryMarks.push(markStr(word)))
for (let i = 0; i < words.length; i++) {
for (let j = i + 1; j < words.length; j++) {
if (!(binaryMarks[i] & binaryMarks[j])) {
res = Math.max(res, words[i].length * words[j].length)
}
}
}
return res
}
o(￣︶￣)o