散列的概念和用途

散列的概念和用途

• 散列后的数据可以快速插入取用。

• 在散列表上插入、删除和取用数据非常快，但是查找数据却效率低下，比如查找一组数据中的最大值和最小值。

• JavaScript 散列表基于数组设计，理想情况下散列函数会将每一个键值映射为唯一的数组索引，数组长度有限制，更现实的策略是将健均匀分布。

散列的一些关键点

• 数组长度是预先设定的，可以随时增加，所有元素根据和该元素对应的健，保存在数组的特定位置。

• 即使使用高效的散列函数，仍然存在两个键值相同的情况，这种现象称为碰撞。

• 数组的长度应该是一个质数，所有的策略都基于碰撞。

• 解决散列冲突的方法有：

  • 开链法：两个键相同保存位置一样。开辟第二个数组，也称第二个数组为链。

  • 线性探测法属于开放寻址散列，查找散列位置，如果当前位置没有继续寻找下一个位置。存储数据较大比较合适。数据大小 >= 1.5*数据（开链法），数据大小 >= 2*数据（线性探测法）。

• 更好的散列函数：djb2。

var djb2HashCode = function(key) {
  var hash = 5381;
  for (var i = 0; i < key.length; i++) {
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
};

散列的代码实现

function HashTable() {
  this.table = new Array(137);
  this.simpleHash = simpleHash;
  this.betterHash = betterHash;
  this.buildChains = buildChains;
  this.put = put;
  this.get = get;
  this.showHashTable = showHashTable;
}

// 简单的散列函数，使用除留余数法
function simpleHash(data) {
  var hash = 0;
  for (var i = 0; i < data.length; i++) {
    hash += data.charCodeAt(i);
  }
  return hash % this.table.length;
}

// 分布更均匀的散列函数
function betterHash(data) {
  var H = 31; // 质数
  var hash = 0;
  for (var i = 0; i < data.length; i++) {
    hash += H * hash + data.charCodeAt(i);
  }
  if (hash < 0) {
    hash += this.table.length - 1;
  }
  return hash % this.table.length;
}

// 开链法
function buildChains() {
  for (var i = 0; i < this.table.length; i++) {
    this.table[i] = new Array();
  }
}

// 插入数据
function put(data) {
  var pos = this.simpleHash(data);
  this.table[pos] = data;

  // var pos = this.betterHash(data);
  // this.table[pos] = data;

  // 开链法
  // var pos = this.simpleHash(data);
  // var index = 0;
  // if (!this.table[pos][index]) {
  //   this.table[pos][index] = data;
  //   index++;
  // } else {
  //   while (this.table[pos][index]) {
  //     index++;
  //   }
  //   this.table[pos][index] = data;
  // }

  // 线性探测法
  // var pos = this.simpleHash(data);
  // if (!this.table[pos]) {
  //   this.table[pos] = data;
  // } else {
  //   while (this.table[pos]) {
  //     pos++;
  //   }
  //   this.table[pos] = data;
  // }
}

// 取出数据
function get(data) {
  return this.table[this.simpleHash(data)];

  // 配合线性探测法
  // var pos = this.simpleHash(data);
  // console.log(data + '本来的位置是：' + pos);
  // for (var i = pos; i < this.table.length; i++) {
  //   if (this.table[i] === data) {
  //     return i;
  //   }
  // }
  // return -1;
}

// 打印整个散列表的数据
function showHashTable() {
  var n = 0;
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i]) {
      console.log("键 " + i + " 对应的值是：" + this.table[i]);
    }
  }

  // 配合开链法
  // var n = 0;
  // for (var i = 0; i < this.table.length; i++) {
  //   if (this.table[i][0]) {
  //     console.log('键 ' + i + ' 对应的值是：' + this.table[i]);
  //   }
  // }
}

var hashTable = new HashTable();

// 开链
// hashTable.buildChains();

hashTable.put("first");
hashTable.put("study");
hashTable.put("student");
hashTable.put("cool");
hashTable.put("ice");
hashTable.put("china");
hashTable.put("nicha");

// console.log('使用线性探测法之后 nicha 的位置是：' + hashTable.get('nicha'));

hashTable.showHashTable();