ECMAScript前端学数据结构之字典和散列表

散列表

  上面将详细介绍HashTable类,也叫HashMap类,是Dictionary类的一种散列表实现情势

  散列算法的效果是尽可能快地在数据结构中找到一个值。假如要在数据结构中拿走一个值(使用get方法),需要遍历整个数据结构来找到它。倘诺使用散列函数,就知道值的具体地方,因而可以急忙搜索到该值。散列函数的意义是给定一个键值,然后再次来到值在表中的地点

  举个例子,我们继承使用在后边使用的电子邮件地址簿。我们就要采用最广泛的散列函数——“lose
lose”散列函数,方法是概括地将每个键值中的每个字母的ASCII值相加

ECMAScript 1

【创制散列表】

  我们将使用数组来代表大家的数据结构,从搭建类的龙骨开头:

function HashTable(){
  var table = [];
}

  然后,给类添加一些艺术。我们给每个类实现多少个基础的艺术

put(key,value):向散列表增加一个新的项(也能更新散列表)。
remove(key):根据键值从散列表中移除值。
get(key):返回根据键值检索到的特定的值。

  在实现这五个办法此前,要落实的首先个点子是散列函数,它是HashTable类中的一个私房方法:

var loseloseHashCode = function (key) {
 var hash = 0; //{1}
 for (var i = 0; i < key.length; i++) { //{2}
     hash += key.charCodeAt(i); //{3}
 }
 return hash % 37; //{4}
};

  给定一个key参数,就能依照组成key的各样字符的ASCII码值的和得到一个数字。所以,首先需要一个变量来储存这些总和(行{1})。然后,遍历key(行{2})并将从ASCII表中查到的各样字符对应的ASCII值加到hash变量中(可以运用JavaScript的String类中的charCodeAt方法——行{3})。最后,返回hash值。为了取得相比小的数值,大家会动用hash值和一个任意数做除法的余数(mod)

【put】

  现在,有了散列函数,大家就足以兑现put方法了:

this.put = function(key, value) {
 var position = loseloseHashCode(key); //{5}
 console.log(position + ' - ' + key); //{6}
 table[position] = value; //{7}
}; 

  首先,遵照给定的key和所开创的散列函数总计出它在表中的地方(行{5})。为了便于展示音信,我们将总括出的职务输出至控制台(行{6})。由于它不是必要的,我们也能够将这行代码移除。然后要做的,是将value参数添加到用散列函数总结出的照应的岗位上(行{7})

【get】

  从HashTable实例中摸索一个值也很简短。为此,将会实现一个get方法。首先,大家会使用所成立的散列函数来求出给定key所对应的岗位。这么些函数会重回值的岗位,因而大家所要做的就是基于那一个职位从数组table中收获那么些值。

this.get = function (key) {
 return table[loseloseHashCode(key)];
}; 

【remove】

  要从HashTable实例中移除一个因素,只需要求出元素的职位(可以运用散列函数来得到)并赋值为undefined。

  对于HashTable类来说,大家不需要像ArrayList类一样从table数组师长地点也移除。由于元素分布于所有数组范围内,一些地方会没有其他因素占据,并默认为undefined值。大家也不可以将地方本身从数组中移除(这会改变其他因素的岗位),否则,当下次急需取得或移除一个因素的时候,这么些元素会不在我们用散列函数求出的职位上

this.remove = function(key) {
 table[loseloseHashCode(key)] = undefined;
}; 

【完整代码】

  HashTable类的全体代码如下所示 

function HashTable() {

    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 djb2HashCode = function (key) {
        var hash = 5381;
        for (var i = 0; i < key.length; i++) {
            hash = hash * 33 + key.charCodeAt(i);
        }
        return hash % 1013;
    };

    var hashCode = function (key) {
        return loseloseHashCode(key);
    };

    this.put = function (key, value) {
        var position = hashCode(key);
        console.log(position + ' - ' + key);
        table[position] = value;
    };

    this.get = function (key) {
        return table[hashCode(key)];
    };

    this.remove = function(key){
        table[hashCode(key)] = undefined;
    };

    this.print = function () {
        for (var i = 0; i < table.length; ++i) {
            if (table[i] !== undefined) {
                console.log(i + ": " + table[i]);
            }
        }
    };
}

【使用HashTable类】

  下边执行一些代码来测试HashTable类:

