散列表

   散列表的英文叫 Hash Table，我们平时也叫它 哈希表 或者 Hash 表。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

  数组和链表都被直接映射到内存，但散列表更复杂，它使用 散列函数 来确定元素的存储位置。

  你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。

    一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 X 到首字母F(x)的一个 函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字 key，取首字母是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

散列表

    散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

---

散列函数

        散列函数又称 哈希函数，是将关键字映射到存储地址的函数（将输入映射到数字），我们可以把它定义成 hash(key) = Addr。其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。

       散列函数必须满足一些条件： 1 它必须是一致的；2 它应将不同的输入映射到不同的数组。

        设计散列函数必须遵守以下两个原则：

            1. 散列函数要尽可能简单，能够快速计算任意关键字的散列地址；

            2. 散列函数映射的地址应该均匀分布整个地址空间，避免聚集，以减少冲突。

        简单总结就是： 简单、均匀。

---

散列冲突

    散列函数总是将不同 的键映射到数组的不同位置。

   前面的散列函数将所有的键都映射到一个位 置，而 最理想的情况 是，散列函数将键均匀地映射到散列表的不同位置，但是这个几乎不可能，这就会造成 不同的 key 会产生相同的 散列值，这就是 散列冲突。

    那么如何解决 散列冲突呢，常用的有两种：

        1. 开放寻址法

        2. 链表法

   2 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如 果使用的散列函数很好 ，这些链表就不会很长！

散列表的应用

    散列表作为缓存

     缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中。

散列表适用于：

    仿真映射关系；防止重复；缓存/记住数据，以免服务器在通过处理来生成它们。