一、哈希表基础

  • 哈希表是根据关键码的值而直接进行访问的数据结构。直白来讲其实数组就是一张哈希表。
  • 哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。
  • 哈希表都是用来快速判断一个元素是否出现集合里。

二、哈希函数

例如要查询一个名字是否在这所学校里。

  • 哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
  • 哈希函数通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
  • 如果hashCode得到的数值大于哈希表的大小，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，保证了一定可以映射到哈希表上了。

三、哈希碰撞

  • 当多个值映射到同一个位置的时候，这一现象叫做哈希碰撞。
  • 一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

四、拉链法

  • 将发生冲突的元素都被存储在链表中。
  • 当需要访问的时候，直接访问发生冲突的索引即可。
  • 其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

五、线性探测法

  • 使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
  • 例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。

六、常见的三种哈希结构

  • 当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
    • 数组
    • set （集合）
    • map(映射)

总结

  • 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
  • 哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。