我對(duì)JS散列表的簡(jiǎn)單學(xué)習(xí)

lindroid 發(fā)布于2019-08-21 15:33 / 2931人閱讀

摘要：對(duì)散列表的簡(jiǎn)單學(xué)習(xí)類(lèi)也叫類(lèi)，是類(lèi)的一種散列表實(shí)現(xiàn)方式。鍵值散列函數(shù)散列值形成散列表地址數(shù)據(jù)鍵值對(duì)相關(guān)操作方法創(chuàng)建一個(gè)散列表實(shí)現(xiàn)一個(gè)散列函數(shù)，即將碼值相加的方法。

對(duì)JS散列表的簡(jiǎn)單學(xué)習(xí)

HashTable類(lèi)也叫HashMap類(lèi)，是Dictionary類(lèi)的一種散列表實(shí)現(xiàn)方式。

散列算法的作用是盡可能快的在數(shù)據(jù)結(jié)構(gòu)中找到一個(gè)值。

在之前的學(xué)習(xí)中，如果你想要獲得數(shù)據(jù)結(jié)構(gòu)中的一個(gè)值，需要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)找到它。如果使用散列函數(shù)，就能知道具體位置，也就能夠快速找到該值。

使用最常見(jiàn)的散列函數(shù)--‘lose lose’散列函數(shù)，簡(jiǎn)單的將每個(gè)鍵值中的每個(gè)字母的ASCII碼值相加，將得到的散列值作為地址。

（鍵值）John （散列函數(shù)）74+111+104+110 （散列值）399 形成散列表

地址	數(shù)據(jù)鍵值對(duì)
[399]	john/[email protected]
...
[685]	gandalf/@email.com

相關(guān)操作方法

創(chuàng)建一個(gè)散列表

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

實(shí)現(xiàn)一個(gè)散列函數(shù)，即將ASCII碼值相加的方法。

var loseloseHashTable = function(key) {
  var hash = 0;
  for(var i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % 37; //這里只是為了得到比較小的數(shù)值，隨便除了一個(gè)數(shù)
}

實(shí)現(xiàn)put(key, value)方法，向散列表中添加一個(gè)新的項(xiàng)。

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

實(shí)現(xiàn)get(key)方法，返回根據(jù)鍵值檢索到的特定的值。

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

實(shí)現(xiàn)remove()方法，從散列中移除鍵值對(duì)應(yīng)的數(shù)據(jù)值。

this.remove = function(key) {
  table[loseloseHashTable(key)] = undefined; //沒(méi)有數(shù)據(jù)占據(jù)的位置默認(rèn)值為undefined
};

具體使用方法這里就不贅述了，就是方法的調(diào)用。

沖突怎么辦？

假如有多個(gè)鍵值得到的散列值相等，那么后面的元素會(huì)覆蓋前面前面相同散列值的元素，
怎么解決呢？

分離鏈接

分離鏈接法為散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表并將元素存儲(chǔ)在里面。

地址	鏈表存儲(chǔ)數(shù)據(jù)
[5]	[no1/no1.com]指針-> [no2/no2.com]指針-> [X]null

在地址5上，鏈表實(shí)例上有兩個(gè)元素no1.com和no2.com。

需要添加一個(gè)valuePair類(lèi)，來(lái)表示將要加入鏈表的實(shí)例的元素。

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

重寫(xiě)一個(gè)put()方法

this.put = function(key, value) {
  var position = loseloseHashTable(key);
  if(table[position] == undefined) {
    table[position] = new LinkedList(); //如果這個(gè)位置是第一次被加入元素，那么就初始化一個(gè)LinkedList實(shí)例
  }
  table[position].append(new valuePair(key, value)); //鏈表實(shí)現(xiàn)的append方法添加一個(gè)valuePair實(shí)例。
};

重寫(xiě)一個(gè)get(key)方法

this.get = function(key) {
  var position = loseloseHashTable(key);
  if(table[position] !== undefined) { //位置上有元素存在
    //遍歷鏈表來(lái)尋找鍵/值
    var current = table[position].getHead();
    while (current.next) { //這里遍歷不到鏈表最后一個(gè)位置
      if(current.element.key === key) {
        return current.element.value; //element屬性是valuePair的實(shí)例，包含key和value屬性
      }
      current = current.next;
    }

    //檢查元素在鏈表第一個(gè)或者最后一個(gè)的情況
    if(current.element.key === key) {
      return current.element.value;
    }
  }
  return undefined; //位置上沒(méi)有值
};

重寫(xiě)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); //鏈表實(shí)現(xiàn)的remove方法
        if(table[position].isEmpty()) { //刪除元素之后判斷鏈表是否變空
          table[position] = undefined;
        }
        return true;
      }
      current = current.next;
    }

    //檢查是否是第一個(gè)或者最后一個(gè)元素
    if(current.element.key === key) {
      table[position].remove(current.element);
      if(table[position].isEmpty()) {
        table[position] = undefined;
      }
      return true;
    }
  }
  return false;
}

