algorithmbook 散列

散列

Open RubyLouvre opened this issue 4 years ago • 0 comments

3.6 散列

散列又叫哈希表，其实是我们前端人最常用的结构了，因为javascript的对象就是一个散列。在实现链表，我们使用insertAt, 来指定数据放入某个位置上。但这个要遍历内部的结构，即便使用了双向链表，其查找速度还是无法与数组相比拟。但数组也有问题，它是查找容易，插入和删除困难；链表则是查找困难，插入和删除容易。

基于这原因，前辈们通过某种算法将关键字转换成数字，实现O(1)的插入删除与查找，综合上两者优点，这就是散列。

![[图片]][17]

下面是完整的定义

散列法存储的线性表被称为哈希表，使用的函数被称为散列函数或者哈希函数，f(k)被称为散列地址或者哈希地址。通常情况下，散列表的存储空间是一个一维数组，而其哈希地址为数组的下标。散列表中的一个位置称为槽（slot）。

我们的重点是设计哈希函数。

哈希函数的选择原则：

1：若哈希函数是一个一一对应的函数，则在查找时，只需要根据哈希函数对给定关键字的某种运算得到待查找结点的存储位置，无需进行比较

2：一般情况下，散列表的空间要比结点的集合大，虽然浪费了一部分空间但是却提高了查找的效率，散列表空间为m，填入表中结点数为n，则比值n/m成为哈希表的装填因子，一般取0.65~0.9之间

3：哈希函数应当尽量简单，其值域必须在表长的范围之内，尽量不要产生“冲突”(两个关键字得到相同的哈希地址)

以下有这几利方法：

直接地址法：以关键字的某个线性函数值为哈希地址，可以表示为hash(K)=aK+C;优点是不会产生冲突，缺点是空间复杂度可能会较高，适用于元素较少的情况

除留余数法：它是由数据元素关键字除以某个常数所留的余数为哈希地址，该方法计算简单，适用范围广，是经常使用的一种哈希函数，可以表示为：hash(K）=K mod C;

数字分析法：该方法是取数据元素关键字中某些取值较均匀的数字来作为哈希地址的方法，这样可以尽量避免冲突，但是该方法只适合于所有关键字已知的情况，对于想要设计出更加通用的哈希表并不适用

平方求和法：对当前字串转化为Unicode值，并求出这个值的平方，去平方值中间的几位为当前数字的hash值，具体取几位要取决于当前哈希表的大小。

分段求和法：根据当前哈希表的位数把所要插入的数值分成若干段，把若干段进行相加，舍去调最高位结果就是这个值的哈希值。

一个简单哈希函数不做冲突处理的哈希表实现

class Hash {
    constructor() {
        this.table = new Array(1000);
    }
    hash(data) {
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        }
        //把字符串转化为字符用来求和之后进行平方运算
        var s = total * total + ""
        //保留中间2位
        var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1
        console.log("Hash Value: " + data + " -> " + index);
        return index;
    }
    insert(key, data) {
        var index = this.hash(key);
        //把取中当做哈希表中索引
        var index = this.hash(key);
        //把取中当做哈希表中索引
        this.table[index] = {
            name: key,
            data: data
        };
    }
    get(key) {
        var index = this.hash(key);
        var node = this.table[index]
        return node && node.data;
    }
    forEach(cb) {
        for (var i = 0; i < this.table.length; i++) {
            var node = this.table[i]
            if (node) {
                cb(node.data, node.name);
            }
        }
    }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
    hash.insert(someNames[i], someNames[i]);
}

hash.forEach(function(el, i) {
    console.log(el, i)
})

![image_1cjipgpcls1r16re1v13mhp1pi96v.png-72.2kB][18]

哈希冲突的解决方案

在构造哈希表时，存在这样的问题：对于两个不同的关键字，通过我们的哈希函数计算哈希地址时却得到了相同的哈希地址，我们将这种现象称为哈希冲突

https://segmentfault.com/img/bV3f92?w=783&h=312![image_1cjin4ncud0q18p41vuc97m1ck165.png-165.5kB][19]

解决冲突的技术可以分为两类：开散列方法（open hashing）和闭散列方法（closed hashing，也称开地址方法，open addressing）开散列方法解决冲突是将冲突记录在表外，而闭散列方法是将冲突记录在表内的另一个位置上。

拉链法

开散列法最著名的实现是拉链法。它把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。我们在添加元素时，通过哈希函数计算出索引值，然后判定它是否为空，不为空则遍历链表是否已经保存相同的值。否则就创建一个新节点，插入到数组上，原链表则作为跟班挂在它的next属性中。删除时，为了方便，直接将链表的data属性置为null。 ![image_1dgecf55ga9m1b6t1lq1rrq12li3t.png-45.8kB][20]

