可以模拟映射关系：根据key查找value
散列函数
不管输入是什么，总是返回一个数字
对于相同的输入，返回的数字总是相同。例如，输入apple，总是返回0
对于不同的输入，理想情况下，返回的数字总是不同的（实际上，这样的理想情况几乎不可能实现，所以要处理冲突）。例如，输入apple返回0；输入banana返回1。
散列函数只返回有效的索引。例如数组长度为10，它只会返回10以内的数字，不会返回100。
散列表可以用数组+散列函数实现
例如，实现商品和价格的对应关系。apple的价格是0.67，milk的价格是1.49，egg的价格是2.49。
key（商品）：value（价格）
首先创建一个长度为5个数组。
存储：散列函数根据key计算出索引位置，将value存储在数组索引处。
例如，f(apple)=0，f(milk)=2，f(egg)=3，则对应的散列表为[0.67, , 1.49, 2.49, ]（其中，索引位置为1和4的值为空）
查找：散列函数根据key计算出索引位置，在数组索引处找到value。
例如，查找商品apple的价格，散列函数输入apple返回0，数组[0]=0.67
冲突
实际情况下，散列函数几乎很难实现【对于不同的输入，返回的数字总是不同】
比如散列函数【将字符串首字母作为索引】，则apple的索引为0，banana的索引为1，但是avocados的索引也为0。此时如果将avocados的价格存储到索引位置，那么根据apple查找时，预期得到的应该是apple的价格，却得到了avocados的价格。
解决冲突最简单的方式，是在数组冲突的位置存储一个链表。
如果没有冲突，则在散列表中查找元素等同于在数组中根据索引获取元素，速度为O(1)
如果有冲突，且散列函数很糟糕，将所有元素都匹配到了同一个索引位置，则相当于将散列表的所有元素都存储在了一个链表中，那么在散列表中查找元素等同于在链表中查找元素，速度为O(n)
所以为了提高散列表的查找性能，应该尽量减少冲突
减少冲突
降低填装因子
填装因子=散列表的元素总数/位置总数
比如有100个元素，而散列表有100个位置，则填装因子等于1，此时理想情况下，每个元素都可以匹配到一个不同的位置；
如果散列表只有50个位置，则填装因子为2，此时不可能让每个元素都有自己的位置，因为位置总数不够。
良好的散列函数
良好的散列函数总是将元素均匀的分布到散列表中。
散列表的应用案例
模拟映射关系：根据key获取value
防止重复：判断key在散列表中是否已存在
缓存：根据key获取缓存内容
