Hash

哈希表(Hash Table,也叫散列表),是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。哈希表的实现主要需要解决两个问题,哈希函数和冲突解决。

哈希函数

哈希函数也叫散列函数,它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构,同时散列结果应当具有同一性(输出值尽量均匀)和雪崩效应(微小的输入值变化使得输出值发生巨大的变化)

冲突解决

  • 开放地址法以发生冲突的哈希地址为输入,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。有以下几种方式:
    • 线性探查法:从发生冲突的地址开始,依次探查下一个地址,直到找到一个空闲单元。
    • 平方探查法:设冲突地址为d0,则探查序列为:d0+1^2,d0-1^2,d0+2^2…
  • 拉链法:把所有的同义词用单链表链接起来。在这种方法下,哈希表每个单元中存放的不再是元素本身,而是相应同义词单链表的头指针。HashMap就是使用这种方法解决冲突的。

    Hash - 图1