LeetCode #1 Two Sum

var twoSum = function(numbers, target) {
        // 用对象来模拟hash table
        // 将所有数组放进hash里面,key为当前值,value为下标
        var hash = {};
        for(var i=0; i<numbers.length; i++) {
                hash[numbers[i]] = i;
        }
// 遍历数组,如果hash里面有key和数组当前的值相加为target,那么就是那两下标了
        // 注意要判断两下标不能一样
        for(var i=0; i<numbers.length; i++) {
                var needValue = target-numbers[i];
                if(hash.hasOwnProperty(needValue)) {
                        var index1 = i+1;
                        var index2 = hash[needValue]+1;
                        if(index1!==index2) {
                                return [index1, index2];
                        }
                }
        }
};

散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。 散列表是普通数组的推广,由于普通数组可以直接寻址,使得能在O(1)时间内访问数组中的任意位置。但是直接寻址的缺点也很明显,如果全域U很大,就要占用很大的内存空间。另外实际存储的关键字K相对U来说可能很小,使得分配给T的大部分空间都浪费掉了,而在这种情况下散列表需要的存储空间就要小很多。 hash-table-300x156.png 构造散列函数 散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快定位。 hash表的性能取决于两个因素:hash表的大小和解决冲突的方法。这两个是矛盾的:hash表大,则冲突少,但是用内存过大;而hash表小,则内存使用少,但冲突多,性能低。一个好的hash表会权衡这两个因素,使内存使用量和性能均尽可能低。

  1. 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即 hash(k)=k 或 hash(k)=a*k+b,其中k为常数(这种散列函数叫做自身函数,当全域U较小时,直接寻址是一种简单有效的方法)
  2. 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
  3. 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
  4. 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
  5. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=k mod p,p<=m。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生碰撞。
  6. MAD法:以素数为表长的除余法,在关键码空间到散列地址空间映射依然具有一定的连续性,为弥补之一不足,采用MAD法,将key映射为:(a*key+b) mod M,其中M仍为素数,a>0,b>0,a mod M!=0 一种常用高效的字符串Hash函数(BKDR hash) // BKDR Hash Function unsigned int BKDRHash(char *str){ unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); }

冲突的排解 然而无论散列函数设计的如何巧妙也不能保证不同的关键吗之间互不冲突。最直接的想法是把散列到一个槽中的元素都放在一个链表中,但是既然好的散列函数已经能够保证不会经常发生冲突,所以每个链表的规模都不大,而且大多数只包含单个词条,在查找过程中一旦发生冲突就要遍历整个列表,导致成本的增加。 其是,依靠散列表本身的结构就能有效地排解冲突,当新词条与现有词条冲突时,按一定规则在放后续的空桶中,当查找某个元素时需要系统地检索所有表项。因为散列地址对所有词条开放,所以这种方法成为开放定址法 1、开放定址法 之前已经提到过,开放定址法所有元素都保存在散列表中,所以散列表可能被填满,所以该方法装填因子不会大于1,一般取小于0.5。 Hi=( H(key)+di ) MOD m i=1,2,…,k(k<=m-1) 按照形成探查序列的方法不同,可将开放定址法区分为线性探查法(di =1,2,3,…,m-1)、(di =1^2,-1^2,…,±k^2 k<=m/2)、随机探测(di=伪随机序列),双重散列法(di=i*hash’ (key))。 线性探查比较容易实现,但是它存在一个问题,称为一次集群。随着连续被占用的槽不断增加,平均查找时间也不断增加。二次探查法中,试探位置将以线性速度增长,当发生冲突时试探位置会尽快跳离关键吗聚集区段。双重散列是用于开放寻址的最好方法之一,探查序列以两种不同的方式关联于k,因此初始探查位置、偏移量或者二者都有可能发生变化。为了能查找整个表,hash’ (key)必须与m互素,一般取m为2的幂,并设计一个总产生奇数的hash’ (key)。

各种字符串Hash函数比较

Licensed under CC BY-NC-SA 4.0