1、简介

• 通过将k经过散列函数计算后 映射到散列表（散列函数+数组+链表） ，将value存储起来，下一次取k的value值时，也是经过相同散列函数计算，即可在O(1)时间取出数据。但是会有可能不同key映射到相同位置，冲突发生，那么可以通过链表来处理冲突

• 散列表整合了数组和链表的优点，查找、插入、删除平均情况都是O(1)

  2、散列表要素

• 散列函数

• 冲突解决策略

  3、散列函数

• 好的散列函数能将自己的冲突降到最低，最好的散列函数是将数据均匀分布到数据+链表中

  4、冲突解决策略

• 良好的散列函数

  • SHA函数

• 较低的填装因子

  • 填装因子 = （数组中已经存有数据的个数）/数组总长度
  • 当填装因子增大时，表明发生冲突的几率变大。一般规则是：一旦填装因子大于0.7，就调整散列表的长度 ，来降低填装因子，减少冲突。填装因子最大是1。

    5、应用

• 可用于查找，如将网址映射成ip地址，DNS域名解析

• 可用于防止重复，如在投票中，检查是否已经投过票了，避免搜索全部记录
• 可用于缓存，例如你向facebook发送一个请求，它会首先在散列表中找这个请求url，有的话将存的页面数据给你，否则访问服务器来进行处理