算法图解第5章——散列表

散列函数：将输入映射到数字

1.必须是一致的，输入同一个值时，返回的值必须相同；

2.将不同的输入映射到不同的数字。

var phone_book = {}
phone_book.alice = 135890505
phone_book.desll = 1434545
phone_book["jenny"] = 1434

console.log(phone_book);
//{ alice: 135890505, desll: 1434545, jenny: 1434 }

防止重复

var voted = {}
function check_vote(name) {
  //判断是否已经存在
  if (voted.hasOwnProperty(name)) {
    console.log('kick ' + name + ' out!');
  } else {
    voted[name] = true
    console.log('let ' + name + ' vote!');
  }
  return voted
}

check_vote('alice');
check_vote('alice');
check_vote('mark')；

console.log(voted);
//{ alice: true, mark: true }

数组写法

var voted2 = []
function check_vote2(name) {
  console.log(voted2.indexOf(name));
  if (voted2.indexOf(name) !== -1) {
    console.log('kick ' + name + ' out!');
  } else {
    voted2.push(name)
    console.log('let ' + name + ' vote!');
  }
  return voted2
}
check_vote('alice'); 
check_vote('alice'); 
check_vote('anna')； 

console.log(voted2);
//[ 'alice', 'anna' ]

服务器缓存，如果有缓存就读取缓存，没有就从服务器获取

const cache = {}
function getPage(url) {
  if (cache.hasOwnProperty(url)) {
    return 'cache ' + cache[url]
  } else {
    const data = getUrlServer(url)
    cache[url] = data
    return 'server ' + data
  }
}
function getUrlServer(url) {
  return 'http://'
}

console.log(getPage('www'));
console.log(getPage('www'));
//server http://
//cache http://

平均情况下，散列表的查找速度和数组一样快，插入和删除速度和链表一样快，兼具两者的优点。

但在最糟情况下，各种操作速度都很慢。所以需要避免冲突。（需要有较低的填装因子和良好的散列函数）

以上的例子，更确切的来说是字典，不是确切意义上的散列表。

以下例子是从网上找到的js字典和散列表实例详解

function HashTable() {
  var table = [];

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

  this.put = function(key, value) {
    var position = loseloseHashCode(key);
    table[position] = new ValuePair(key, value);
  }

  this.get = function(key) {
    var position = loseloseHashCode(key);
    if (table[position] !== undefined) 
      return table[position].value;
    return undefined;
  }

  this.remove = function(key) {
    var position = loseloseHashCode(key);
    if (table[position] !== undefined) {
      table[position] = undefined;
      return true;
    }
    return false;
  };

  this.print = function() {
    for (var i = 0; i < table.length; ++i) { //{1}
      if (table[i] !== undefined) { //{2}
        console.info("output", table[i], table[i].toString());
      }
    }
  };

  //新增的方法 创建node元素 将key，value放入这个对象
  var ValuePair = function(key, value) {
    this.key = key;
    this.value = value;
    this.toString = function() {
      return '[' + this.key + ' - ' + this.value + ']';
    }
  };
}

var price = new HashTable()
price.put('apple', 4.5)
price.put('appel', 4.5)
price.put('pear', 3.5)
price.print()
//output ValuePair { key: 'pear', value: 3.5, toString: [Function] } [pear - 3.5]
//output ValuePair { key: 'appel', value: 4.5, toString: [Function] } [appel - 4.5]
//output ValuePair { key: 'apple', value: 4.5, toString: [Function] } [apple - 4.5]