算法图解笔记（四）---哈希表

哈希表 哈希表又称为散列表，是一种key-value表结构。由哈希函数和数组组成，它的原理是通过哈希函数将传入的key值计算出索引，最后从数组中通过索引快速获取数据。 哈希表结构图 一般情况下它的时间复杂度为O(1)，相比较于有序列表，它的时间复杂度为O(logn)。 哈希表与列表最大的区别在于哈希表需要通过哈希函数中的算法来将key值换算成列表的索引，并且同一个key只能指向与同一个索引，也就是说一旦某个key换算成了一个索引后任何其他key都无法换算成该索引。如果出现重复的索引就称之为哈希碰撞。 在常用的语言中，哈希表通常以字典（dict）的形式表现。 哈希函数 构造哈希函数有多种方式，比如直接寻址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法。 由于哈希函数有可能会出现不同的输入值会输..