散列表适合用于：

  • 模拟映射关系； （域名跟IP地址，DNS域名解析器）
  • 防止重复；
  • 缓存/记住数据，以免服务器再通过处理来生成它们。

    冲突

    冲突：不同的键映射到数组的同一个位置。
    处理冲突的方式 很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。
    image.png

    两个经验教训

  1. 散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是， 散列函数将键均匀地映射到散列表的不同位置。
  2. 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很 好，这些链表就不会很长！

    性能

    散列表中查找所花费的时间为常量时间。
    image.png
    散列表同数组和链表比较。
    image.png

    装填因子

    image.png

散列表使用数组来存储数据，因此你需要计算数组中被占用的位置数。例如，下述散列表的 填装因子为2/5，即0.4。
image.png
填装因子度量的是散列表中有多少位置是空的。
填装因子越低，发生冲突的可能性越小， 散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

可研究一下SHA函数，可将它用作散列函数