哈希表到底是个啥？

哈希表到底是啥？

      我们先用Leetcode上一道面试真题来说说，什么是哈希表？

      给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

      案例:

      s = "leetcode"

      返回 0.

      s = "loveleetcode"

      返回 2.

      注意事项：您可以假定该字符串只包含小写字母。

      解题思路：

      我们可以创建一个长度为26的数组，每个数组下标中对应一个字符出现的次数。然后，遍历这个数组，找到一个为1的值，其对应字母就是第一个不重复的字符。

      这道题的解题思路就是哈希表。

      哈希表就是一个数组。根据数据得到数组位置下标的方法，就叫哈希函数。当两个不同数据经过哈希函数计算，得到了相等的下标，这种情况叫做哈希碰撞。

      哈希表的两个重要学习内容，就是设计哈希函数和解决哈希碰撞。接下来，我们逐一说明。

哈希函数和哈希碰撞

      哈希函数有很多构造方法，常用的有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等。

      以除留余数法为例：

      假设，给定一些数字，要把这些数据放在hash表中，可以用这些数字模上数组的长度n, 得到一个0~n-1的数字，正好是数组下标。

      然而，不同关键字可能得到同一哈希地址，即：key1！=key2，而f（key1）=f（key2）

      这种现象叫哈希冲突。一般情况下，冲突只能尽可能减少，不能完全避免。

      因为，哈希函数是从关键字集合到地址集合的映像。通常，关键字集合较大，而地址有限。那么，如何处理冲突，就成了构造哈希表不可缺少的一个方面了。

      通常用于处理冲突的方法有：开放定址法、再哈希法、链地址法、建立一个公共溢出区等。其中较常用的是链地址法。

      比如，关键字列表为： （19,14,23,01,68,20,84,27,55,11,10,79），

      哈希函数为H（key）=key MOD 13。则采用除留余数法和链地址法后得到的预想结果应该为：

自己实现一个HashMap

      Jdk8以前，HashMap解决哈希冲突，使用的是链表存储哈希值相同的元素。Jdk8以后，HashMap解决哈希冲突使用的是红黑树。这是我们使用TreeMap来简单模拟，因为TreeMap的底层实现就是红黑树。

自己实现一个HashSet

      HashSet底层实现基于HashMap, 在HashSet中，元素都存到HashMap键值对的Key上面，而Value时有一个统一的值：

      private static final Object PRESENT = new Object();

      以上，就是哈希表的知识要点，你学会了吗？