var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com'); 

  执行上述代码,会在控制巴尔的摩取得如下输出:

19 - Gandalf
29 - John
16 - Tyrion 

  上面的图样展现了含蓄这五个元素的HashTable数据结构:

ECMAScript 2

  现在来测试get方法:

console.log(hash.get('Gandalf'));
console.log(hash.get('Loiane')); 

  拿到如下的出口:

gandalf@email.com
undefined 

  由于Gandalf是一个在散列表中存在的键,get方法将会回去它的值。而鉴于Loiane是一个不设有的键,当我们试图在数组中按照岗位获取值的时候(一个由散列函数生成的地点),再次回到值将会是undefined(即不存在)

  然后,我们摸索从散列表中移除Gandalf:

hash.remove('Gandalf');
console.log(hash.get('Gandalf'));

  由于Gandalf不再存在于表中,hash.get(‘Gandalf’)方法将会在控制台上给出undefined的输出结果

【散列集合】

  在有的编程语言中,还有一种叫作散列集合的落实。散列集合由一个成团构成,可是插入、移除或得到元素时,使用的是散列函数。我们得以拔取本章中实现的具备代码来贯彻散列集合,不同之处在于,不再添加键值对,而是只插入值而并未键。例如,可以使用散列集合来储存所有的泰语单词(不包括它们的概念)。和聚众相似,散列集合只存储唯一的不另行的值

 

前方的话

  集合、字典和散列表可以储存不重复的值。在集结中,大家感兴趣的是每个值我,并把它看做紧要因素。在字典中,我们用[键,值]的形式来存储数据。在散列表中也是千篇一律(也是以[键,值]对的款型来存储数据)。不过两种数据结构的实现格局略有不同,本文将详细介绍字典和散列表这三种数据结构

 

ES6

  ECMAScript
2015增产了Map类。我们可以基于ES6的Map类开发我们的Dictionary类

  看看原生的Map类怎么用。仍旧用我们原先测试Dictionary类的例证:

var map = new Map();
map.set('Gandalf', 'gandalf@email.com');
map.set('John', 'johnsnow@email.com');
map.set('Tyrion', 'tyrion@email.com');
console.log(map.has('Gandalf')); //输出true
console.log(map.size); //输出3
console.log(map.keys()); //输出["Gandalf", "John", "Tyrion"]
console.log(map.values()); //输出["gandalf@email.com",
"johnsnow@email.com", "tyrion@email.com"]
console.log(map.get('Tyrion')); //输出tyrion@email.com 

  和Dictionary类不同,ES6的Map类的values方法和keys方法都回来Iterator,而不是值或键构成的数组。另一个区别是,我们兑现的size方法重返字典中存储的值的个数,而ES6的Map类则有一个size属性

  删除map中的元素得以用delete方法:

map.delete('John');

  clear方法会重置map数据结构,这跟我们在Dictionary类里实现的平等

  除了Set和Map这二种新的数据结构,ES6还扩大了它们的削弱版本,WeakSet和WeakMap。基本上,Map和Set与其弱化版本之间仅有的区别是:

  1、WeakSet或WeakMap类没有entries、keys和values等方法;

  2、只可以用对象作为键

  制造和采用这六个类重点是为着性能。WeakSet和WeakMap是削弱的(用对象作为键),没有强引用的键。那使得JavaScript的垃圾回收器可以从中清除整个入口。另一个亮点是,必须用键才可以取出值。这个类没有entries、keys和values等迭代器方法,因此,除非知道键,否则没有章程取出值

  使用WeakMap类的例子如下:

var map = new WeakMap();
var ob1 = {name:'Gandalf'}, //{1}
    ob2 = {name:'John'},
    ob3 = {name:'Tyrion'};
map.set(ob1, 'gandalf@email.com'); //{2}
map.set(ob2, 'johnsnow@email.com');
map.set(ob3, 'tyrion@email.com');
console.log(map.has(ob1)); //{3} 输出true
console.log(map.get(ob3)); //{4} 输出tyrion@email.com
map.delete(ob2); //{5}

  WeakMap类也足以用set方法,但无法拔取数字、字符串、布尔值等骨干数据类型,需要将名字转换为对象(行{1}和行{2})。搜索(行{3})、读取(行{4})和删除值(行{5}),也要传播作为键的目标。同样的逻辑也适用于WeakSet类

 

