哈希表原理，Hashtable（Hushmap）原理

哈希表 Hash table 散列表

特点

• 接近O（1）的查找效率
• 根据键（key 关键值）而直接访问在内存存储位置
• 本质上是一个数组，数组里面存的链表

原理和例子

• 原始数据（key 关键值） —— 哈希函数（散列函数）—— 得到一个值（类似于数组下标），映射到表中一个位置（散列表）
• 小王 —— 取首字母 —— W —— 电话博里面W那一页
• 地址 index=H（key）
• 键值对 key—— value 键值——Hush值 学号——名字

哈希函数构造方法

• 考虑因素
  • 计算散列地址所需要的时间 关键字长度是否均匀，是否有规律可循 表长 Hush冲突
• 构造方法
• 直接定制法
  • H（key）=a*key+b 仅限于地址大小=关键字集合
• 数字分析法
  • 假设每个关键字key都是由s位数字组成（k1 , k2 , … Kn）并从中提取分布均匀的若干位或他们的组合构成全体
  • 比如同一地区的同学，身份证5位相同，那取后几位存储 H（key）=key%100000
• 平方取中法
  • 先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址 key=1234 1234^2=1522756 取227作hash地址
• 折叠法：
  • 数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址
• 除留余数法
  • H（key）=key MOD p （p<=m m为表长）很明显，如何选取p是个关键问题
  • 比如我们存储3 6 9，那么p就不能取3 3 MOD 3 == 6 MOD 3 == 9 MOD 3
  • p应为不大于m的质数或是不含20以下的质因子的合数，这样可以减少地址的重复（冲突）

哈希冲突

• H（key1）=H（key2）
• 处理方法
  • 开放寻址法（ThreadLocal）：查看下一个位置是否可用，直到找到空位置
    • 扩容：占据总容量的百分之七十五，总容量扩大到原来的2倍，并使用新的Hush函数（以HashMap举例）
  • 拉链法：存放在对应链表的下一个节点（以HashMap举例）
    • 链表长度大于等于8的话，链表就会转换成树结构，小于等于6，维持原链表，7作为一个差值，来避免频繁转换影响性能
  • 公共溢出区法
    • 建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况
  • 再散列法
    • 准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数