字典（也被稱為映射）和散列表是用來存儲唯一值的數(shù)據(jù)結構统倒。
在字典和散列表中都是用[鍵寨典，值]的形式存儲數(shù)據(jù)的。其中鍵名是用來查詢特定元素的房匆。
在ECMAScript 6中包含了Map類的實現(xiàn)耸成，也就是字典。在ECMAScript 6中的Map類型是一種存儲著許多鍵值對的有序列表坛缕，其中鍵名和對應的值支持所有的類型墓猎。和對象不太一樣，不會將鍵名強制轉換為字符串類型赚楚。
以ECMAScript 6中的Map類為基礎實現(xiàn)一個字典類毙沾。
function Dictionaries() {
var items = {};
this.set = function (key, value) {
//向字典中添加新元素
return items[key] = value;
};
this.remove = function (key) {
//通過鍵值從字典中移除元素
if(this.has(key)) {
delete items[key];
return true;
}
return false;
};
this.has = function (key) {
//判斷鍵值是否存在
return items.hasOwnProperty(key);
};
this.get = function (key) {
//通過鍵值獲取元素
return this.has(key) ? items[key] : undefined;
};
this.clear = function () {
//將字典中所有元素全部刪除
items = {};
};
this.size = function () {
//獲取字典所包含元素的數(shù)量
//有兼容問題
// return Object.keys(items).length;
//通用
var count = 0;
for(var key in items) {
if(items.hasOwnProperty(key)) {
count++;
}
}
return count;
};
this.keys = function () {
//獲取字典所包含的所有鍵值以數(shù)組形式返回
//有兼容問題
// return Object.keys(items);
//通用
var keys = [];
for (var key in items) {
if (items.hasOwnProperty(key)) {
keys.push(key);
}
}
return keys;
};
this.values = function () {
//獲取字典中所有包含的數(shù)值以數(shù)組形式返回
var values = [];
for (var key in items) {
if(items.hasOwnProperty(key)) {
values.push(items[key]);
}
}
return values;
};
}
var dictionaries = new Dictionaries();
dictionaries.set('name', 'Jason');
dictionaries.set('age', 23);
dictionaries.set('hobby', 'short story');
console.log(dictionaries.size()); //3
console.log(dictionaries.keys()); //[ 'name', 'age', 'hobby' ]
console.log(dictionaries.values()); //[ 'Jason', 23, 'short story' ]
散列表
HashTable類，也叫HashMap類宠页，是Dictionary類的一種散列表實現(xiàn)方式左胞。
散列算法的作用：是盡可能快的在數(shù)據(jù)結構中找到一個值寇仓。在數(shù)組中，通常獲得一個值烤宙，需要遍歷整個數(shù)據(jù)結構來找到他遍烦。如果使用散列函數(shù)，就能知道值的具體位置躺枕，因此能夠快速檢索到該值服猪。散列函數(shù)的作用是給定一個鍵值，然后返回值在表中的地址拐云。
創(chuàng)建一個散列表
function HashTable() {
var table = [];
var hashFunction = function (key) {
//散列函數(shù)罢猪，根據(jù)每個字符串的ASCII碼值的和得到
// 一個數(shù)字做為散列表項的Key值
var hash = 5381;
for (var i=0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i);
}
return hash % 1013;
};
this.put = function (key, value) {
//向散列表增加一個新的項目或者更新項
var position = hashFunction(key);
table[position] = value;
};
this.remove = function (key) {
//移除散列表中的某個項
table[hashFunction(key)] = undefined;
};
this.get = function (key) {
//獲取散列表中的某個項
return table[hashFunction(key)];
};
}
var hash = new HashTable();
hash.put('Jason', 'jason@email.com');
console.log(hash.get('Jason')); //jason@email.com
處理散列表中的沖突
哈希沖突：每一個鍵都對應有散列值，當不同的值在散列表中對應相同位置的時候叉瘩，就會產(chǎn)生沖突膳帕。
處理沖突的方法有：
分離鏈接：為散列表的每一個位置創(chuàng)建一個鏈表并將元素存儲在里面。
線性探查：當想向表中某個位置加入一個新元素時薇缅，如果索引為index的位置以及被占據(jù)危彩，就嘗試index+1的位置，如果也被占據(jù)就繼續(xù)+1泳桦，以此類推汤徽。
雙散列法。
