我對JS散列表的簡單學習

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

摘要：對散列表的簡單學習類也叫類，是類的一種散列表實現方式。鍵值散列函數散列值形成散列表地址數據鍵值對相關操作方法創(chuàng)建一個散列表實現一個散列函數，即將碼值相加的方法。

對JS散列表的簡單學習

HashTable類也叫HashMap類，是Dictionary類的一種散列表實現方式。

散列算法的作用是盡可能快的在數據結構中找到一個值。

在之前的學習中，如果你想要獲得數據結構中的一個值，需要遍歷整個數據結構來找到它。如果使用散列函數，就能知道具體位置，也就能夠快速找到該值。

使用最常見的散列函數--‘lose lose’散列函數，簡單的將每個鍵值中的每個字母的ASCII碼值相加，將得到的散列值作為地址。

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

地址	數據鍵值對
[399]	john/john@email.com
...
[685]	gandalf/@email.com

相關操作方法

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

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
};

具體使用方法這里就不贅述了，就是方法的調用。

沖突怎么辦？

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

分離鏈接

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

地址	鏈表存儲數據
[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) { //被占據繼續(xù)尋找下一個位置
      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 散列表簡單的深度學習最簡單的深度學習

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/88223.html

我對JS字典的簡單學習

摘要：我對字典的簡單學習字典的概念集合字典和散列表都可以來存儲不重復的值。字典也被稱為映射。中有集合類的實現，也有字典類的實現。相關操作方法實現方法，判斷某個鍵值是否在這個字典中，有則返回。實現方法，將字典所有的值以數組的形式返回。我對JS字典的簡單學習字典的概念集合、字典和散列表都可以來存儲不重復的值。在集合中我們使用[值,值]來保存，在字典和散列表中使用[鍵,值]來存儲數據。字典...

CntChen 2019-08-20 15:35 評論0 收藏0
學習數據結構與算法之字典和散列表

摘要：小結實現了字典和哈希表感覺沒有想象中那么困難，當然這還是開始。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算法之二叉搜索樹字典不是新華字典哦，這里的字典也稱作_映射_，是一種數據結構，跟set集合很相似的一種數據結構，都可以用來...

Heier 2019-08-21 11:52 評論0 收藏0
《Javascript數據結構和算法》筆記-「字典和散列表」

摘要：我經常在業(yè)務代碼中把數據處理成這種字典的數據結構獲取的方法哈希表在學習了類之后，我們會學習散列表，也就是哈希表。《Javascript數據結構和算法》筆記-「字典和散列表」集合、字典、散列表存儲的都是「不重復」的數據結構集合：我們更關注每一個元素的值，并把其作為主要元素字典：我們用[鍵,值]的形式來存儲數據散列表：跟字典類似，也會是用[鍵,值]的形式來存儲數據但是「字...

wenyiweb 2019-08-26 13:23 評論0 收藏0
我對JS鏈表的簡單學習

摘要：我對鏈表的學習什么是鏈表要存儲多個元素，數組可能是最常用的數據結構。鏈表的學習創(chuàng)建一個鏈表各種方法表示要加入列表的項，它包含一個屬性以及一個屬性，表示要添加到列表的值，表示指向列表下一個節(jié)點項的指針。我對JS鏈表的學習什么是鏈表要存儲多個元素，數組可能是最常用的數據結構。這種數據結構非常方便，但是有一個缺點：從數組的起點或者中間插入或移除項的成本非常高，因為需要移動元素（比如你插...

余學文 2019-08-20 15:07 評論0 收藏0
Map集合、散列表、紅黑樹介紹

摘要：并且，我們的底層都是紅黑樹來實現的。紅黑樹是一種平衡二叉樹因此它沒有節(jié)點。前言聲明，本文用得是jdk1.8 前面已經講了Collection的總覽和剖析List集合： Collection總覽 List集合就這么簡單【源碼剖析】原本我是打算繼續(xù)將Collection下的Set集合的，結果看了源碼發(fā)現：Set集合實際上就是HashMap來構建的！ showImg(https:/...

2json 2019-08-15 15:20 評論0 收藏0