前端学数据结构之字典和散列表

字典

集合表示一组互不相同的元素（不重复的元素）。在字典中，存储的是 [键，值] 对，其中键名是用来查询特定元素的。字典和集合很相似，集合以 [值，值] 的形式存储元素，字典则是以 [键，值] 的形式来存储元素。字典也称作映射。

字典如同 ES6 中的 Map 类。

相关功能

set(key,value)：向字典中添加新元素。remove(key)：通过使用键值来从字典中移除键值对应的数据值。has(key)：如果某个键值存在于这个字典中，则返回 true，反之则返回 false。get(key)：通过键值查找特定的数值并返回。clear()：将这个字典中的所有元素全部删除。size()：返回字典所包含元素的数量。与数组的 length 属性类似。keys()：将字典所包含的所有键名以数组形式返回。values()：将字典所包含的所有数值以数组形式返回。

代码

function Dictionary(){var items = {};

  // 添加
  this.set = function(key, value){items[key] = value; 
  };

  // 删除
  this.delete = function(key){if (this.has(key)){delete items[key];
          return true;
      }
      return false;
  };

  // 判断是否有某个 key 值
  this.has = function(key){return key in items;};

  // 通过某个 key 获取 value
  this.get = function(key) {return this.has(key) ? items[key] : undefined;
  };

  // 清楚
  this.clear = function(){items = {};
  };

  // 长度
  this.size = function(){return Object.keys(items).length;
  };

  // 键
  this.keys = function(){return Object.keys(items);
  };

  // 值
  this.values = function(){return Object.values(items);
  };

  this.each = function(fn) {for (var k in items) {if (this.has(k)) {fn(k, items[k]);
          }
      }
  };

  // 字典
  this.getItems = function(){return items;}
}

验证

var dictionary = new Dictionary(); 
dictionary.set('Gandalf', 'gandalf@email.com'); 
dictionary.set('John', 'johnsnow@email.com'); 
dictionary.set('Tyrion', 'tyrion@email.com');
console.log(dictionary.has('Gandalf')); // true
console.log(dictionary.size()); // 3
console.log(dictionary.keys()); // ["Gandalf", "John", "Tyrion"]
console.log(dictionary.values()); // ["gandalf@email.com", "johnsnow@email.com", "tyrion@email.com"] 
console.log(dictionary.get('Tyrion')); // tyrion@email.com
dictionary.delete('John');
console.log(dictionary.keys()); // ["Gandalf", "Tyrion"] 
console.log(dictionary.values());// ["gandalf@email.com", "tyrion@email.com"]
console.log(dictionary.getItems()); // Object {Gandalf: "gandalf@email.com", Tyrion: "tyrion@email.com"}

散列表

一、哈希表

1、概念

   哈希表 (Hash Table) 也叫散列表，是依据关键码值（Key Value）而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来訪问记录，以加快查找的速度。

这个映射函数就做散列函数。存放记录的数组叫做散列表。

2、散列存储的基本思路

 以数据中每一个元素的 keyword 为自变量。通过散列函数 H（k）计算出函数值，以该函数值作为一块连续存储空间的的单元地址，将该元素存储到函数值相应的单元中。

3、哈希表查找的时间复杂度

 哈希表存储的是键值对，其查找的时间复杂度与元素数量多少无关。哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问问元素的，因此，哈希表查找的时间复杂度为 O（1）。

二、经常使用的哈希函数

1. 直接寻址法

取 keyword 或者 keyword 的某个线性函数值作为哈希地址, 即 H(Key)=Key 或者 H(Key)=a*Key+b(a,b 为整数), 这样的散列函数也叫做自身函数. 假设 H(Key)的哈希地址上已经有值了, 那么就往下一个位置找, 知道找到 H(Key)的位置没有值了就把元素放进去.

2. 数字分析法

分析一组数据, 比方一组员工的出生年月, 这时我们发现出生年月的前几位数字一般都同样, 因此, 出现冲突的概率就会非常大, 可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大, 假设利用后面的几位数字来构造散列地址, 则冲突的几率则会明显减少. 因此数字分析法就是找出数字的规律, 尽可能利用这些数据来构造冲突几率较低的散列地址.

3. 平方取中法

取 keyword 平方后的中间几位作为散列地址. 一个数的平方值的中间几位和数的每一位都有关。

因此，有平方取中法得到的哈希地址同 keyword 的每一位都有关。是的哈希地址具有较好的分散性。

该方法适用于 keyword 中的每一位取值都不够分散或者较分散的位数小于哈希地址所须要的位数的情况。

4. 折叠法

折叠法即将 keyword 切割成位数同样的几部分, 最后一部分位数能够不同, 然后取这几部分的叠加和 (注意: 叠加和时，去除进位) 作为散列地址. 数位叠加能够有移位叠加和间界叠加两种方法. 移位叠加是将切割后的每一部分的最低位对齐, 然后相加; 间界叠加是从一端向还有一端沿切割界来回折叠, 然后对齐相加.

5. 随机数法

选择一个随机数, 去 keyword 的随机值作为散列地址, 通经常使用于 keyword 长度不同的场合.

6. 除留余数法

