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

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

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

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

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

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

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

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

class Node {
    val: T
    next: Node | null
    constructor(val: T) {
        this.val = val
        this.next = null
    }

    /
function encode(longUrl: string): string {
    let hashUrl = genRandString()
    // 去重
    while (dataMap.has(hashUrl)) hashUrl = genRandString()
    dataMap.set(hashUrl, longUrl)
    return `http://tinyurl.com/${hashUrl}`
}


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