字典

  集合表示一组互不相同的要素(不另行的元素)。在字典中,存储的是[键,值]对,其中键名是用来查询特定元素的。字典和会聚很相似,集合以[值,值]的款式储存元素,字典则是以[键,值]的样式来储存元素。字典也称作映射

【成立字典】

  与Set类一般,ECMAScript 6同样包含了一个Map类的兑现,即咱们所说的字典

  下面将要实现的类就是以ECMAScript
6中Map类的实现为底蕴的。它和Set类很相似(但不同于存储[值,值]对的形式,我们将要存储的是[键,值]对)

  这是我们的Dictionary类的骨子:

function Dictionary() {
    var items = {};
}

  与Set类类似,我们将在一个Object的实例而不是数组中贮存元素。
然后,大家需要声明一些映射/字典所能使用的办法

set(key,value):向字典中添加新元素。
remove(key):通过使用键值来从字典中移除键值对应的数据值。
has(key):如果某个键值存在于这个字典中,则返回true,反之则返回false。
get(key):通过键值查找特定的数值并返回。
clear():将这个字典中的所有元素全部删除。
size():返回字典所包含元素的数量。与数组的length属性类似。
keys():将字典所包含的所有键名以数组形式返回。
values():将字典所包含的所有数值以数组形式返回。

【has】

  首先来贯彻has(key)方法。之所以要先实现那一个点子,是因为它会被set和remove等任何情势调用。这多少个措施的兑现和在此以前在Set类中的实现是同一的。使用JavaScript中的in操作符来表达一个key是否是items对象的一个性能。可以通过如下代码来落实:

this.has = function(key) { 
  return key in items;
}

【set】

  该格局接受一个key和一个value作为参数。我们直接将value设为items对象的key属性的值。它可以用来给字典添加一个新的值,或者用于更新一个已有的值

this.set = function(key, value) {
  items[key] = value; //{1}
}

【remove】

  它和Set类中的remove方法很一般,唯一的不同点在于大家将先找找key(而不是value),然后我们可以运用JavaScript的delete操作符来从items对象中移除key属性

this.remove = function(key) { 
  if (this.has(key)) {
    delete items[key];
    return true;
  }
  return false;
}

【get】

  get方法首先会注明大家想要检索的值是否存在(通过搜索key值),假使存在,将回来该值,
反之将赶回一个undefined值

this.get = function(key) {
  return this.has(key) ? items[key] : undefined;
};

【values】

  首先,我们遍历items对象的所有属性值(行{1})。为了确定值存在,大家运用has函数来阐明key确实存在,然后将它的值参加values数组(行{2})。最终,我们就能回去所有找到的值。那个点子以数组的样式再次来到字典中具有values实例的值:

this.values = function() { 
  var values = {};
  for (var k in items) { //{1} 
    if (this.has(k)) {
      values.push(items[k]); //{2}
    }
  }
  return values;
};

【clear】

    this.clear = function(){
        items = {};
    };

【size】

    this.size = function(){
        return Object.keys(items).length;
    };

【keys】

  keys方法重回在Dictionary类中持有用于标识值的键名。要取出一个JavaScript对象中有所的键名,可以把这么些目标作为参数传入Object类的keys方法,如下:

this.keys = function() {
 return Object.keys(items);
}; 

【items】

  上边来验证items属性的输出值。我们可以实现一个回到items变量的法门,叫作getItems:

this.getItems = function() {
 return items;
} 

【完整代码】

  Dictionary类的完全代码如下所示

function Dictionary(){

    var items = {};

    this.set = function(key, value){
        items[key] = value; //{1}
    };

    this.delete = function(key){
        if (this.has(key)){
            delete items[key];
            return true;
        }
        return false;
    };

    this.has = function(key){
        return items.hasOwnProperty(key);
        //return value in items;
    };

    this.get = function(key) {
        return this.has(key) ? items[key] : undefined;
    };

    this.clear = function(){
        items = {};
    };

    this.size = function(){
        return Object.keys(items).length;
    };

    this.keys = function(){
        return Object.keys(items);
    };

    this.values = function(){
        var values = [];
        for (var k in items) {
            if (this.has(k)) {
                values.push(items[k]);
            }
        }
        return values;
    };

    this.each = function(fn) {
        for (var k in items) {
            if (this.has(k)) {
                fn(k, items[k]);
            }
        }
    };

    this.getItems = function(){
        return items;
    }
}

