应用类问题
2019-07-12 本文已影响0人
伊凡的一天
1. Hash算法
Hash函数是将输入键(key)转换为一个确定输出的函数。这个输出成为散列值。一个Hash函数拥有以下约束：
- 如果输出的散列值不同，那么输入key一定不同。
- 两个不同的key有可能输出的散列值相同，这被称为散列碰撞。
常见的Hash函数有MD5， SHA-1等。
一个完美的Hash函数，我们希望达到以下效果：
如果key1 != key2，那么hash (key1) != hash(key2)
然而在真实世界中，想要找到一个不同key对应不同散列值的Hash函数是不可能的。两个不同的key对应的散列值相同，这被称为散列碰撞或散列冲突。
常见的散列冲突解决方法有两种：开放寻址发和链表法。
比较经典的开放寻址法包括：线性探测法，二次探测法和双重检测法。
- 线性探测法：当计算出的hash值对应的散列表位置被占用时，自动寻找下一个位置，直到找到第一个未被占用的位置为止。
- 二次探测法：当计算出的hash值对应的散列表位置被占用时，不是直接一个一个往下遍历，而是按照二次幂的步长向下或向上探测。也就是说，它探测的下标序列为：hash(key)+0，hash(key)+1^2 或hash(key)-1^2 ，hash(key)+2^2 或 hash(key)-2^2
- 双重探测法：所谓双重散列，意思就是不仅要使用一个散列函数，而是使用一组散列函数 hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
事实上，不管采用哪种探测方法，只要当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，需要尽可能保证散列表中有一定比例的空闲槽位。一般使用加载因子（load factor）来表示空位的多少。加载因子是表示 Hsah 表中元素的填满的程度，若加载因子越大，则填满的元素越多,这样的好处是：空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了，但空间浪费多了。
load factor的应用可以参考Java中HashMap的实现，HashMap中load factor默认值为0.75。
而链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。在散列表中，每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中。这也是Java中HashMap的实现方式。
