我对JS散列表的简单学习

lindroid 发布于2019-08-21 15:33 / 2871人阅读

摘要：对散列表的简单学习类也叫类，是类的一种散列表实现方式。键值散列函数散列值形成散列表地址数据键值对相关操作方法创建一个散列表实现一个散列函数，即将码值相加的方法。

对JS散列表的简单学习

HashTable类也叫HashMap类，是Dictionary类的一种散列表实现方式。

散列算法的作用是尽可能快的在数据结构中找到一个值。

在之前的学习中，如果你想要获得数据结构中的一个值，需要遍历整个数据结构来找到它。如果使用散列函数，就能知道具体位置，也就能够快速找到该值。

使用最常见的散列函数--‘lose lose’散列函数，简单的将每个键值中的每个字母的ASCII码值相加，将得到的散列值作为地址。

（键值）John （散列函数）74+111+104+110 （散列值）399 形成散列表

地址	数据键值对
[399]	john/john@email.com
...
[685]	gandalf/@email.com

相关操作方法

创建一个散列表

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

实现一个散列函数，即将ASCII码值相加的方法。

var loseloseHashTable = function(key) {
  var hash = 0;
  for(var i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % 37; //这里只是为了得到比较小的数值，随便除了一个数
}

实现put(key, value)方法，向散列表中添加一个新的项。

this.put = function (key, value) {
  var position = loseloseHashTable(key); //得到散列值，即位置
  table[position] = value;
};

实现get(key)方法，返回根据键值检索到的特定的值。

this.get = function(key) {
  var position = loseloseHashTable(key);
  return table[position];
};

实现remove()方法，从散列中移除键值对应的数据值。

this.remove = function(key) {
  table[loseloseHashTable(key)] = undefined; //没有数据占据的位置默认值为undefined
};

具体使用方法这里就不赘述了，就是方法的调用。

冲突怎么办？

假如有多个键值得到的散列值相等，那么后面的元素会覆盖前面前面相同散列值的元素，
怎么解决呢？

分离链接

分离链接法为散列表的每一个位置创建一个链表并将元素存储在里面。

地址	链表存储数据
[5]	[no1/no1.com]指针-> [no2/no2.com]指针-> [X]null

在地址5上，链表实例上有两个元素no1.com和no2.com。

需要添加一个valuePair类，来表示将要加入链表的实例的元素。

var valuePair = function(key, value) {
  this.key = key;
  this.value = value;
  this.toString = function() {
    return `[${this.key} - ${this.value}]`;
  }
}

重写一个put()方法

this.put = function(key, value) {
  var position = loseloseHashTable(key);
  if(table[position] == undefined) {
    table[position] = new LinkedList(); //如果这个位置是第一次被加入元素，那么就初始化一个LinkedList实例
  }
  table[position].append(new valuePair(key, value)); //链表实现的append方法添加一个valuePair实例。
};

重写一个get(key)方法

this.get = function(key) {
  var position = loseloseHashTable(key);
  if(table[position] !== undefined) { //位置上有元素存在
    //遍历链表来寻找键/值
    var current = table[position].getHead();
    while (current.next) { //这里遍历不到链表最后一个位置
      if(current.element.key === key) {
        return current.element.value; //element属性是valuePair的实例，包含key和value属性
      }
      current = current.next;
    }

    //检查元素在链表第一个或者最后一个的情况
    if(current.element.key === key) {
      return current.element.value;
    }
  }
  return undefined; //位置上没有值
};

重写remove(key)方法

this.remove = function(key) {
  var position = loseloseHashTable(key);

  if(table[position] !== undefined) {
    var current = table[position].getHead();
    while (current.next) {
      if(current.element.key === key) {
        table[position].remove(current.element); //链表实现的remove方法
        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;
}

线性探查

如果索引为index的位置已经被占据了，就尝试index+1的位置，以此类推。

5的位置被占据，就寻找6的位置，6的位置被占据，就找7，7没被占据就赋值(本应该在位置5上，但是线性探查变成了位置7)

实现put(key, value)方法

this.put = function(key, value) {
  var position = loseloseHashTable(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);
  }
};

实现get()方法

this.get = function(key) {
  var position = loseloseHashTable(key);
  if(table[position] !== undefined) {
    if(table[position].key === key) { //举例位置5
      return table[position].value; //记号1
    } 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; //找到7 //记号2
      }
    }
  }
  return undefined;
};

实现remove()方法

只需要改变get方法的记号1和记号2的位置代码即可
改为table[index] = undefined;

更好的散列函数

var djb2HashCode = function(key) {
  var hash = 5381; //初始化一个hash变量并赋值为一个质数5381
  for(var i = 0; i < key.length; i++) { //遍历
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
}

相比来说，冲突会变少很多~

GPU云服务器云服务器散列表 python 散列表简单的深度学习最简单的深度学习

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/88223.html

我对JS字典的简单学习

摘要：我对字典的简单学习字典的概念集合字典和散列表都可以来存储不重复的值。字典也被称为映射。中有集合类的实现，也有字典类的实现。相关操作方法实现方法，判断某个键值是否在这个字典中，有则返回。实现方法，将字典所有的值以数组的形式返回。我对JS字典的简单学习字典的概念集合、字典和散列表都可以来存储不重复的值。在集合中我们使用[值,值]来保存，在字典和散列表中使用[键,值]来存储数据。字典...

CntChen 2019-08-20 15:35 评论0 收藏0
学习数据结构与算法之字典和散列表

摘要：小结实现了字典和哈希表感觉没有想象中那么困难，当然这还是开始。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算法之二叉搜索树字典不是新华字典哦，这里的字典也称作_映射_，是一种数据结构，跟set集合很相似的一种数据结构，都可以用来...

Heier 2019-08-21 11:52 评论0 收藏0
《Javascript数据结构和算法》笔记-「字典和散列表」

摘要：我经常在业务代码中把数据处理成这种字典的数据结构获取的方法哈希表在学习了类之后，我们会学习散列表，也就是哈希表。《Javascript数据结构和算法》笔记-「字典和散列表」集合、字典、散列表存储的都是「不重复」的数据结构集合：我们更关注每一个元素的值，并把其作为主要元素字典：我们用[键,值]的形式来存储数据散列表：跟字典类似，也会是用[键,值]的形式来存储数据但是「字...

wenyiweb 2019-08-26 13:23 评论0 收藏0
我对JS链表的简单学习

摘要：我对链表的学习什么是链表要存储多个元素，数组可能是最常用的数据结构。链表的学习创建一个链表各种方法表示要加入列表的项，它包含一个属性以及一个属性，表示要添加到列表的值，表示指向列表下一个节点项的指针。我对JS链表的学习什么是链表要存储多个元素，数组可能是最常用的数据结构。这种数据结构非常方便，但是有一个缺点：从数组的起点或者中间插入或移除项的成本非常高，因为需要移动元素（比如你插...

余学文 2019-08-20 15:07 评论0 收藏0
Map集合、散列表、红黑树介绍

摘要：并且，我们的底层都是红黑树来实现的。红黑树是一种平衡二叉树因此它没有节点。前言声明，本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合： Collection总览 List集合就这么简单【源码剖析】原本我是打算继续将Collection下的Set集合的，结果看了源码发现：Set集合实际上就是HashMap来构建的！ showImg(https:/...

2json 2019-08-15 15:20 评论0 收藏0