【使用Dictionary类】

  首先,我们来创立一个Dictionary类的实例,然后给它添加三条电子邮件地址。大家将会选取那些dictionary实例来落实一个电子邮件地址簿。使用大家创造的类来实施如下代码:

var dictionary = new Dictionary(); 
dictionary.set('Gandalf', 'gandalf@email.com'); 
dictionary.set('John', 'johnsnow@email.com'); 
dictionary.set('Tyrion', 'tyrion@email.com');

  假诺推行了如下代码,输出结果将会是true:

console.log(dictionary.has('Gandalf'));

  下边的代码将会输出3,因为我们向字典实例中添加了多少个元素:

console.log(dictionary.size());

  现在,执行下面的几行代码:

console.log(dictionary.keys()); 
console.log(dictionary.values()); 
console.log(dictionary.get('Tyrion'));

  输出结果个别如下所示:

["Gandalf", "John", "Tyrion"]
["gandalf@email.com", "johnsnow@email.com", "tyrion@email.com"] 
tyrion@email.com

  最终,再履行几行代码:

dictionary.remove('John');

  再实施下边的代码:

console.log(dictionary.keys()); 
console.log(dictionary.values()); 
console.log(dictionary.getItems());

  输出结果如下所示:

["Gandalf", "Tyrion"] 
["gandalf@email.com", "tyrion@email.com"]
Object {Gandalf: "gandalf@email.com", Tyrion: "tyrion@email.com"}

  移除了一个因素后,现在的dictionary实例中只含有五个要素了

 

拍卖争辩

  有时候,一些键会有同一的散列值。不同的值在散列表中对应一律地方的时候,我们称其为冲突。例如,我们看看下面的代码会收获哪些的输出结果:

var hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jonathan', 'jonathan@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com'); 

  输出结果如下:

19 - Gandalf
29 - John
16 - Tyrion
16 - Aaron
13 - Donnie
13 - Ana
5 - Jonathan
5 - Jamie
5 - Sue
32 - Mindy
32 - Paul
10 – Nathan

  Tyrion和Aaron有同样的散列值(16)。Donnie和Ana有同一的散列值(13),乔纳森、詹米(Jamie)和Sue有一样的散列值(5),Mindy和保罗(Paul)也有一致的散列值(32)

  这HashTable实例会怎样呢?执行往日的代码后散列表中会有什么样值吗?为了得到结果,大家来兑现一个叫作print的赞助方法,它会在控制台上输出HashTable中的值:

this.print = function() {
 for (var i = 0; i < table.length; ++i) { //{1}
   if (table[i] !== undefined) { //{2}
     console.log(i + ": " + table[i]);//{3}
   }
 }
}; 

  首先,遍历数组中的所有因素(行{1})。当某个地方上有值的时候(行{2}),会在控制台上输出地方和相应的值(行{3})。现在来采用这多少个点子:

hash.print();

  在控制台上得到如下的输出结果:

5:sue@email.com
10:nathan@email.com
13:ana@email.com
16:aaron@email.com
19:gandalf@email.com
29:johnsnow@email.com
32:paul@email.com

  乔纳森、Jamie和Sue有同样的散列值,也就是5。由于Sue是最后一个被添加的,Sue将是在HashTable实例中据为己有地点5的元素。首先,乔纳森(Jonathan)会占据这多少个地点,然后詹米(Jamie)会覆盖它,然后Sue会再度覆盖。这对于其他发生争辨的要从来说也是均等的。

  使用一个数据结构来保存数据的目标显明不是去丢失这么些多少,而是经过某种情势将它们整个保存起来。由此,当这种气象暴发的时候就要去解决它。处理争持有二种形式:分离链接、线性探查和双散列法

【分离链接】

  分离链接法包括为散列表的每一个职位创设一个链表并将元素存储在其间。它是化解顶牛的最简便易行的不二法门,不过它在HashTable实例之外还需要异常的仓储空间

  例如,我们在事先的测试代码中利用分别链接的话,输出结果将会是这般:

