有时候,一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候,称其为冲突。
举个例子来看,见如下代码。其中,HashTable类的创建见博客 学习JavaScript数据结构与算法(七)——散列表(一) 。
var hash = new HashTable(); hash.put('Jack', 'jack@email.com'); hash.put('John', 'john@email.com'); hash.put('Ben', 'ben@email.com'); hash.put('Jim', 'jim@email.com'); hash.put('Tyrion', 'tyrion@email.com'); hash.put('Aaron' ,'aaron@email.com'); hash.put('Jonathan', 'jonathan@eamil.com'); hash.put('Jamie', 'jamie@email.com'); hash.put('Sue', 'sue@eamil.com'); console.log('-------'); hash.print();处理冲突的方法有:分离链接、线性探查和双散列法。
为散列表的每一个位置创建一个链表并将元素存储在里面。 可以这么简单地理解,一个年级在操场集合,操场上划分不同的区域,每个班占一个区域(位置),而一个班级里人依次排列,就好比是一个链表。
它是解决冲突的最简单的方法,但是它在HashTable实例之外还需要额外的存储空间。
function HashTableSeparateChaining () { var table = []; var loseloseHashCode = function(key){ var hash = 0; for (var i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % 37; }; /* ValuePair 辅助类,表示将要加入LinkedList实例的元素。 只会将key和value存储在一个Object实例中。 */ var ValuePair = function(key, value){ this.key = key; this.value = value; this.toString = function(){ return '[' + this.key + ' - ' + this.value + ']'; } }; /*重写put()、get()、remove()方法*/ this.put = function(key, value){ var position = loseloseHashCode(key); /* 验证要加入新元素的位置是否已经被占据。 如果这个位置是第一次被加入元素,则在这个位置初始化一个LinkedList实例。 */ if (table[position] == undefined) { table[position] = new LinkedList(); } table[position].append(new ValuePair(key,value)); }; this.get = function(key){ var position = loseloseHashCode(key); //确定在特定的位置上是否有元素存在 if (table[position] !== undefined) { var current = table[position].getHead();//遍历之前先获取链表表头的引用 //遍历链表来寻找键/值(从头到尾) while (current.next) { if (current.element.key === key) { return current.element.value; } current = current.next; } //检查元素在链表第一个或最后一个节点的情况 if (current.element.key === key) { return current.element.value; } } return undefined; }; this.remove = function(key){ var position = loseloseHashCode(key); if (table[position] !== undefined) { var current = table[position].getHead(); while (current.next) { if (current.element.key === key) { table[position].remove(current.element); //如果链表为空了,就将散列表这个位置的值设为undefined。 if (table[position].isEmpty()) { table[position] = undefined; } return true; } current = current.next; } //检查是否为第一个或最后一个元素 if (current.element.key === key) { table[position].remove(current.element); if (table[position].isEmpty()) { table[position] = undefined; } return true; } } return false; }; this.print = function() { for (var i = 0; i < table.length; ++i) { if (table[i] !== undefined) { console.log(i + ": " + table[i].toString()); } } }; }测试代码:
var hash = new HashTableSeparateChaining(); hash.put('Jack', 'jack@email.com'); hash.put('John', 'john@email.com'); hash.put('Ben', 'ben@email.com'); hash.put('Jim', 'jim@email.com'); hash.put('Tyrion', 'tyrion@email.com'); hash.put('Aaron' ,'aaron@email.com'); hash.put('Jonathan', 'jonathan@eamil.com'); hash.put('Jamie', 'jamie@email.com'); hash.put('Sue', 'sue@eamil.com'); hash.print(); console.log('-------'); console.log(hash.get('Jack')); console.log('-------'); hash.remove('John'); hash.print();测试结果如下:
当想向表中某个位置加入一个新元素的时候,如果索引为index的位置已经被占据了,就尝试index+1的位置。如果index+1的位置也被占据了,就尝试index—+2的位置。以此类推。
function HashTableLinearProbing () { var table = []; var loseloseHashCode = function(key){ var hash = 0; for (var i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % 37; }; var ValuePair = function(key, value){ this.key = key; this.value = value; this.toString = function(){ return '[' + this.key + ' - ' + this.value + ']'; } }; this.put = function(key,value){ var position = loseloseHashCode(key); if (table[position] == undefined) { table[position] = new ValuePair(key,value); } else { var index = ++position; while (table[index] != undefined) { index++; } table[index] = new ValuePair(key,value); } }; this.get = function(key){ var position = loseloseHashCode(key); if (table[position] !== undefined) { if (table[position].key === key) { return table[position].value; } else { var index = ++position; while (table[index] === undefined || table[index].key != key) { index++; } if (table[index].key === key) { return table[index].value; } } } return undefined; }; this.remove = function(key){ var position = loseloseHashCode(key); if (table[position] !== undefined) { if (table[position].key === key) { table[position] = undefined; } else { var index = ++position; while (table[index] === undefined || table[index].key != key) { index++; } if (table[index].key === key) { table[index] = undefined; } } } return undefined; }; this.print = function() { for (var i = 0; i < table.length; ++i) { if (table[i] !== undefined) { console.log(i + ": " + table[i].toString()); } } }; }测试代码:
var hash = new HashTableLinearProbing(); hash.put('Jack', 'jack@email.com'); hash.put('John', 'john@email.com'); hash.put('Ben', 'ben@email.com'); hash.put('Jim', 'jim@email.com'); hash.put('Tyrion', 'tyrion@email.com'); hash.put('Aaron' ,'aaron@email.com'); hash.put('Jonathan', 'jonathan@eamil.com'); hash.put('Jamie', 'jamie@email.com'); hash.put('Sue', 'sue@eamil.com'); hash.print(); console.log('-------'); console.log(hash.get('Jack')); console.log('-------'); hash.remove('John'); hash.print();测试结果如下:
3、双散列法
事先准备多个散列函数。每当发生散列地址冲突时,就换一个散列函数计算,直到把冲突解决。 这种方法使得关键字不产生聚集,也增加了计算的时间。
在上面实现的“lose lose”散列函数不是一个表现良好的散列函数,因为它会产生很多的冲突。
一个表现良好的散列函数由以下几个方面构成: 插入和检索元素的时间(即性能),较低的冲突可能性。
下面来创建一个更好的散列函数djb2:
var djb2HashCode = function(key){ //初始化一个hash变量并赋为一个质数 var hash = 5381;//大多实现使用5381 //迭代参数key for (var i = 0; i < key.length; i++) { //将hash与33相乘(用来当作一个魔力数),并和当前迭代到的字符的ASCII码值相加 hash = hash *33 + key.charCodeAt(i); } //使用相加的和与另一个随机质数相除的余数 //随机质数比我们认为的散列表的大小要大 //本例中,我们认为散列表大小为1000 return hash % 1013; };用之前冲突的那个例子做测试,会发现输出的结果显示没有冲突。
这并不是最好的散列函数,但这是最被社区推荐的散列函数之一。