数据结构 散列表 HashTable

散列算法的作用是尽可能快的在数据结构中找到一个值，使用散列表可以直接直到值的具体位置，因此能够快速检索到该值，散列函数的作用是给定一个键名，然后返回键值在表中的位置。

哈希表用到的哈希函数，一方面要能尽量把 key 均匀散布在表空间中（从而尽量减少冲突），另一方面又要有尽量快的计算速度。

无论如何，原理所限，哈希表中碰撞无法绝对避免。 当碰撞发生时，就不得不使用开链表法或再散列法存储冲突数据；而这必将影响哈希表的性能。

散列表的功能

增加，移除，检索

散列表的实现

// Hashtable.js

// 引入链表数据结构
const LinkedList = require("./Linkedlist.js");

// 构造一个散列函数
const loseloseHashCode = function (key, size) {
  const hash = 5381; // magic number
  const size = size || 1543; // hash size
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 33 + key.charCodeAt(i)) % size; // 这个公式可以让结果尽可能的让这个数和2的32次方互质
  }
  return hash; // 设置散列长度
};

// 构造一个键值对
var ValuePair = function (key, value) {
  this.key = key;
  this.value = value;
  this.toString = function () {
    return "[" + this.key + "," + this.value + "]";
  };
};

function HashTable(length) {
  this.table = [];
}

增加

HashTable.prototype.put = function (key, value) {
  const table = this.table;
  const position = loseloseHashCode(key);
  if (table[position] == undefined) {
    table[position] = new LinkedList();
  }
  table[position].append(new ValuePair(key, value));
};

删除

HashTable.prototype.remove = function (key) {
  const table = this.table;
  const position = loseloseHashCode(key);
  if (table[position] !== undefined) {
    let current = table[position].getHead();
    // 链表长度不为一 进入循环
    while (current.next) {
      if (current.item.key === key) {
        table[position].remove(key);
        // 检查链表是否为空
        if (table[position].isEmpty()) {
          table[position] = undefined;
        }
        return true;
      }
      //移动指针
      current = current.next;
    }
    // 检查第一个或最后一个
    if (current.item.key === key) {
      table[position].remove(key);
      if (table[position].isEmpty()) {
        table[position] = undefined;
      }
      return true;
    }
  }
  return false;
};

查找

HashTable.prototype.get = function (key) {
  const table = this.table;
  const position = loseloseHashCode(key);
  if (table[position] !== undefined) {
    let current = table[position].getHead();
    while (current.next) {
      if (current.item.key === key) {
        return current.item.value;
      }
      current = current.next;
    }
    // 检查第一个或最后一个
    if (current.item.key === key) {
      return current.item.value;
    }
    return undefined;
  }
};

修改

HashTable.prototype.set = function (key, value) {};

测试

// HashTable.test.js
const hash = new HashTable(1024);
hash.put("bob", "bob@qq.com");
hash.put("tom", "tom@126.com");
hash.put("john", "john@163.com");
console.log(hash.get("bob")); // bob@qq.com
hash.remove("bob");
console.log(hash.get("bob")); // undefined