class Node {
    constructor(name, data) {
        this.name = name;
        this.data = data;
        this.next = null
    }
}
class Hash {
    constructor() {
        this.table = [];
    }
    hash(key) {
        key += ""; //强制转字符串
        var HASHSIZE = 100
        var h = 0
        for (var i = 0; i < key.length; i++) {
            h = key.charCodeAt(i) + h * 31
        }
        //将整个字符串按照特定关系转化为一个整数，然后对hash长度取余
        return h % HASHSIZE;
    }
    loopup(key) {
        var hashvalue = this.hash(key);
        var node = this.table[hashvalue];
        while (node) {
            if (node.name == key + "") {
                return node
            }
            node = node.next
        }
    }
    get(key) {
        var node = this.loopup(key)
        return (node && node.data !== null) ? node.data : null;
    }
    remove(key) {
        var node = this.loopup(key);
        if (node) {
            node.data = null
        }
    }
    insert(key, data) {
        var hashvalue = this.hash(key);
        //头插法，不管该hash位置有没有其他结点，直接插入结点
        var node = this.table[hashvalue]
        var next = node;
        if (node) {
            do {
                if (node.name === key+"") {
                    node.data = value;
                    return //key,data一致
                }
            } while (node = node.next)
        }
        var np = new Node(key, data);
        this.table[hashvalue] = np;
        np.next = next;
    }
    forEach(cb) {
        for (var i = 0; i < 100; i++) {//HASHSIZE = 100
            if (this.table[i]) {
                var link = this.table[i]
                while (link) {
                    if (link.data !== null) {
                        cb(link.name, link.data)
                    }
                    link = link.next
                }
            }
        }
    }
}

var names = ["First Name", "Last Name", "address", "phone", "k101", "k110"];
var descs = ["Kobe", "Bryant", "USA", "26300788", "Value1", "Value2"];
var hash = new Hash()
for (var i = 0; i < 6; ++i) {
    hash.insert(names[i], descs[i]);
}
console.log("we should see ", hash.get("k110"));
hash.insert("phone", "9433120451"); //这里计算的hash是冲突的，为了测试冲突情况下的插入
console.log("we have ", hash.get("k101"), "and", hash.get("phone"));

![image_1cjjfbvl2qus19ea15jo199baid93.png-22kB][21]

闭散列方法可选择的方案则很多了，说明这个方向是对的，因此大家才集中精力研究这个。闭功列方法将所有记录都直接存储在散列表中，可以节约空间。

1、线性探测：当不同的key值通过哈希函数映射到同一散列地址上时，检测当前地址的下一个地址是否可以插入，如果可以的话，就存在当前位置的下一个地址，否则，继续向下一个地址寻找，地址++。

2、二次探测：是针对线性探测的一个改进，线性探测后插入的key值太集中，这样造成key值通过散列函数后还是无法正确的映射到地址上，太集中也会造成查找、删除时的效率低下。因此，通过二次探测的方法，取当前地址加上i^2，可以取到的新的地址就会稍微分散开。

如：此时的散列表长度为10： ![image_1cjjadth118fn191ackrje44147c.png-65.7kB][22]

从使用效果来看，线性探索不如二次索引，因此线性探索最后导致索引值都聚集在一起（这在数学上叫基本聚集primary clustering），数据量大了，测测次数会越来越多。

3、伪随机探查在伪随机探查中，探查序列中的第 i 个槽是 (h(k) + ri) mod M ，ri是 1 到 M-1 之间的数的随机序列。所有的插入和检索都使用相同的伪随机序列。

尽管二次探查和伪随机探查能够解决基本聚集问题，然而如果散列函数在某个基槽聚集，依然会保持聚集。这个问题称为二次聚集（secondary clustering）解决二次聚集问题可以使用双散列方法

双散列方法双散列方法的形式：

function hash1( key,  i){
    return i*hash2(key);
}

hash2 是第二个哈希函数。

好的双散列实现方法应当保证所有探查序列常数都与表 M 长度互素。其中一种方法是设置 M 为素数，而h2 返回 1<=h2<=M-1 之间的值。另外一种方法是给定一个 m 值，设置 M = 2m ，然后让 h2 返回 1 到 2m 之间的一个奇数值。

闭散列方法结论

每个新插入操作产生的额外查找代价将在散列表接近半满时急剧增加。如果还考虑到访问模式，在理想情况下，记录应当沿着探查序列按照访问频率排序。

