算法随笔 — 搜索查找算法 — 哈希表

刺骨的言语ヽ痛彻心扉 2022-08-28 07:42 189阅读 0赞

## 哈希表原理 ##

哈希表是一种能够快速索引到数据的数据结构，与此类似的是数组，和数组不同的是数组是通过数字下标来索引到数据，而哈希表可以通过任意数据结构来定位。

![哈希表原理][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]  
哈希表的原理如上图所示，本质上还是需要数组，但是我们可以通过设计哈希函数来将任意数据结构来映射成数组下标。

在学习哈希表时，我们的重点工作是设计一个合适的哈希函数。设计哈希函数有很多方法，并没有一个标准答案，不同场景有不同的最佳实践方式，但是还是有很多范式可以参考的，本文先不讨论这方面。(其实是我现在也没会多少 o(*￣︶￣*)o)

当然这种设计方式会出现一个问题，就是“哈希冲突”，所谓“哈希冲突”就是哈希函数将超过一个元素映射到同一个位置上，而对待哈希冲突的态度应该是怎么解决而不是避免。

解决哈希冲突方法主流的有以下几种：

1.  开放定址法(线性探测)  
    ![开放定址法][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 1]
2.  再哈希法  
    当出现哈希冲突的时候那就再换个哈希函数再哈希一遍就好了，使用这种方法的时候可以多设置几个哈希函数。  
    但是还是要考虑最坏情况，就是经过所有的哈希方法之后还是会有冲突，所以还是要用其他哈希方法做兜底。
3.  建立公共溢出区  
    ![建立公共溢出区][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
    公共溢出区可以用其他数据结构来维护
4.  链式地址法(拉链法)  
    这个方法是最常用的，原理是在哈希表的基础上，数组存储的是链表  
    ![拉链法][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 3]

这里提供一种使用拉链法处理冲突的哈希表设计范式，有很多地方可以根据具体场景进行优化

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'))

> **布隆过滤器**

布隆过滤器原理和哈希表类似，但它主要是用来判定某数据是否不存在。

![布隆过滤器][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
当一组哈希函数映射的位置都是1时，说明这个数据 **可能** 存在，但是但凡出现一个0就可以肯定这个数据 **肯定** 不存在。

--------------------

## 哈希表题目 ##

> ### leetCode 705 设计哈希集合 ###

![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
        }
    }

![705结果][705 1]

> ### leetCode 706 设计哈希映射 ###

![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
        }
    }

![706结果][706 1]

> ### 面试题16.25 LRU缓存 ###

![16.25题目][16.25]  
更新数据的排序，最好的数据结构是用链表，因为链表的插入、取出操作都相对方便。

所以要解这道题，可以将哈希表中映射到数组改成映射到链表，而为了能映射到链表上，需要用到 Map 来管理节点的映射。

为了更好地管理链表，可以设定虚拟头和虚拟尾，相关操作参考[链表篇][Link 1]

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)
        }
    }

![16.25结果][16.25 1]

> ### leetCode 535 TinyURL的加密与解密 ###

![535题目][535]

![535结果][535 1]

> ### leetCode 187 重复的DNA序列 ###

![187][]  
这道题的解法可以参考哈希映射和数据存储的思想

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
    }

![187结果][187 1]

> ### 318 最大单词长度乘积 ###

![318][]  
这道题可以借鉴布隆过滤器的设计思想，把每个单词映射成长度为26的向量，每个位置用1和0表示

![318结果][318 1]

--------------------

o(*￣︶￣*)o

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3cc044f215a344af9114ffaa2eef49d2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/334a18d696a241bf962bdf6b0da88202.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/98733dd8a6144e1db8e9a7bce8c5bd6d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/7d6b282e55724509abcd26eddd264b8d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/326911a7aec34c34b55590c5bfc7c8c4.png
[705]: /images/20220828/d9492280c5cd400896ab049161ce55b8.png
[705 1]: /images/20220828/e0ba6daa1ccc470c8231e8cced353395.png
[706]: /images/20220828/a5e3931f85ba4d079e63138f03e9772b.png
[706 1]: /images/20220828/d6fb97fc0e6d4340a3c04a8fd68a85b2.png
[16.25]: https://img-blog.csdnimg.cn/5f20e84cea4f44348c760887ba3328aa.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://blog.csdn.net/TM_Godspeed/article/details/114497771
[16.25 1]: https://img-blog.csdnimg.cn/cbd99a3bbc5b475480aa9f9ba14eab6c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[535]: https://img-blog.csdnimg.cn/ba0ee3497afe49dd800f668d81de6c65.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[535 1]: https://img-blog.csdnimg.cn/9349454193774290ab82cba5e45c4884.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[187]: https://img-blog.csdnimg.cn/da1c90291e394cce8f25f29bd1009ce5.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[187 1]: https://img-blog.csdnimg.cn/58611c19c2b245a59afc58c74e876724.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[318]: https://img-blog.csdnimg.cn/e2064aeb27a440539b7b0c99e4edd8db.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[318 1]: https://img-blog.csdnimg.cn/bcc639402dd845c2b7fe1900a550e484.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qmZ5qmZ5a2Q5aSn5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16