哈希表也叫散列表，这种数据结构提供了键和值的映射关系，只要给出一个key，就可以高效的查找到它所匹配的Value,时间复杂度接近于O(1)。
什么是哈希函数呢？我们知道数组的查询效率是很高的，因为数组可以根据下标进行元素的随机访问。哈希表本质上也是一个数组，但是哈希表的key是以字符串类型为主的，所以，我们要通过某种方式，把哈系表的key转换成数组下标的形式，从而达到像数组那样可以通过下标快速定位元素的位置，这种方式就叫做哈希函数。
这个所谓的哈希函数是怎么实现的呢？在不同的语言中，哈希函数实现的方式是不一样的，在python语言中，哈希表对应的集合叫做字典。在python及大多数面向对象的语言中，每一个对象都有属于自己的hash值，这个hash值是区分不同对象的重要标识。无论对象是什么类型，是字符串，浮点型，它们的hash值都是一个整型变量。既然是整型变量，想要转换成数组的下标也就不难实现了。最简单的方式是什么呢？是按照数组长度进行取模运算。
index = hash(key)%size
通过哈希函数，可以把字符串或其他类型的key,转换成数组的下标index.如果给出一个长度为8的数组，则当
key = 001121时，index=hash(“001121”)%size = 1420036703%8 = 7 key="this"时，index = hash(‘this’)%size = 3559097%8 = 6
有了哈希函数这种对应关系，就可以在哈希表中进行读写操作了。写操作就是在哈希表中插入新的键值对(也被称为Entry)。比如dict[‘姓名’] = “程咬金”，意思是插入一组key为“姓名”，值为“程咬金”的键值对。具体内部是怎么实现的呢？
第1步：通过哈希函数，把key转换成数组下标5。 第2步：如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标为5的位置
哈希冲突
但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的key通过哈希函数获得的下标有可能是相同的。例如，002936这个key对应的数组下标是2；002947这个key对应的数组下标也是2。下标一样了，后面的键值对就插不进去了，它的萝卜坑被占了。这就叫哈希冲突。
哈希冲突是无法避免的，既然不能避免，就要想办法解决
如何解决哈希冲突？
解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。
一：开放寻址法
开放寻址法的原理很简单，当一个key通过哈希函数获得对应的数组下标已经被占用时，寻找后一个位置是否为空，为空的话放进去，不为空的话继续找下一个。
二：链表法
哈希表数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
在众多编成语言中，有些语言的哈希表采用了链表法，最具代表性的就是Java中的HashMap;有些编程语言采用的是开放寻址法，如python 中的dict。
哈希表可以说是数组和链表的结合，它在算法中应用很普遍，是一种非常重要的数据结构。
努力为大家分享更多通俗易懂有趣的python知识哦！欢迎大家关注我的微信公众号：宁仔说python，让学习变得开心有趣
吧!
