实现散列

痛定思痛。 2021-07-24 16:59 371阅读 0赞

散列:
    	快速插入、取用和删除
    	查找数据低下,如最大值和最小值
    	质数:素数也指的是质数,除了1和它本身,没有其他因子

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA_size_16_color_FFFFFF_t_70 1]

代码示例:  
通过传入字符串的uniCode或优化过uniCode的编码总和%字符串的长度,来获取散列的索引值,来存储内容

增大散列值解决位置冲突:

function HashTable() { 
      this.table = new Array(137);
      this.simpleHash = simpleHash;	//计算散列位置辅助函数,计算出所有字符串的unicode值,但相同字符不同位置的字符串会得出相同结果
      this.betterHash = betterHash;//增大散列值后的辅助函数
      this.display = display;//遍历
      this.put = put;//插入元素
      this.get = get;//获取元素
    }
    
    function simpleHash(data) {  //计算键位置的辅助函数
      let total = 0;
      for (let i = 0; i < data.length; i++){ 
        total += data.charCodeAt(i); //计算出所有字符串的unicode值,但相同字符不同位置的字符串会得出相同结果
      }
    
      return total % this.table.length; //散列函数除留余数法
    }
    
    function betterHash(data) { 
      let total = 0;
      let H = 31; //手动设定一个值,将unicode计算得出的值更散列,即使得相同字符不同位置的字符串,得出的结果相同概率减少
      for (let i = 0; i < data.length; i++){ 
        total +=H*total+ data.charCodeAt(i); //计算出所有字符串的unicode值
      }
    
      return total % this.table.length; //散列函数除留余数法
    }
    
    function put(data) { 
      //let pos = this.simpleHash(data);
      let pos = this.betterHash(data); //方式一:增大散列值
      this.table[pos] = data;
    
    
    }
    
    function get(key) { 
      //return this.simpleHash(key);
      return this.betterHash(key);
    }
    
    function display() { 
      var n;
      for (var i = 0; i < this.table.length; i++){ 
        if (this.table[i]!= undefined) { 
          console.log("键值是->" + i + "值是" + this.table[i]);
        }
      }
    }
    
    let hTable = new HashTable();
    hTable.buildChains();
    hTable.put('china');  //会和nicha的unicode值重复,因为字符都是相同的
    hTable.put('jeff');
    hTable.put('jack');
    hTable.put('nicha');
    hTable.put('tom');
    hTable.put('12344');
    hTable.display();

开链法解决冲突:  
将存储的数组变成二维数组,如果unicode值相同,则往对应数组后挪一位存储,\[\[1,冲突2\],\[…\],\[…\]\]

function HashTable() { 
      this.table = new Array(137);
      this.simpleHash = simpleHash;
      this.buildChains = buildChains;
      this.display = display;
      this.put = put;
      this.get = get;
    }
    
    //开链法,即升级为二维数组
    function buildChains() { 
      console.log(this.table)
      for (let i = 0; i < this.table.length; i++){ 
        this.table[i] = new Array();
      }
    }
    
    
    function simpleHash(data) {  //计算键位置的辅助函数
      let total = 0;
      for (let i = 0; i < data.length; i++){ 
        total += data.charCodeAt(i); //计算出所有字符串的unicode值,但相同字符不同位置的字符串会得出相同结果
      }
    
      return total % this.table.length; //散列函数除留余数法
    }
    
    
    function put(data) { 
      let pos = this.simpleHash(data);
      
      let index = 0;
      if (this.table[pos][index] == undefined) { 	
        this.table[pos][index] = data;
        index++;
      } else { 
        while (this.table[pos][index] !== undefined) { //若存储冲突,往后挪一位
          index++;
        }
        this.table[pos][index] = data;
        index++;
      }
    }
    
    function get(key) { 
      return this.simpleHash(key);
    }
    
    function display() { 
      var n;
      for (var i = 0; i < this.table.length; i++){ 
        if (this.table[i][0] != undefined) { 
          console.log("键值是->" + i + "值是" + this.table[i]);
        }
      }
    }
    
    let hTable = new HashTable();
    hTable.buildChains(); //将一维数组变成二维数组
    hTable.put('china');  //会和nicha的unicode值重复,因为字符都是相同的
    hTable.put('jeff');
    hTable.put('jack');
    hTable.put('nicha');
    hTable.put('tom');
    hTable.put('12344');
    hTable.display();

线性探测法解决冲突:  
如果数组当前位置存储冲突,则移动到下一个位置存储,同时还需修改返回散列值的get方法,不能单纯地返回对应simpleHash,因为可能相同值冲突,真正值往后移了

