哈希表是key-value类型的数据结构，通过关键码值直接进行访问。通过散列函数进行键和数组的下标映射从而决定该键值应该放在哪个位置，哈希表可以理解为一个键值需要按一定规则存放的数组，而哈希函数就是这个规则。
算法中时间和空间是不能兼得的，哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作，这取决于具体的功能要求。
创建一个数组，数组下标是索引号，数组中的值是要获得的数据，这样只需要O(1)的时间复杂度就可以完成操作，但是扩展性不强，有以下两个方面的考虑：
-1- 新添加的元素超出数组索引范围，这就需要重新申请数组进行迁移操作。
-2- 假设一种极端的情况：只存在两个元素，索引号分别是1和100000000001，按照先前的设计思路，会浪费很大的存储空间。
会不会存在一个方法，为已有的索引创建新的索引，通过压缩位数，让新索引可以和原有的大范围的稀疏索引进行一一对应，新索引所需要的存储空间要大大减小，这就是哈希思想。
上面的例子中哈希函数的设计很随意，但是从这个例子中我们也可以得到信息：
哈希函数就是一个映射，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可；
因为新的索引对旧的索引进行了空间上的压缩，所以不可能所有的输入都只对应唯一一个输出，也就是哈希函数式有可能发生冲突的，哈希函数不可能做成一对一的映射关系，其本质是一个多对一的映射。
直接定址法：很容易理解，key=Value+C； 这个“C”是常量。Value+C其实就是一个简单的哈希函数。
除法取余法： 很容易理解， key=value%C解释同上。
数字分析法：这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。
平方取中法。此处忽略，见名识意。
折叠法：这种蛮有意思,比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相关，来做到“散列地址”尽可能分散的目地。
当两个不同的数据元素的哈希值相同时，就会发生冲突。解决冲突常用的手法有2种：
开放地址法：
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
链接法：
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。
python的dict采用了哈希表，最低能在 O(1)时间内完成搜索，在发生哈希冲突的时候采用的是开放寻址法。java的HashMap也是采用了哈希表实现，但是在发生哈希冲突的时候采用的是链接法。
python字典类型的英文单词是：dict。
在Python中，字典这种数据类型的英文叫做 “dict”，有的语言里它的名称是 “hash”。字典是编程中最常用的数据结构之一。它是用来做映射或者存储你需要的键值对，这样当你需要的时候，你可以通过key来获取它的值。
同样，程序员不会使用一个像“字典”这样的术语，来称呼那些不能像一个写满词汇的真实字典正常使用的事物，所以我们只要把它当做真实世界中的字典来用就好。
字典与列表的区别
针对列表你可以做这样的事情：
>>>things = ['a', 'b', 'c', 'd']
>>>print things[1]
b >>>things[1] =
'
z'
>>>print things[1]
z >>>things
['a', 'z', 'c', 'd']
你可以使用数字作为列表的索引，也就是你可以通过数字找到列表中的元素。你现在应该了解列表的这些特性，而你也应了解，你也只能通过数字来获取列表中的元素。而 dict是让你可以通过任何东西找到元素，不只是数字。是的，字典可以将一个物件和另外一个东西关联，不管它们的类型是什么。