ECMAScript 3

  在岗位5上,将会有隐含多少个元素的LinkedList实例;在职务13、16和32上,将会有隐含五个因素的LinkedList实例;在地方10、19和29上,将会有隐含单个元素的LinkedList实例

  对于分离链接和线性探查来说,只需要重写两个点子:put、get和remove。那两个主意在每种技术实现中都是见仁见智的

  为了兑现一个选取了分手链接的HashTable实例,大家需要一个新的协助类来表示即将加盟LinkedList实例的因素。大家管它叫ValuePair类(在HashTable类内部定义):

var ValuePair = function(key, value){
 this.key = key;
 this.value = value;
 this.toString = function() {
  return '[' + this.key + ' - ' + this.value + ']'; 
  }
};

  那么些类只会将key和value存储在一个Object实例中。大家也重写了toString方法,以便之后在浏览器控制苏州输出结果

  大家来兑现率先个情势,put方法,代码如下:

this.put = function(key, value){
 var position = loseloseHashCode(key);
 if (table[position] == undefined) { //{1}
   table[position] = new LinkedList();
 }
 table[position].append(new ValuePair(key, value)); //{2}
}; 

  在那些法子中,将表明要参加新因素的岗位是不是业已被占据(行{1})。倘若那些职务是首先次被投入元素,我们会在这多少个职位上伊始化一个LinkedList类的实例(你曾经在第5章中上学过)。然后,使用append方法向LinkedList实例中添加一个ValuePair实例(键和值)(行{2})

  然后,大家兑现用来博取特定值的get方法:

this.get = function(key) {
 var position = loseloseHashCode(key);
 if (table[position] !== undefined){ //{3}
  //遍历链表来寻找键/值
  var current = table[position].getHead(); //{4}
    while(current.next){ //{5}
    if (current.element.key === key){ //{6}
      return current.element.value; //{7}
    }
    current = current.next; //{8}
  }
  //检查元素在链表第一个或最后一个节点的情况
  if (current.element.key === key){ //{9}
    return current.element.value;
  }
 }
 return undefined; //{10}
}; 

  大家要做的率先个验证,是规定在特定的地方上是否有元素存在(行{3})。假如没有,则赶回一个undefined表示在HashTable实例中没有找到这一个值(行{10})。假诺在这一个职位上有值存在,我们清楚这是一个LinkedList实例。现在要做的是遍历这些链表来搜寻我们需要的元素。在遍历在此之前先要获取链表表头的引用(行{4}),然后就可以从链表的头部遍历到尾部(行{5},current.next将会是null)。

  Node链表包含next指针和element属性。而element属性又是ValuePair的实例,所以它又有value和key属性。可以透过current.element.next来得到Node链表的key属性,并由此相比它来确定它是否就是大家要找的键(行{6})。(这就是要利用ValuePair那几个协助类来囤积元素的原委。我们不能够简单地囤积值我,这样就不可以确定哪些值对应着一定的键。)如若key值相同,就再次来到Node的值(行{7});假设不雷同,就继续遍历链表,访问下一个节点(行{8})。

  假设要找的要素是链表的率先个或最终一个节点,那么就不会进入while循环的其中。由此,需要在行{9}处理那种不同常常的场所

  使用分别链接法从HashTable实例中移除一个元素和从前在本章实现的remove方法有一些不同。现在选拔的是链表,我们需要从链表中移除一个要素。来看看remove方法的实现:

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){ //{11}
      table[position].remove(current.element); //{12}
      if (table[position].isEmpty()){ //{13}
        table[position] = undefined; //{14}
      }
      return true; //{15}
    }
    current = current.next;
  }
  // 检查是否为第一个或最后一个元素
  if (current.element.key === key){ //{16}
    table[position].remove(current.element);
  if (table[position].isEmpty()){
    table[position] = undefined;
  }
  return true;
  }
 }
 return false; //{17}
}; 

  在remove方法中,我们运用和get方法一致的步调找到要找的元素。遍历LinkedList实例时,尽管链表中的current元素就是要找的因素(行{11}),使用remove方法将其从链表中移除。然后举行一步额外的表明:倘使链表为空了(行{13}——链表中不再有此外因素了),就将散列表这么些岗位的值设为undefined(行{14}),这样搜索一个因素或打印它的内容的时候,就足以跳过这么些地方了。最终,重临true表示那个因素已经被移除(行{15})或者在终极回到false表示那个因素在散列表中不存在(行{17})。同样,需要和get方法一致,处理元素在首先个或最终一个的动静(行{16})

  重写了这六个主意后,大家就具备了一个运用了分手链接法来拍卖争执的HashMap实例

  分离链接的HashMap的总体代码如下所示

