简单算法——哈希

哈希
哈希（Hash）也称为散列，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。


哈希表
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。


使用Hash的查询算法分为两步：
① 用Hash函数将被查找的键转化为数组的一个索引。
理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。
② 处理碰撞冲突的过程


hash算法有很多，这里不再列举。下面是一个简单的例子，使用的就是哈希


题目： 做加法。
给定N个整数，找出有多少对的和为100.
输入示例： ['5','1 99 98 2 2']
限制内存：100M， 限制时间：1000ms


let inputArray = ['5','1 99 98 2 2'] //测试输入
console.log(add(inputArray))

function add(inputArray){
    inputArray = inputArray[1].split(" ").map(Number)
    let hashMap = new Map()
    let count = 0
    inputArray.forEach(item => {
        if (hashMap.get(100 - item)) {
            count += hashMap.get(100 - item)
        }
        let val = hashMap.get(item) ? hashMap.get(item) + 1 : 1;
        hashMap.set(item,val)
    })
    return count
}

注：有多种方法，比如二分查找也可以求解。 不过新手容易暴力求解（直接双重for循环），妥妥的超时