取 keyword 被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址. 即 H(Key)=Key MOD p,p<=m. 不仅能够对 keyword 直接取模, 也可在折叠、平方取中等运算之后取模。对 p 的选择非常重要，一般取素数或 m，若 p 选得不好。则非常 easy 产生冲突。

一般 p 取值为表的长度为表的长度。

HashTable 类

也叫 HashMap 类，是 Dictionary 类的一种散列表实现方式

散列值比较大，可以用算出的散列值除以一个数取余

散列值可能相同，存在冲突，处理冲突

处理冲突有几种方法：分离链接、线性探查和双散列法

分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在 HashTable 实例之外还需要额外的存储空间

// 链表
function LinkedList() {let Node = function(element){

        this.element = element;
        this.next = null;
    };

    let length = 0;
    let head = null;

    this.append = function(element){let node = new Node(element),
            current;

        if (head === null){head = node;} else {

            current = head;
            while(current.next){current = current.next;}

            current.next = node;
        }

        length++; 
    };

    this.isEmpty = function() {return length === 0;};

    this.getHead = function(){return head;};
    
    
    this.toString = function(){

        let current = head,
            string = '';

        while (current) {string += current.element + (current.next ? ',' : '');
            current = current.next;
        }
        return string;

    };
}


function HashTableSeparateChaining(){
    // 散列表
    var table = [];
    // 使用 append 方法向 LinkedList 实例中添加一个 ValuePair 实例（键和值）var ValuePair = function(key, value){
     this.key = key;
     this.value = value;
     this.toString = function() {return '[' + this.key + '-' + this.value + ']'; 
      }
    };
    // 散列函数
    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {hash += key.charCodeAt(i);
        }
        return hash % 37;
    };

    var hashCode = function(key){return loseloseHashCode(key);
    };
    
    // 添加
    this.put = function(key, value){var position = hashCode(key);
        console.log(position + '-' + key);

        if (table[position] == undefined) {table[position] = new LinkedList();}
        table[position].append(new ValuePair(key, value));
    };
    // 查找
    this.get = function(key) {var position = hashCode(key);

        if (table[position] !== undefined  && !table[position].isEmpty()){

            // 获取头节点
            var current = table[position].getHead();

            do {if (current.element.key === key){return current.element.value;}
                current = current.next;
            } while(current);
        }
        return undefined;
    };
    
    // 删除
    this.remove = function(key){var position = hashCode(key);

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

           // 获取头节点
            var current = table[position].getHead();

            do {if (current.element.key === key){table[position].remove(current.element);
                    if (table[position].isEmpty()){table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;
            } while(current);
        }

        return false;
    };

    // 表里所有数据
    this.print = function() {for (var i = 0; i < table.length; ++i) {if (table[i] !== undefined) {console.log(i+'----'+table[i].toString());
            }
        }
    };
}

验证

var hash = new HashTableSeparateChaining();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jonathan', 'jonathan@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com');

hash.print();

线性探查

另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引为 index 的位置已经被占据了，就尝试 index+ 1 的位置。如果 index+ 1 的位置也被占据了，就尝试 index+ 2 的位置

function HashLinearProbing(){var table = [];
    var ValuePair = function(key, value){
        this.key = key;
        this.value = value;

        this.toString = function() {return '[' + this.key + '-' + this.value + ']';
        }
    };
    // 散列函数
    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {hash += key.charCodeAt(i);
        }
        return hash % 37;
    };

    var hashCode = function(key){return loseloseHashCode(key);
    };
    
    // 添加
    this.put = function(key, value){var position = hashCode(key);
        console.log(position + '-' + key);

        if (table[position] == undefined) {table[position] = new ValuePair(key, value);
        } else {
            var index = ++position;
            while (table[index] != undefined){index++;}
            table[index] = new ValuePair(key, value);
        }
    };

    // 删除
    this.remove = function(key){var position = hashCode(key);

        if (table[position] !== undefined){if (table[position].key === key) {table[position] = undefined;
            } else {
                var index = ++position;
                while (table[index] === undefined || table[index].key !== key){index++;}
                if (table[index].key === key) {table[index] = undefined;
                }
            }
        }
    };

    // 输出
    this.print = function() {for (var i = 0; i < table.length; ++i) {if (table[i] !== undefined) {console.log(i + '->' + table[i].toString());
            }
        }
    };
}

5 -> [Jonathan - jonathan@email.com]
6 -> [Jamie - jamie@email.com]
7 -> [Sue - sue@email.com]
10 -> [Nathan - nathan@email.com]
13 -> [Donnie - donnie@email.com]
14 -> [Ana - ana@email.com]
16 -> [Tyrion - tyrion@email.com]
17 -> [Aaron - aaron@email.com]
19 -> [Gandalf - gandalf@email.com]
29 -> [John - johnsnow@email.com]
32 -> [Mindy - mindy@email.com]
33 -> [Paul - paul@email.com]

更好的散列函数

个可以实现的比“loselose”更好的散列函数是 djb2：

var djb2HashCode = function (key) {var hash = 5381; //{1}
 for (var i = 0; i < key.length; i++) {//{2}
     hash = hash * 33 + key.charCodeAt(i); //{3}
 }
 return hash % 1000; //{4}
};