資料結構學習-字典和散清單

集合、字典和散清單都可以存儲不重複的值。在集合中，存儲的是每個值本身。而在字典中，存儲的是鍵值對（也稱作字典映射）。在散清單中存儲的也是鍵值對（也稱作散列映射），但是兩種資料結構的實作方式略有不同

### 字典

ES6提供了Map類，也就是上面說的字典，Map類的具體操作可[移步至此](https://blog.86886.wang/posts/5b2324f88493c32a8e81fc99)

### 散清單

散清單也叫 HashTable 類，或者 HashMap 類，它是字典的一種散清單實作方式。要想建立散清單，需要先實作雜湊演算法，雜湊演算法的作用是盡可能快地在資料結構中找到一個值。在之前實作的資料結構中，擷取一個值需要周遊整個資料結構，找到比對項傳回結果。如果使用散列函數，就可以知道值的具體位置，是以能夠快速檢索到該值，散列函數的作用是給定一個鍵值，然後傳回值在表中的位址

#### 散列函數

```js

var loseloseHashCode = function (key) {

var hash = 0;

for (var i = 0; i < key.length; i++) {

hash += key.charCodeAt(i); //每個字元的ASCII碼值的和

}

return hash % 37; // 為了得到比較小的數值，使用hash值和一個任意數做除法，求餘數

};

```

這個散列函數接收一個key值，計算key值對應ASCII碼值的和，然後傳回一個計算後hash值。

#### 建立散清單

散清單要實作以下基本方法

put(key,value) ：向散清單增加一個新的項（也能更新散清單）

remove(key) ：根據鍵值從散清單中移除值

get(key) ：傳回根據鍵值檢索到的特定的值

function HashTable() {

var table = [];

// 新添加的元素在數組内部是用 位置:值 形式存儲的

this.put = function(key, value) {

var position = loseloseHashCode(key);

console.log(position + ' - ' + key);

table[position] = value;

// 基于位置查找元素

this.get = function (key) {

return table[loseloseHashCode(key)];

};

// 移除元素隻需要求出元素的位置，并指派為undefined

// 這裡不能像數組一樣直接删除，因為會把位置資訊也删除

this.remove = function(key) {

table[loseloseHashCode(key)] = undefined;

}

#### 使用 HashTable 類

var hash = new HashTable();

hash.put('Gandalf', '[email protected]');

hash.put('John', '[email protected]');

hash.put('Tyrion', '[email protected]');

// 19 - Gandalf

// 29 - John

// 16 - Tyrion

散清單内部存儲示意圖


#### 散清單中的沖突

其實上面實作的散清單是有問題的，因為散列函數是基于ASCLL碼計算的，這麼做很容易導緻由于碼值相同而沖突。比如`Tyrion`和`Aaron`的計算結果都是16，但很顯然這是兩個不同的資訊。

一個解決方法是使用線性探索，當向表中某個位置加入一個新元素的時候，如果索引為index的位置已經被占據了，就嘗試index+1的位置。如果index+1的位置也被占據了，就嘗試index+2的位置，以此類推。

具體實作

// 把key和value儲存為一個獨立的對象

var ValuePair = function(key, value) {

this.key = key;

this.value = value;

// 重寫toString，友善檢視執行結果

this.toString = function() {

return '[' + this.key + ' - ' + this.value + ']';

if (table[position] == undefined) { // 位置沒有被占用

table[position] = new ValuePair(key, value);

} else { // 位置被占用，hash值進行遞增

var index = ++position;

while (table[index] != undefined) {

index++;

}

table[index] = new ValuePair(key, value);

}

this.get = function(key) {

if (table[position] !== undefined) { // 找到元素後，需要判斷下key值是否正确

if (table[position].key === key) {

return table[position].value;

} else {

var index = ++position;

while (table[index] === undefined ||

table[index].key !== key) {

index++;

}

if (table[index].key === key) {

return table[index].value;

return undefined;

if (table[position] !== undefined) {

table[index] = undefined; // 指派undefined

table[index] = undefined; // 指派undefined

this.print = function() {

for (var i = 0; i < table.length; ++i) {

if (table[i] !== undefined) {

console.log(i + ": " + table[i]); // 字元串拼接會調用對象的toString方法

測試結果

hash.put('Aaron', '[email protected]');

hash.print()

// 16: [Tyrion - [email protected]]

// 17: [Aaron - [email protected]]

// 29: [John - [email protected]]

部落格: https://blog.86886.wang

GitHub: https://github.com/wmui