在前面 数组中重复的数字 的一道算法题中，我发现有人提到了Hash算法。自己第一次接触这个概念，所以在此简单的总结一下python中Hash的应用，具体原理留到以后的笔记中吧。

Hash表

Hash表是一种以 键值对（Key-Value） 存储数据的结构，在python中字典类型就是其应用。当查找某一数据值时，只需要输入其Key值就可以。

一般步骤：

  1. 使用哈希函数将被查找的键转换为数组索引。 在理想情况下，不同的键对应转换后的索引值是不同的，但是对于有限的数组长度，需要处理多个Key的冲突问题。
  2. 处理碰撞冲突：多个Key对应到同一个索引值的情况。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

具体如何做呢？“数组可以通过下标直接定位到相应的空间”，哈希表的做法其实很简单，就是把Key通过一个固定的算法函数，既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

Hash表其实就是通过空间换取时间的做法。由于hashcode会对数组长度进行取余，因此其结果由于数组长度的限制必然会出现重复，所以就会有“冲突”这一问题。

Python中的应用

准确来讲，python中是没有 数组 概念的。python中的数组分为三种类型：

  1. List，普通的链表长度可变。定义方式：arr = [元素]
  2. Tuple，一旦定义后，长度不可变。定义方式：arr = [元素]
  3. Dict，字典长度可变，Hash数组。定义方式：arr = [元素]

三种类型的相关操作可以参考前面的笔记或者菜鸟教程相关文档！

Numpy数组

尽管，Python中提供了list容器，可以当作数组使用。但是list中的元素可以是任何对象，因此list中保存的是对象的指针，对于数值运算来讲这种结构显然不够高效。

Python中提供了array（数组）模块，但是只支持1D。

什么是Numpy？

  1. NumPy 是用于处理数组的 python 库。
  2. 它还拥有在线性代数、傅立叶变换和矩阵领域中工作的函数。
  3. NumPy 由 Travis Oliphant 于 2005 年创建。它是一个开源项目，您可以自由使用它。
  4. NumPy 指的是数值 Python（Numerical Python）。

####为何使用Numpy？

  1. 在 Python 中，我们有满足数组功能的列表，但是处理起来很慢。
  2. NumPy 旨在提供一个比传统 Python 列表快 50 倍的数组对象。
  3. NumPy 中的数组对象称为 ndarray，它提供了许多支持函数，使得利用 ndarray 非常容易。
  4. 数组在数据科学中非常常用，因为速度和资源非常重要。

参考