JS中數據結構之散列表

散列是一種常用的數據存儲技術，散列后的數據可以快速地插入或取用。散列使用的數據結構叫做散列表。在散列表上插入、刪除和取用數據都非常快。

下面的散列表是基于數組進行設計的，數組的長度是預先設定的，如有需要，可以隨時增加。所有元素根據和該元素對應的鍵，保存在數組的特定位置。使用散列表存儲數據時，通過一個散列函數將鍵映射為一個數字，這個數字的范圍是0到散列表的長度。

散列函數會將每個鍵值映射為一個唯一的數組索引。然而，鍵的數量是無限的，數組的長度是有限的，一個更現實的目標是讓散列函數盡量將鍵均勻地映射到數組中。

即使使用一個高效的散列函數，仍然存在將兩個鍵映射成同一個值的可能，這種現象稱為碰撞（collision），當碰撞發生時，我們需要利用一定的方法去解決碰撞。

對數組大小常見的限制是：數組長度應該是一個質數。

HashTable類

使用 HashTable 類來表示散列表，該類包含計算散列值的方法、向散列中插入數據的方法、從散列表中讀取數據的方法、顯示散列表中數據分布等方法。

function HashTable() {
　　this.table = new Array(137);
　　this.simpleHash = simpleHash;
　　this.showDistro = showDistro;
　　this.put = put;
　　this.get = get;
　　this.buildChains = buildChains;
}

散列函數

散列函數的選擇依賴于鍵值的數據類型。如果鍵是整型，最簡單的散列函數就是以數組的長度對鍵取余，這種散列方式稱為除留余數法。

選擇針對字符串類型的散列函數比較困難

簡單的散列函數：字符串中每個字符的 ASCII 碼值相加然后再除以數組長度，將得出的余數做為散列值。

function simpleHash(data) {
　　var total = 0;
　　for (var i = 0; i < data.length; ++i) {
　　　　total += data.charCodeAt(i);
　　}
　　return total % this.table.length;
}

put() 和 showDistro()，一個用來將數據存入散列表，一個用來顯示散列表中的數據

function put(data) {
　　var pos = this.simpleHash(data);
　　this.table[pos] = data;
}

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

使用簡答的散列函數 simpleHash() 時數據并不是均勻分布的，而是向數組的兩端集中，并且數據很大概率將會產生碰撞而不會全部顯示出來。

更好的散列函數：霍納算法是一種比較好的散列函數算法，計算時仍然先計算字符串中各字符的 ASCII 碼值，不過求和時每次要乘以一個質數。

為了避免碰撞，首先要確保散列表中用來存儲數據的數組其大小是個質數。這一點和計算散列值時使用的取余運算有關。數組的長度應該在 100 以上，這是為了讓數據在散列表中分布得更加均勻。

function betterHash(string, arr) {
　　const H = 37;  //質數
　　var total = 0;
　　for (var i = 0; i < string.length; ++i) {
　　　　total += H * total + string.charCodeAt(i);
　　}
　　total = total % arr.length;
　　return parseInt(total);
}

接受鍵和數據作為參數的put() 方法

function put(key, data) {
　　var pos = this.betterHash(key);  //使用更好的散列函數
　　this.table[pos] = data;
}

get() 方法讀取存儲在散列表中的數據

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

碰撞處理

當散列函數對于不同的輸入產生同樣的散列值時，就產生了碰撞。下面是兩種碰撞解決辦法：開鏈法和線性探測法。

開鏈法：當碰撞發生時，仍然將鍵存儲到通過散列算法產生的索引位置上，但實際上，每個數組元素又是一個新的數據結構，比如另一個數組，這樣就能存儲多個鍵了（即用二維數組實現）。

buildChains() 函數創建二維數組

function buildChains() {
　　for (var i = 0; i < this.table.length; ++i) {
　　　　this.table[i] = new Array();
　　}
}

使用了開鏈法后，要重新定義 put() 和 get() 方法。

新的put() 方法將鍵值散列，散列后的值對應數組中的一個位置，先嘗試將數據放到該位置上的數組中的第一個單元格，如果該單元格里已經有數據了，put() 方法會搜索下一個位置，直到找到能放置數據的單元格，并把數據存儲進去。

它既保存數據，也保存鍵值。該方法使用鏈中兩個連續的單元格，第一個用來保存鍵值，第二個用來保存數據。

function put(key, data) {
  var pos = this.betterHash(key);
  var index = 0;
  if (this.table[pos][index] == undefined) {
    this.table[pos][index] = key;
    this.table[pos][index + 1] = data;
  } else {
    while (this.table[pos][index] != undefined) {
      ++index;
    }
    this.table[pos][index] = key;
    this.table[pos][index + 1] = data;
  }
}

新的 get() 方法先對鍵值散列，根據散列后的值找到散列表中相應的位置，然后搜索該位置上的鏈，直到找到鍵值。如果找到，就將緊跟在鍵值后面的數據返回；如果沒找到，就返回 undefined

function get(key) {
  var index = 0;
  var pos = this.betterHash(key);
  if (this.table[pos][index] == key) {
    return this.table[pos][index + 1];
  } else {
    while (this.table[pos][index] != key) {
      index += 2;
    }
    return this.table[pos][index + 1];
  }
  return undefined;
}

線性探測法：線性探測法隸屬于一種更一般化的散列技術：開放尋址散列。當發生碰撞時，線性探測法檢查散列表中的下一個位置是否為空。如果為空，就將數據存入該位置；如果不為空，則繼續檢查下一個位置，直到找到一個空的位置為止。

當存儲數據使用的數組特別大時，選擇線性探測法要比開鏈法好。如果數組的大小是待存儲數據個數的 1.5 倍，那就使用開鏈法；如果數組的大小是待存儲數據的兩倍及兩倍以上時，那么使用線性探測法。

使用線性探測法需要為 HashTable 類增加一個新的數組，用來存儲數據。數組 table 和 values 并行工作，當將一個鍵值保存到數組 table 中時，將數據存入數組 values 中相應的位置上。即在 HashTable 的構造函數中加入下面一行代碼： this.values = []

重寫 put() 和 get() 方法。

function put(key, data) {
  var pos = this.betterHash(key);
  if (this.table[pos] == undefined) {
    this.table[pos] = key;
    this.values[pos] = data;
  } else {
    while (this.table[pos] != undefined) {
      pos++;
    }
    this.table[pos] = key;
    this.values[pos] = data;
  }
}

function get(key) {
  var hash = this.betterHash(key);
  for (var i = hash; this.table[hash] != undefined; i++) {
    if (this.table[hash] == key) {
      return this.values[hash];
    }
  }
  return undefined;
}

posted @ 2019-01-18 17:17 wenxuehai 閱讀(1683) 評論(0) 收藏舉報

刷新頁面返回頂部

提升自己，才有選擇的能力和勇氣

JS中數據結構之散列表

公告