散列表

散列表是一种数据结构，也叫Hash table. 在python中以字典实现。

散列表通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。散列表是数组的一种扩展。

举个例子

商店中有许多商品，客户来买东西时，需要在一个本子中查找价格。商品很多，我们查找价格的时间就会增加，无论使用之前的简单查找 or 二分查找。

如果我想要快速的获取商品的价格，我就需要一个数组来存放商品的价格，apple放在[0], milk放在[1]…以此类推。

现在我想要知道apple的价格，我仅需要取出数组[0]的存储信息。

这就是散列思想，商品的名称称为key，然后通过散列函数将商品名称与数组位置匹配。

散列函数

给出自变量，散列函数返还一个数字(即数组索引位置)。这里的一些做法和高中数学定义的函数是相似的。

1. 对于给定自变量，有且仅有一个函数值与之对应。例如，我每次输入apple得到的都应是0。
2. 对于同一函数值，可以有多个自变量与之对应。但是在列表函数中，将不同的输入映射到不同的数字是最好的结果。

对于第二条的最佳情况，我们无法避免这也被称为哈希冲突。

一些有意思的应用

最近做网站用到的DNS解析，正式将网站地址映射到IP地址。上软广

mrlepro.com –> 185.199.109.153

哈希冲突

当不同输入映射到同一位置时候就出现了冲突。

链表法解决冲突

如果两个键映射到了同一个位置，就在这个位置储存一个链表。

性能

避免冲突的因素：

1. 较低的装填因子
2. 良好的散列函数

装填因子

散列表中元素数 / 位置总数

经验而谈，当装填因子大于0.7时，扩大散列表长度降低装填因子。

良好的散列函数

MD5， SHA，CRC

待补充