function HashTableSeparateChaining(){

    var table = [];

    var ValuePair = function(key, value){
        this.key = key;
        this.value = value;

        this.toString = function() {
            return '[' + this.key + ' - ' + this.value + ']';
        }
    };

    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    };

    var hashCode = function(key){
        return loseloseHashCode(key);
    };

    this.put = function(key, value){
        var position = hashCode(key);
        console.log(position + ' - ' + key);

        if (table[position] == undefined) {
            table[position] = new LinkedList();
        }
        table[position].append(new ValuePair(key, value));
    };

    this.get = function(key) {
        var position = hashCode(key);

        if (table[position] !== undefined  && !table[position].isEmpty()){

            //iterate linked list to find key/value
            var current = table[position].getHead();

            do {
                if (current.element.key === key){
                    return current.element.value;
                }
                current = current.next;
            } while(current);
        }
        return undefined;
    };

    this.remove = function(key){

        var position = hashCode(key);

        if (table[position] !== undefined){

            //iterate linked list to find key/value
            var current = table[position].getHead();

            do {
                if (current.element.key === key){
                    table[position].remove(current.element);
                    if (table[position].isEmpty()){
                        table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;
            } while(current);
        }

        return false;
    };

    this.print = function() {
        for (var i = 0; i < table.length; ++i) {
            if (table[i] !== undefined) {
               console.log(table[i].toString());
            }
        }
    };
}

【线性探查】

  另一种缓解争持的办法是线性探查。当想向表中某个地点参与一个新因素的时候,倘使索引为index的地点已经被占据了,就尝试index+1的岗位。假设index+1的岗位也被挤占了,就尝试index+2的职务,以此类推

  继续贯彻内需重写的三个办法。第一个是put方法:

this.put = function(key, value){
 var position = loseloseHashCode(key); // {1}
 if (table[position] == undefined) { // {2}
   table[position] = new ValuePair(key, value); // {3}
 } else {
  var index = ++position; // {4}
  while (table[index] != undefined){ // {5}
    index++; // {6}
  }
  table[index] = new ValuePair(key, value); // {7}
 }
}; 

  和事先同一,先拿走由散列函数生成的职务(行{1}),然后验证这么些职位是不是有元素存在(假设这么些地方被霸占了,将会透过行{2}的验证)。假使没有元素存在,就在这么些职务参与新因素(行{3}——一个ValuePair的实例)

  即便那些职务已经被占据了,需要找到下一个不曾被占据的职位(position的值是undefined),因而我们讲明一个index变量并赋值为position+1(行{4}——在变量名前拔取自增运算符++会先递增变量值然后再将其赋值给index)。然后验证这个职位是不是被占据(行{5}),假如被霸占了,继续将index递增(行{6}),直到找到一个一直不被挤占的岗位。然后要做的,就是将值分配到这么些职位(行{7})

ECMAScript,  假诺重新实施前面实例中插入数据的代码,下图呈现使用了线性探查的散列表的末梢结出:

ECMAScript 4

  让大家来模拟一下散列表中的插入操作

  1、试着插入Gandalf。它的散列值是19,由于散列表刚刚被创制,地点19仍然空的——可以在那边插入数据

  2、试着在岗位29插入约翰。它也是空的,所以可以插入这厮名

  3、试着在岗位16插入Tyrion。它是空的,所以可以插入这个人名

  4、试着插入Aaron,它的散列值也是16。地点16早已被Tyrion占据了,所以需要检查索引值为position+1的职位(16+1)。地方17是空的,所以可以在地方17插入亚伦(Aaron)

  5、接着,试着在职位13插入Donnie。它是空的,所以可以插入这厮名

  6、想在职务13插入Ana,不过这些职位被占据了。由此在地方14开展尝试,它是空的,所以可以在此间插入姓名

  7、然后,在职位5插入乔纳森(Jonathan),那么些地方是空的,所以可以插入这厮名

  8、试着在职位5插入詹米,不过这多少个地点被占了。所以跳至地点6,这么些岗位是空的,因而得以在这些职务插入姓名

  9、试着在职务5插入Sue,然而地点被占用了。所以跳至地方6,但也被占了。接着跳至地点7,这里是空的,所以可以在此处插入姓名。以此类推

  现在安插了颇具的元素,下边实现get方法来获取它们的值

this.get = function(key) {
 var position = loseloseHashCode(key);
 if (table[position] !== undefined){ //{8}
  if (table[position].key === key) { //{9}
    return table[position].value; //{10}
  } else {
    var index = ++position;
    while (table[index] === undefined  || table[index].key !== key){ //{11}
      index++;
    }
    if (table[index].key === key) { //{12}
      return table[index].value; //{13}
    }
  }
 }
 return undefined; //{14}
}; 

  要赢得一个键对应的值,先要确定那些键存在(行{8})。假设那些键不设有,表达要摸索的值不在散列表中,因而得以再次来到undefined(行{14})。假设这多少个键存在,需要检讨我们要找的值是否就是其一职务上的值(行{9})。如假如,就赶回这个值(行{10})。

  即使不是,就在散列表中的下一个地方连续查找,直到找到一个键值与我们要找的键值相同的因素(行{11})。然后,验证一下当下项就是我们要找的项(行{12}——只是为了确认一下)并且将它的值重临(行{13})。

  大家不可以确定要找的要素实际上在哪里,那就是应用ValuePair来代表HashTable元素的原由

  remove方法和get方法基本相同,不同之处在于行{10}和{13},它们将会由上面的代码代替:

table[index]=undefined;

  要移除一个元素,只需要给其赋值为undefined,来表示这一个职务不再被占用同时可以在必要时接受一个新因素

  线性探查的HashTable的一体化代码如下所示

function HashLinearProbing(){

    var table = [];

    var ValuePair = function(key, value){
        this.key = key;
        this.value = value;

        this.toString = function() {
            return '[' + this.key + ' - ' + this.value + ']';
        }
    };

    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    };

    var hashCode = function(key){
        return loseloseHashCode(key);
    };

    this.put = function(key, value){
        var position = hashCode(key);
        console.log(position + ' - ' + 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 = hashCode(key);

        if (table[position] !== undefined){
            if (table[position].key === key) {
                return table[position].value;
            } else {
                var index = ++position;
                while (table[index] !== undefined && (table[index] && table[index].key !== key)){
                    index++;
                }
                if (table[index] && table[index].key === key) {
                    return table[index].value;
                }
            }
        } else { //search for possible deleted value
            var index = ++position;
            while (table[index] == undefined || index == table.length ||
                (table[index] !== undefined && table[index] && table[index].key !== key)){
                index++;
            }
            if (table[index] && table[index].key === key) {
                return table[index].value;
            }
        }
        return undefined;
    };

    this.remove = function(key){
        var position = hashCode(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;
                }
            }
        }
    };

    this.print = function() {
        for (var i = 0; i < table.length; ++i) {
            if (table[i] !== undefined) {
                console.log(i + ' -> ' + table[i].toString());
            }
        }
    };
}

