在Javascript中實現偽哈希表
了解數據結構的人應該都聽說過哈希表這種數據結構，它是一種典型的利用鍵值對存儲并檢索數據的一種非線性結構，又稱散列表或雜湊法。在一般的線性表結構中，數據的相對位置是隨機的，即數據和用于檢索的關鍵字之間不存在確定的關系，檢索數據時往往需要進行一系列的比較，最終找到要檢索的數據，這種方法往往建立在循環比較的機制上，利用時間的代價節省了空間，實現了數據的存儲和檢索功能。而哈希表則使用鍵值對進行數據的存儲，在數據的存儲位置和它的關鍵字之間建立了一一對應的關系，從而使每個關鍵字和結構中的一個***的存儲位置相對應，所以在檢索數據時，只需要根據這個對應關系便可快速定位到要查找的數據。
事實上，我們通常并不關心數據是如何存儲的，而關心的是我們在使用數據的時候是否方便，例如對數據進行排序、查找、替換等操作，由于這種操作是貫穿在整個應用程序始終的，因此對效率的要求也就很高了。一般的高級語言，如C和C的變種，都提供了用于存儲哈希表的數據結構，但在弱類型語言中，如javascript等腳本語言，本身并沒有直接提供類似于哈希表的這種結構，不過我們可以從數組出發，按照哈希表的原理自己打造一個腳本語言專有的哈希表數據結構。
我們知道，在數據中，可以通過下標直接定位到相應數據，也就是用于存儲數據的空間，數組的這種特性本身就決定了它可以被用來實現哈希算法，不過在C語言中，數組的下標只能是從0開始的整數，而不能為其它類型的數據，但在javascript中，我們可以借用“對象”這個概念，按照數組的特性來模擬哈希算法。因為在javascript中，對象其實就是屬性或方法的一個集合，于是我們可以構造一個Hashtable對象，它有key和value兩個屬性，自己編寫代碼來模擬一個完整的哈希表。下面是一段在javascript中實現哈希表的代碼：
2 {
3 this._hash = {};
4 this._count = 0;
5 this.add = function(key, value)
6 {
7 if (this._hash.hasOwnProperty(key)) return false;
8 else { this._hash[key] = value; this._count++; return true; }
9 }
10 this.remove = function(key) { delete this._hash[key]; this._count--; }
11 this.count = function() { return this._count; }
12 this.items = function(key) { if (this.contains(key)) return this._hash[key]; }
13 this.contains = function(key) { return this._hash.hasOwnProperty(key); }
14 this.clear = function() { this._hash = {}; this._count = 0; }
15 }
實現起來很簡單，我們在function中定義了一個_hash對象，該對象有一個屬性key，我們可以給這個屬性賦值，hasOwnProperty方法是javascript提供的方法，用于返回指定的對象中是否包含某個屬性。同時我們在該function中還定義了一個_count對象，用于記錄Hashtable中的數據個數，因為我們不想每次獲取Hashtable中的數據個數時都要通過一個內置的循環來計數，這樣開銷就會小一些，前面說了，哈希算法的一個基本特性就是效率高。delete語句在javascript中用于銷毀一個對象。
下面是使用該Hashtable的一些例子：
2
3 //向Hashtable中添加鍵值對
4 function FillData(arr) {
5 hashCompany.clear();
6
7 for (var i = 0; i ﹤ arr.length - 1; i++) {
8 if (arr[i] != "") {
9 t = arr[i].split("`");
10 if (t.length ﹥ 2) {
11 if (!hashCompany.contains(t[0].trim())) {
12 hashCompany.add(t[0].trim(), t[1]);
13 }
14 }
15 }
16 }
17 }
18
19 //遍歷Hashtable并取出值
20 function GetDataFromHash() {
21 var s;
22 if (hashCompany.count ﹥ 0) {
23 for (var i in hashCompany._hash) {
24 s += i + "|";
25 }
26 }
27
28 if (s.length ﹥ 0) {
29 s = s.substring(0, s.length - 2);
30 }
31
32 return s;
33 }
代碼比較簡單，這里就不再多加說明了，其中用到了一個trim函數，下面補上。
//采用正則表達式去除字符串兩端的空格，匿名函數用于擴展String對象的方法 |
哈希表在代碼中使用頻率很高，靈活使用哈希表可以簡化代碼并提供諸多方便，尤其是在存儲類似于數組的數據并且希望之后能夠方便檢索。將代碼保存于此，以備日后使用。
【編輯推薦】
