《图解算法》学习笔记之散列表(hash table)
目录
散列函数
散列函数准确地指出了价格的存储位置，你根本不用查找！之所以能够这样，具体原因如下。
散列函数总是将同样的输入映射到相同的索引。每次你输入avocado，得到的都是同一个
数字。因此，你可首先使用它来确定将鳄梨的价格存储在什么地方，并在以后使用它来
确定鳄梨的价格存储在什么地方。
散列函数将不同的输入映射到不同的索引。 avocado映射到索引4， milk映射到索引0。每
种商品都映射到数组的不同位置，让你能够将其价格存储到这里。
散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会
返回无效索引100。
你结合使用散列函数和数组创建了一种被称为散列表（hash table）的数据结构。散列表是你学习的第一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
在你将学习的复杂数据结构中，散列表可能是最有用的，也被称为散列映射、映射、字典和关联数组。散列表的速度很快！你可以立即获取数组中的元素，而散列表也使用数组来存储数据，因此其获取元素的速度与数组一样快。
防止重复
你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。 Python提供的散列表实现为字典，你可使用函数dict来创建散列表。
Michael_Book = {}
def addName(name):
if Michael_Book.get(name):
print("Let tom out")
else:
Michael_Book[name] = 1111111111
print("Let tom vote")
Michael_Book["Michael"] = 1253
Michael_Book["Jance"] = 5482
Michael_Book["Tomoto"] = 874152
addName("Sun")
print(Michael_Book)
将散列表用作缓存
例如， Facebook的服务器可能搜集你朋友的最近活动，以便向你显示这些信息，这需要几秒
钟的时间。作为用户的你，可能感觉这几秒钟很久，进而可能认为Facebook怎么这么慢！另一方
面， Facebook的服务器必须为数以百万的用户提供服务，每个人的几秒钟累积起来就相当多了。
为服务好所有用户， Facebook的服务器实际上在很努力地工作。有没有办法让Facebook的服务器
少做些工作，从而提高Facebook网站的访问速度呢？
假设你有个侄女，总是没完没了地问你有关星球的问题。火星离地球多远？月球呢？木星
呢？每次你都得在Google搜索，再告诉她答案。这需要几分钟。现在假设她老问你月球离地球多
远，很快你就记住了月球离地球238 900英里。因此不必再去Google搜索，你就可以直接告诉她
答案。这就是缓存的工作原理：网站将数据记住，而不再重新计算。
如果你登录了Facebook，你看到的所有内容都是为你定制的。你每次访问facebook.com，其
服务器都需考虑你感兴趣的是什么内容。但如果你没有登录，看到的将是登录页面。每个人看到
的登录页面都相同。 Facebook被反复要求做同样的事情：“当我注销时，请向我显示主页。”有鉴
于此，它不让服务器去生成主页，而是将主页存储起来，并在需要时将其直接发送给用户。
这就是缓存，具有如下两个优点。
用户能够更快地看到网页，就像你记住了月球与地球之间的距离时一样。下次你侄女再
问你时，你就不用再使用Google搜索，立刻就可以告诉她答案。
Facebook需要做的工作更少。
缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！
Facebook不仅缓存主页，还缓存About页面、 Contact页面、 Terms and Conditions页面等众多
其他的页面。因此，它需要将页面URL映射到页面数据。
小结
这里总结一下，散列表适合用于：
模拟映射关系；
防止重复；
缓存/记住数据，以免服务器再通过处理来生成它们。
冲突
这里的经验教训有两个。
散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，
散列函数将键均匀地映射到散列表的不同位置。如果散列表存储的链表很长，散列表的速度将急剧下降。然而， 如果使用的散列函数很
好，这些链表就不会很长！
散列函数很重要，好的散列函数很少导致冲突。
性能
一条水平线，看到了吧？这意味着无论散列表包含一个元素还是10亿个元素，从其中获取数
据所需的时间都相同。实际上，你以前见过常量时间——从数组中获取一个元素所需的时间就是
固定的：不管数组多大，从中获取一个元素所需的时间都是相同的。在平均情况下，散列表的速
度确实很快。
填装因子
小结
你几乎根本不用自己去实现散列表，因为你使用的编程语言提供了散列表实现。你可使用
Python提供的散列表，并假定能够获得平均情况下的性能：常量时间。
散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。
你可能很快会发现自己经常在使用它。
你可以结合散列函数和数组来创建散列表。
冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
散列表的查找、插入和删除速度都非常快。
散列表适合用于模拟映射关系。
一旦填装因子超过0.7，就该调整散列表的长度。
散列表可用于缓存数据（例如，在Web服务器上）。
散列表非常适合用于防止重复。
示例代码
Python
voted = {}
def check_voter(name):
if voted.get(name):
print("kick them out!")
else:
voted[name] = True
print("let them vote!")
check_voter("tom")
check_voter("mike")
check_voter("mike")
book = {"apple": 0.67, "milk": 1.49, "avocado": 1.49}
print(book)C++
#include <iostream>
#include <unordered_map>
#include <string>
#include <utility>
#include <map>
using namespace std;
using std::cout;
using std::endl;
int main() {
std::unordered_map<std::string, float> book = {
{ "apple", 0.67 },
{ "milk", 1.49 },
{ "avocado", 1.49 }
};
map<string, float> priceGoods = {
{ "apple", 0.67 },
{ "milk", 1.49 },
{ "avocado", 1.49 }
};
// print book
for (std::pair<std::string, float> pair : book) {
cout << pair.first << ": " << pair.second << "$" << endl;
}
// print map book
cout << "-------------map book myself------------------" << endl;
map<string, float>::iterator iter;
for (iter = priceGoods.begin(); iter != priceGoods.end(); iter++)
{
cout << iter->first << " : " << iter->second << endl;
}
}#include <iostream>
#include <unordered_map>
#include <string>
using std::cout;
using std::endl;
std::unordered_map<std::string, bool> voted;
void check_voter(const std::string& name) {
//使用find，返回的是被查找元素的位置，没有则返回map.end()。
auto search = voted.find(name);
if (search == voted.end() || search->second == false) {
voted.insert({ name, true });
cout << "Let them vote!" << endl;;
}
else {
cout << "Kick them out!" << endl;
}
}
int main() {
check_voter("tom");
check_voter("mike");
check_voter("mike");
check_voter("tom");
}C#
using System;
using System.Collections.Generic;
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
var book = new Dictionary<string, decimal>();
book.Add("apple", 0.67m);
book.Add("milk", 1.49m);
book.Add("avocado", 1.49m);
foreach (var item in book)
{
Console.WriteLine($"{item.Key}: {item.Value}");
}
}
}
}
using System;
using System.Collections.Generic;
namespace ConsoleApplication
{
public class Program
{
private static Dictionary<string, bool> _voted = new Dictionary<string, bool>();
public static void Main(string[] args)
{
CheckVoter("tom");
CheckVoter("mike");
CheckVoter("mike");
}
private static void CheckVoter(string name)
{
if (_voted.ContainsKey(name))
{
Console.WriteLine("kick them out!");
}
else
{
_voted.Add(name, true);
Console.WriteLine("let them vote!");
}
}
}
}
JS
const book = {};
// an apple costs 67 cents
book['apple'] = 0.67;
// milk costs $1.49
book['milk'] = 1.49;
book['avocado'] = 1.49;
console.log(book); // { apple: 0.67, milk: 1.49, avocado: 1.49 }
const voted = {};
function check_voter(name) {
if (voted[name]) {
console.log('kick them out!');
} else {
voted[name] = true;
console.log('let them vote!');
}
}
check_voter("tom"); // let them vote!
check_voter("mike"); // let them vote!
check_voter("mike"); // kick them out!
//Console.log(voted["tom"]);
Harstable
/**
* Class HashTable
*
* @param {object} obj
*/
let HashTable = function( obj ) {
let length = 0;
this._items = ( function( obj ) {
let items = {};
for ( let p in obj ) {
items[p] = obj[p];
length++;
}
return items;
}( obj ) );
/**
* Associates the specified value to the specified key
*
* @param {string} key The key to which associate the value
* @param {string} value The value to associate to the key
*
* @return {(undefined|object)} Undefined is object didn't exists before this call
*/
this.set = function( key, value ) {
let previous = undefined;
if ( this.has( key ) ) {
previous = this._items[key];
} else {
length++;
}
this._items[key] = value;
return previous;
};
/**
* Returns the value associated to the specified key
*
* @param {string} key The key from which retrieve the value
*
* @return {(undefined|string)} Undefined or associated value
*/
this.get = function( key ) {
return this._items.hasOwnProperty( key ) ? this._items[key] : undefined;
};
/**
* Returns whether the hashtable contains the specified key
*
* @param {string} key The key to check
*
* @return {boolean}
*/
this.has = function( key ) {
return this._items.hasOwnProperty( key );
};
/**
* Removes the specified key with its value
*
* @param {string} key The key to remove
*
* @return {(undefined|string)} Undefined if key doesn't exist and
* string (previous value) - value of deleted item
*/
this.remove = function( key ) {
if ( this.has( key ) ) {
let previous = this._items[key];
length--;
delete this._items[key];
return previous;
} else {
return undefined;
}
};
/**
* Returns an array with all the registered keys
*
* @return {array}
*/
this.getKeys = function() {
let keys = [];
for ( let i in this._items ) {
if ( this.has( i ) ) {
keys.push( i );
}
}
return keys;
};
/**
* Returns an array with all the registered values
*
* @return {array}
*/
this.getValues = function() {
let values = [];
for ( let i in this._items ) {
if ( this.has( i ) ) {
values.push( this._items[i] );
}
}
return values;
};
/**
* Iterates all entries in the specified iterator callback
* @param {function} callback A method with 2 parameters: key, value
*/
this.each = function( callback ) {
for ( let i in this._items ) {
if ( this.has( i ) ) {
callback( i, this._items[i] );
}
}
};
/**
* Deletes all the key-value pairs on the hashmap
*/
this.clear = function() {
this._items = {};
length = 0;
};
/**
* Gets the count of the entries in the hashtable
*/
Object.defineProperty( this, 'length', {
get: function() {
return length;
},
});
/**
* Gets an array of all keys in the hashtable
*/
Object.defineProperty(this, 'keys', {
get: function() {
return this.getKeys();
},
});
/**
* Gets an array of all values in the hashtable
*/
Object.defineProperty(this, 'values', {
get: function() {
return this.getValues();
},
});
};
let hashtable = new HashTable({'one': 1, 'two': 2, 'three': 3, 'cuatro': 4});
console.log( 'Original length: ' + hashtable.length ); // Original length: 4
console.log( 'Value of key "one": ' + hashtable.get( 'one' ) ); // Value of key "one": 1
console.log( 'Has key "foo"? ' + hashtable.has( 'foo' )); // Has key "foo"? false
console.log( 'Previous value of key "foo": ' + hashtable.set( 'foo', 'bar' ) ); // Previous value of key "foo": undefined
console.log( 'Length after set: ' + hashtable.length ); // Length after set: 5
console.log( 'Value of key "foo": ' + hashtable.get( 'foo' ) ); // Value of key "foo": bar
console.log( 'Value of key "cuatro": ' + hashtable.get( 'cuatro' )); // Value of key "cuatro": 4
console.log( 'Get keys by using property: ' + hashtable.keys ); // Get keys by using property: one,two,three,cuatro,foo
hashtable.clear();
console.log( 'Length after clear: ' + hashtable.length ); // Length after clear: 0
Java
import java.util.HashMap;
import java.util.Map;
public class JavaLearn {
public static void main(String[] args) {
Map<String, Double> book = new HashMap<>();
// an apple costs 67 cents
book.put("apple", 0.67);
// milk costs $1.49
book.put("milk", 1.49);
book.put("avocado", 1.49);
System.out.println(book); // {apple=0.67, avocado=1.49, milk=1.49}
}
}
import java.util.HashMap;
import java.util.Map;
public class JavaLearn {
private static Map<String, Boolean> voted = new HashMap<>();
private static void checkVoter(String name) {
if (voted.containsKey(name)) {
System.out.println("kick them out!");
} else {
voted.put(name, true);
System.out.println("let them vote!");
}
}
public static void main(String[] args) {
checkVoter("tom"); // let them vote!
checkVoter("mike"); // let them vote!
checkVoter("mike"); // kick them out!
checkVoter("tom"); // let them vote!
}
}