function HashTable() { 
      this.table = new Array(137);
      this.simpleHash = simpleHash;
      this.display = display;
      this.put = put;
      this.get = get;
    }
    
    function simpleHash(data) {  //计算键位置的辅助函数
      let total = 0;
      for (let i = 0; i < data.length; i++){ 
        total += data.charCodeAt(i); //计算出所有字符串的unicode值,但相同字符不同位置的字符串会得出相同结果
      }
    
      return total % this.table.length; //散列函数除留余数法
    }
    
    
    function put(data) { 
      let pos = this.simpleHash(data);
      while (this.table[pos] != undefined) {  //线性探测,如果当前位置有值,往后移动
        pos++;
      }
      this.table[pos] = data;
    }
    
    function get(key) {  //修改返回散列值方法,不能单纯地返回对应simpleHash,因为可能相同值冲突,真正值往后移了
      for (i = 0; i < this.table.length; i++){ 
        if (this.table[i] == key) { 
          return i;
        }
      }
    }
    
    function display() { 
      var n;
      for (var i = 0; i < this.table.length; i++){ 
        if (this.table[i]!= undefined) { 
          console.log("键值是->" + i + "值是" + this.table[i]);
        }
      }
    }
    
    let hTable = new HashTable();
    hTable.put('china');  //会和nicha的unicode值重复,因为字符都是相同的
    hTable.put('jeff');
    hTable.put('jack');
    hTable.put('nicha');
    hTable.put('tom');
    hTable.put('12344');
    hTable.display();
    
    console.log('位置:'+hTable.get('nicha'))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210404213507332.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA_size_16_color_FFFFFF_t_70 1]: /images/20210724/ef795d40b1f246a8a7ddfdd719c74092.png

发表评论取消回复

表情：

评论列表（有 0 条评论，371人围观）

还没有评论，来说两句吧...

相关阅读

相关散列（Hash）和散列码（HashCode）

文章目录 1 概念 2 散列在编程语言中的应用 2.1 散列在Java中应用 2.1.1 忽略重

刺骨的言语ヽ痛彻心扉/ 2023年07月16日 13:56/ 0 赞/ 110 阅读

相关算法_散列

散列：Hashing 引入散列通过构造一个新的数据结构，能使得查找算法的复杂度降到O(1)，这种概念称为“散列Hashing” 如果我们事先能知道要找

墨蓝/ 2023年02月18日 01:57/ 0 赞/ 45 阅读

相关数据结构:JavaScript实现散列

一.引言散列是一种常用的数据存储技术，散列后的数据可以快速的插入或者取用，散列使用的数据结构叫做散列表。我们的散列是基于数组进行设计的，数组的长度是事先设定的，如有

小鱼儿/ 2022年08月20日 05:17/ 0 赞/ 116 阅读

相关散列、散列码、hashCode()

散列： > 散列就是将键保存在某处，以便能很快找到。散列码： 1、存储一组元素最快的是数组，所以用它来表示键的信息，不是键本身，通过键对象生成一个数字，就是散列

比眉伴天荒/ 2022年06月07日 02:12/ 0 赞/ 229 阅读

相关散列查找

散列查找 1. 散列的定义：散列，就是Hash，把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空

Myth丶恋晨/ 2022年05月29日 13:23/ 0 赞/ 159 阅读

相关 Java高级系列——散列与散列码

使用散列的目的：想要使用一个对象查找另一个对象。散列的价值：散列的价值在于速度，散列使得查询得以快速进行。设计hashCode()时最重要的因素：无论何时，对同一个对象

你的名字/ 2022年05月28日 11:28/ 0 赞/ 174 阅读

相关散列

对比前面所学的树，虽然其删除和插入操作可以达到O(logN)，而散列表却可以以常数平均时间实现同样的操作。不过，树的O(logN)这个平均操作时间也未必比散列表的常数平均操

我会带着你远行/ 2022年01月06日 20:47/ 0 赞/ 338 阅读

相关 Java实现MD5散列

生成MD5值 String str = "12345"; MessageDigest digest =MessageDigest.getInstance("M

谁借莪１个温暖的怀抱￠/ 2021年11月11日 17:26/ 0 赞/ 259 阅读

相关散列查找

1.定义在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h(K)计算出该元素的存储位

喜欢ヅ旅行/ 2021年09月20日 14:52/ 0 赞/ 326 阅读

相关实现散列

散列: 快速插入、取用和删除查找数据低下,如最大值和最小值质数:素数也指的是质数,除了1和它本身,没有其他因子 ![在这里插入图片描

痛定思痛。/ 2021年07月24日 16:59/ 0 赞/ 372 阅读