【更好的散列函数】

  “loselose”散列函数并不是一个展现可以的散列函数,因为它会暴发太多的争执。假设采用那一个函数的话,会发出各类各种的争执。一个突显优秀的散列函数是由多少个地点构成的:插入和寻找元素的日子(即性能),当然也囊括较低的争持可能

  另一个可以实现的比“loselose”更好的散列函数是djb2:

var djb2HashCode = function (key) {
 var hash = 5381; //{1}
 for (var i = 0; i < key.length; i++) { //{2}
     hash = hash * 33 + key.charCodeAt(i); //{3}
 }
 return hash % 1013; //{4}
}; 

  它包括初叶化一个hash变量并赋值为一个质数(行{1}——大多数兑现都使用5381),然后迭代参数key(行{2}),将hash与33相乘(用来作为一个魔力数),并和眼前迭代到的字符的ASCII码值相加(行{3})

  最终,大家将运用相加的和与另一个任意质数(比我们以为的散列表的尺寸要大——在本例中,我们觉得散列表的深浅为1000)相除的余数。

  如果重复实施前面实例中插入数据的代码,那将是拔取djb2HashCode代替loseloseHashCode的末段结出:

798-Gandalf
838-John
624-Tyrion
215-Aaron
278-Donnie
925-Ana
288-Jonathan
962-Jamie
502-Sue
804-Mindy
54-Paul
223-Nathan

  没有争辩!这并不是最好的散列函数,但这是最被社区推举的散列函数之一