我们已经有数组、链表、栈和队列，但是有这样的情况：
一个不懂的英语单词，在电子词典，我们可以直接输入单词就得到结果；
查询学生的成绩，怎么样才能在只知道学号的情况下就得到结果；
...
这就需要神奇的哈希表。哈希表就像字典，方便我们查询和统计
哈希表（hash table）也叫做散列表，这种数据结构提供了键（key）和值（value）的映射关系，只要给出一个key，就可以查到对应的value。时间复杂度接近于O(1)
因为哈希表的本质是数组，数组在内存中是连续的，实际上数组名指向的是数组首元素的首地址，但是只要我知道下标，我就可以直接推得元素的内存地址，跟n（问题规模）没有关系，用大O表示法就是O(1)
哈希表的基本原理：
在数组、链表、栈和队列，哪个查询的效率最高
| 查找 | 更新 | 插入 | 删除 | |
|---|---|---|---|---|
| 数组 | O(1) | O(1) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) |
| 入栈/入队 | 出栈/出队 | |||
| 栈 | O(1) | O(1) | ||
| 队列 | O(1) | O(1) |
哈希表在本质上也是一个数组。但是在哈希表中key经常是字符串，数组的索引使用下标的方式，字符串 is not 下标。因此我们需要一个“中转站”，通过某种方式，将key和数组下标进行转换，（这个中转站就叫做哈希函数）。
在Python中的哈希表对应的集合叫做字典（dict），人就直接叫字典了，厉害厉害。
在Python和大多数面向对象的语言中，每个对象都有属于自己的hash值，这个hash值是区分不同对象的重要标志。
hash值是一个整型变量，和对象类型无关
既然哈希表的本质是数组，那么如何把key转化成数组下标？
最简单的方式是，对数组长度进行取模运算 index = hash(key) % size,实际上Python并不是简单的取模，而是利用了位运算的方式，简单理解为取模就OK了
在哈希表中插入新的键值对（也被称为Entry）
通过哈希函数，把key转化成数组下标
如果下标对应的位置没有数据，那么就把Entry插入这个位置
问题：数组长度是有限的，插入的越来越多，咋办？如果key取模之后的index相同(撞衫)如何处理？
这种情况就称为 哈希冲突
哈希冲突是不能避免的，解决办法有两种：
开放寻址法（当一个key通过hash函数得到的数组下标已经被占用了，那么就往下走，如果是空的，就用这个位置，当然寻址方式有很多，这只是提供思路，简单的示例）
链表法（哈希列表中的每一个元素不再是简单的数据，而是一个链表的头节点，也就是每一个元素都是一个链表，遇到一个相同index就把它放到链表末尾，next指针指向它）
通过哈希函数，得到key对应的数组下标
找到数组下标对应的元素（如果是使用链表法，那么找到数组下标之后，先取出一个元素看看元素的key和key是否一致，如果不一致，就接着往下找，也就是链表的遍历）
在Python中的dict使用的是开放寻址法
字典并不是一种序列，而是映射（mapping）。数组是序列，通过相对位置来存储，字典是通过键来存储。
创建字典：
我们可以直接选择使用{}花括号创建字典，也可以创建一个空字典，然后每次以一个键来填写它
字典元素的索引操作和序列是同样的语法，使用的都是[]
dict = {‘name‘:{‘first_name‘:"go",‘second_name‘:‘weibo‘},
‘job‘:["student",‘teacher‘],
‘age‘:21,}
?
dict[‘name‘][‘first_name‘] = ‘guo‘
dict[‘job‘].append(‘engineer‘)
print(dict[‘job‘][-1])
?
dict[‘age‘] = 22
?
print(dict)
Python有一种垃圾收集的特性，在程序运行时可以清理不再使用的内存，在Python中，当最后一次引用对象后（比如将这个变量用其他值进行赋值），这个对象所占用的空间将会被自动清理掉。
当我们需要强调某种顺序的时候，可以使用列表的.sort()方法，或者sorted()函数
d = {
‘a‘:1,
‘b‘:2,
‘c‘:3,
‘d‘:4,
}
?
if ‘e‘ not in d:
print("missing")
?
# 这两种测试方法是等效的
e = d.get("e",5) # 读出d[‘e‘],若不存在，返回5
f = d["f"] if ‘f‘ in d else 6 # 注意没有分号
?
print(e)
print(f)
原文：https://www.cnblogs.com/wb-Hopen/p/13079570.html