//使用二次探索实现的散列 by 司徒正美
class Node {
    constructor(name, data) {
        this.name = name;
        this.data = data;
        this.next = null;
        this.state = true
    }
}
class Hash {
    constructor() {
        this.table = [];
        this.capacity = 100; //容量
        this.length = 0;
    }
    hash(s) {
        //更多常用的hash函数见
        // https://segmentfault.com/a/1190000013132249
        var seed = 131; // 31 131 1313 13131 131313 etc..
        var hash = 0;
        for (var i = 0; i < s.length; i++) {
            hash = s.charCodeAt(i) + hash * seed
        }
        return (hash & 0x7FFFFFFF);
    }
    getHash(key, capacity) {
        return this.hash(key + "") % capacity;
    }
    size() {
        return this.length;
    }
    insert(key, value) {
        var inserted = false
        var index = this.find(key, function(item) {
            item.data = value
            if (!item.state) {
                this.length++;
            }
            inserted = item.state = true;
        })
        if (!inserted) {
            this.table[index] = new Node(key, value)
            this.length++;
        }
        if (this.length * 10 / this.capacity > 6) {
            this.capacity *= 2
        }
        return true;
    }

    find(key, cb) {
        var index = this.getHash(key, this.capacity),
            i = 1,
            table = this.table
        while (table[index]) {
            if (table[index].name === key + "") {
                cb.call(this, table[index]);
            }
            index = index + 2 * i - 1;
            index %= this.capacity;
            i++;
        }
        return index
    }
    get(key) {
        var value = null
        this.find(key, function(item) {
            if (item.state) {
                value = item.data;
            }
        })
        return value
    }
    remove(key) {
        var oldSize = this.length;
        var index = this.find(key, function(item) {
            item.state = false;
            this.length--;
            if (this.length * 10 / this.capacity < 6) {
                this.capacity /= 2
            }
        })
        return this.length !== oldSize;
    }
    forEach(cb) {
        for (var i = 0, n = this.capacity; i < n; i++) {
            var el = this.table[i]
            if (el && el.state) {
                cb(el.name, el.data)
            }
        }
    }
}
var names = ["First Name", "Last Name", "address", "phone", "k101", "k110"];
var descs = ["Kobe", "Bryant", "USA", "26300788", "Value1", "Value2"];
var hash = new Hash()
for (var i = 0; i < 6; ++i) {
    hash.insert(names[i], descs[i]);
}
console.log("we should see ", hash.get("k110"));
hash.insert("phone", "9433120451"); //这里计算的hash是冲突的，为了测试冲突情况下的插入
console.log("we have ", hash.get("k101"), "and", hash.get("phone"));

hash.forEach(function(el, i) {
    console.log(el, i)
})

![image_1cjjf3ig91drttph1js81gt8eq889.png-22.3kB][23]

散列的应用

散列的应用还是蛮多，但通常我们不会使用Hash这样一个类，直接用空对象。javascript对象就是一个性能极佳的散列。

数组去重

如果数组都是字符串或都是数字，我们可以全部放进去，再for in出来就去重了。

var number = [2,3,4,2,5,6,4,88,1]
var hash = {}
number.forEach(function(el){
   hash["."+el] = el //前面加一点是保证它按添加时的顺序for in出来
})
var ret = []
Object.keys(hash).forEach(function(key){
  ret.push(hash[key])
})

只出现一次的数字

与上面差不多，不过每次放时记录次数，再for in出来时判定次数是否为1.

var number = [2,3,4,2,5,6,4,88,1]
var hash = {}
number.forEach(function(el){
   if(hash[el] ){
      hash[el].count ++
   }else{
      hash[el] = {
         count: 1,
         data: el
      }
   }
   
})
var ret = []
Object.keys(hash).forEach(function(key){
  if(hash[key].count === 1){
     ret.push(hash[key].data)
  }
})

两数之和

给定一个数字数组，找到两个数，使得他们的和为一个给定的数值target。这是leetcode非常著名的题目，如果用暴力法来找，性能很差，我们不妨一个查找，一边存储数据。找到就返回它们俩的索引值

function twoSum(numbers,  target) {
    var hash = new Hash() // 
    for(var i = 0; i < numbers.length; i++){
        var el = numbers[i]
       if(hash.get(el) !== null){
          var index = hash.get(el);
          return [index, i]
       }else{
          hash.insert(target - el, i);//target - el可能在后面找到
       }
    }
}
twoSum([5, 75,25], 100)// 1,2

有关散列的知识点是很多很碎的，都集中如何设计哈希函数与防冲突上，想进阶的同学可以访问如下网址继续学习。哈希是一种非常友好的结构，使用简单也不是面试重点。

https://www.zhihu.com/question/26762707

Feb 24 '20 16:02 RubyLouvre

algorithmbook algorithmbook copied to clipboard

散列

3.6 散列

algorithmbook
algorithmbook copied to clipboard