散列表

散列表

散列表是一种数据结构。通过key value进行存储。你可以先看下上面百度百科的解释，注意其中这几个关键字散列函数，冲突。

这样一个需求

假如你是水果的销售人员，那么你肯定要知道每种水果的价格，比如顾客来了说苹果多少钱一斤，假如你有一个清单，也就是我们说的数组。

散列表.jpg

我们前面介绍了二分查找方法，比如我们要查找一个数组中的元素，需要的log2n。如果水果很多怎么办，那么有的同学就说了，哪有这么难，我可以记住这些水果，确实我们也讲过带有缓存的函数，你可以记住那些你查找过的水果，如果不适用缓存函数那，我们想像数组那样，比如我要下标为10的元素，我们就能立刻找到这个元素。所以我们要设法写一个函数吧这些水果都映射到数组的下标中，比如苹果我就要存到0的地方，香蕉我要存到1的地方等等，那么我们在找苹果的时候，我们就要这个函数告诉我苹果在数组的那个位置，我们就可以轻松的找到了苹果的位置。

散列函数

散列函数.jpg

我们通过散列函数将苹果存放到数组下标为七的地方。大家肯定会说这个不就是字典吗。我给一个key就得到一个value.对的字典就是散列表的一种实现。

用途

• 用于查找，散列表是key -> value所以查找速度很快。

• 防止重复，由于一个key -> value所以是一一对应关系

• 用于缓存，一定输入对应一定输出的函数，我们可以使用散列表进行缓存。

冲突

对于编写的散列函数来说，我们希望能编写出一个一一对应的关系，但是这样的函数太难了。于是就会出现了一种情况就是我的处的下标上已经存在了元素。那么就会造成冲突。为了解决冲突我们有两种解决方案

• 使用好的散列函数

• key -> array 没错将我们以前的value改成数组这样就可以是一对多的关系

性能

上面的冲突给我的性能带来了一些性能的影响，如果一个不好的散列函数的出的数组同一位置上的元素越来越多，那么查找速度就会越来越慢，所以就会影响性能。

总结

• 每门编程语言都会编写散列表的实现，所以你无须自己实现

• 注意使用的散列函数，它会影响你的性能

• 注意冲突

• 散列表的用途