線(xiàn)性探查

如果索引為index的位置已經(jīng)被占據(jù)了，就嘗試index+1的位置，以此類(lèi)推。

5的位置被占據(jù)，就尋找6的位置，6的位置被占據(jù)，就找7，7沒(méi)被占據(jù)就賦值(本應(yīng)該在位置5上，但是線(xiàn)性探查變成了位置7)

實(shí)現(xiàn)put(key, value)方法

this.put = function(key, value) {
  var position = loseloseHashTable(key);
  if(table[position] === undefined) { //這個(gè)位置沒(méi)有被占據(jù)
    table[position] = new valuePair(key, value);
  } else {
    var index = ++position; //尋找下一個(gè)位置
    while(table[index] !== undefined) { //被占據(jù)繼續(xù)尋找下一個(gè)位置
      index ++;
    }
    table[index] = new valuePair(key, value);
  }
};

實(shí)現(xiàn)get()方法

this.get = function(key) {
  var position = loseloseHashTable(key);
  if(table[position] !== undefined) {
    if(table[position].key === key) { //舉例位置5
      return table[position].value; //記號(hào)1
    } else {
      var index = ++position;
      while(table[index] !== undefined && (table[index] && table[index].key !== key)) { //該位置有元素但是不是要尋找的元素
        index ++; //索引增加
      }
      if(table[index] && table[index].key === key) { //確認(rèn)正確性
        return table[index].value; //找到7 //記號(hào)2
      }
    }
  }
  return undefined;
};

實(shí)現(xiàn)remove()方法

只需要改變get方法的記號(hào)1和記號(hào)2的位置代碼即可
改為table[index] = undefined;

更好的散列函數(shù)

var djb2HashCode = function(key) {
  var hash = 5381; //初始化一個(gè)hash變量并賦值為一個(gè)質(zhì)數(shù)5381
  for(var i = 0; i < key.length; i++) { //遍歷
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
}

相比來(lái)說(shuō)，沖突會(huì)變少很多~

GPU云服務(wù)器云服務(wù)器散列表 python 散列表簡(jiǎn)單的深度學(xué)習(xí) 最簡(jiǎn)單的深度學(xué)習(xí)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/88223.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

lindroid

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow鏡像下載

閱讀 1437·2023-04-25 18:34
關(guān)于程序員的「年齡歧視」問(wèn)題，程序員的年齡天花板難道是35歲嗎？

閱讀 3547·2021-11-19 09:40
MySQL-Front設(shè)置中文

閱讀 2853·2021-11-17 09:33
Python基礎(chǔ)（四）：數(shù)據(jù)類(lèi)型

閱讀 3001·2021-11-12 10:36
Python3，68個(gè)內(nèi)置庫(kù)函數(shù)詳解，進(jìn)階必備，必須收藏！！!

閱讀 2866·2021-09-26 09:55
SpinServers：美國(guó)服務(wù)器促銷(xiāo)/2*e5-2630Lv2/64g內(nèi)存/1.6T ssd/10

閱讀 2683·2021-08-05 10:03
HTML&&CSS基礎(chǔ)知識(shí)點(diǎn)整理

閱讀 2548·2019-08-30 15:54
CSS 圖像拼合技術(shù)（雪碧圖）

閱讀 2895·2019-08-30 15:54

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

我對(duì)JS散列表的簡(jiǎn)單學(xué)習(xí)

相關(guān)文章

***我對(duì)JS字典的簡(jiǎn)單學(xué)習(xí)***

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表

《Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「字典和散列表」

***我對(duì)JS鏈表的簡(jiǎn)單學(xué)習(xí)***

Map集合、散列表、紅黑樹(shù)介紹

發(fā)表評(píng)論

0條評(píng)論

lindroid

男|高級(jí)講師

TA的文章

tensorflow鏡像下載

關(guān)于程序員的「年齡歧視」問(wèn)題，程序員的年齡天花板難道是35歲嗎？

MySQL-Front設(shè)置中文

Python基礎(chǔ)（四）：數(shù)據(jù)類(lèi)型

Python3，68個(gè)內(nèi)置庫(kù)函數(shù)詳解，進(jìn)階必備，必須收藏！！!

SpinServers：美國(guó)服務(wù)器促銷(xiāo)/2*e5-2630Lv2/64g內(nèi)存/1.6T ssd/10

HTML&&CSS基礎(chǔ)知識(shí)點(diǎn)整理

CSS 圖像拼合技術(shù)（雪碧圖）

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

我對(duì)JS散列表的簡(jiǎn)單學(xué)習(xí)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！