Skip to content

Latest commit

 

History

History
263 lines (255 loc) · 6.75 KB

07.md

File metadata and controls

263 lines (255 loc) · 6.75 KB

散列（哈希表）

散列是什么

  1. 散列是根据关键码而直接访问的数据结构，通过关键码映射到表中的一个位置，来加快查找速度

散列函数

{
  // 普通散列函数，存在碰撞问题
  function HashTable() {
    this.table = new Array(137);
    this.show = show;
    this.simpleHash = simpleHash;
    this.put = put;
  }
  let put = function(data) {
    var pos = this.simpleHash(data);
    this.table[pos] = data;
  };
  let simpleHash = function(data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data[i].charCodeAt();
    }
    return parseInt(total % this.table.length);
  };
  let show = function() {
    var result = "";
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i]) {
        result += i + ":" + this.table[i] + "\n";
      }
    }
    return result;
  };
  // 散列化字符串键
  let hash = new HashTable();
  var arr = ["egg", "koa", "express", "1001", "less", "sass", "stylus", "0101"];
  for (var i = 0; i < arr.length; i++) {
    hash.put(arr[i]);
  }
  console.log(hash.show());
  // 散列化整形键
  let random = function(min, max) {
    return parseInt(min + Math.random() * (max - min + 1));
  };
  let randomNumber = function() {
    var arr = new Array(10);
    for (var i = 0; i < 10; i++) {
      var str = "";
      for (var j = 0; j < 9; j++) {
        str += random(1, 9) + "";
      }
      arr[i] = str + random(10, 99);
    }
    return arr;
  };
  var nums = randomNumber();
  let hash = new HashTable();
  console.log(nums.length);
  for (var i = 0; i < nums.length; i++) {
    hash.put(nums[i]);
  }
  console.log(hash.show());
}

散列会碰见的问题

  1. 存在两个输入值对应到同一个输出值，也就是碰撞
  2. 输出值的不均匀分布

碰撞问题的解决

  • 避免碰撞的条件
    • 散列列表中存储数据的数组大小是一个质数
    • 数组的长度应该在 100 以上，保证散列列表分布均匀
  • 解决碰撞的方法
    • 霍纳算法：更好的计算散列值，保证散列值不重复
    function HashTable() {
  this.table = new Array(137);
  this.show = show;
  this.betterHash = betterHash;
  this.put = put;
  this.find = find;
}
let put = function(data) {
  var pos = this.betterHash(data);
  this.table[pos] = data;
};
// 防止碰撞
let betterHash = function(data) {
  var total = 0;
  var H = 37;
  var result;
  for (var i = 0; i < data.length; i++) {
    total += H * total + data[i].charCodeAt();
  }
  if (total < 0) {
    total = this.table.length - 1;
  }
  result = parseInt(total % this.table.length);
  return result;
};
let show = function() {
  var result = "";
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i]) {
      result += i + ":" + this.table[i] + "\n";
    }
  }
  return result;
};
let find = function(data) {
  return { [this.betterHash(data)]: data };
};
// 散列化字符串键
let hash = new HashTable();
var arr = ["egg", "koa", "express", "1001", "less", "sass", "stylus", "0101"];
for (var i = 0; i < arr.length; i++) {
  hash.put(arr[i]);
}
console.log(hash.show());
console.log(hash.find("express"));
// 散列化整形键
let random = function(min, max) {
  return parseInt(min + Math.random() * (max - min + 1));
};
let randomNumber = function() {
  var arr = new Array(10);
  for (var i = 0; i < 10; i++) {
    var str = "";
    for (var j = 0; j < 9; j++) {
      str += random(1, 9) + "";
    }
    arr[i] = str + random(10, 99);
  }
  return arr;
};
var nums = randomNumber();
let hash = new HashTable();
console.log(nums.length);
for (var i = 0; i < nums.length; i++) {
  hash.put(nums[i]);
}
console.log(hash.show());
    • 开链法：散列值可以重复，但是相同的键还在同一索引位置上，适用于数组大小是待存储数据个数的 1.5 倍
    function HashTable() {
  this.table = new Array(137);
  this.show = show;
  this.simpleHash = simpleHash;
  this.put = put;
  this.build = build;
  this.find = find;
}
let put = function(data) {
  var pos = this.simpleHash(data);
  var index = 0;
  if (!this.table[pos][index]) {
    this.table[pos][index] = data;
  } else {
    while (this.table[pos][index]) {
      index++;
    }
    this.table[pos][index] = data;
  }
};
let simpleHash = function(data) {
  var total = 0;
  for (var i = 0; i < data.length; i++) {
    total += data[i].charCodeAt();
  }
  return parseInt(total % this.table.length);
};
let show = function() {
  var result = "";
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i].length) {
      result += i + ":" + this.table[i].toString() + "\n";
    }
  }
  return result;
};
let build = function() {
  for (var i = 0; i < this.table.length; i++) {
    this.table[i] = new Array();
  }
};
let find = function(data) {
  var table = this.table;
  var pos = this.simpleHash(data);
  var index = table[pos].indexOf(data);
  return {
    [pos + "," + index]: data
  };
};
let hash = new HashTable();
hash.build();
var arr = ["egg", "koa", "express", "1001", "less", "sass", "stylus", "0101"];
for (var i = 0; i < arr.length; i++) {
  hash.put(arr[i]);
}
console.log(hash.show());
console.log(hash.find("0101"));
    • 线性探测法：发生碰撞的时候，寻找下一位置是否为空，为空则则把键存入该位置，适用于数组大小是待存储数据个数的 2 倍及以上
    function HashTable() {
  this.table = new Array(137);
  this.show = show;
  this.simpleHash = simpleHash;
  this.put = put;
  this.find = find;
  this.value = [];
}
let put = function(data) {
  var pos = this.simpleHash(data);
  if (!this.table[pos]) {
    this.table[pos] = data;
    this.value[pos] = data;
  } else {
    while (this.table[pos]) {
      pos++;
    }
    this.table[pos] = data;
    this.value[pos] = data;
  }
};
let simpleHash = function(data) {
  var total = 0;
  for (var i = 0; i < data.length; i++) {
    total += data[i].charCodeAt();
  }
  return parseInt(total % this.table.length);
};
let show = function() {
  var result = "";
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i]) {
      result += i + ":" + this.table[i] + "\n";
    }
  }
  return result;
};
let find = function(data) {
  var index = this.value.indexOf(data);
  return {
    [index]: data
  };
};
let hash = new HashTable();
var arr = ["egg", "koa", "express", "1001", "less", "sass", "stylus", "0101"];
for (var i = 0; i < arr.length; i++) {
  hash.put(arr[i]);
}
console.log(hash.show());
console.log(hash.find("0101"));