如何在一个无序的线性表中查找一个数据元素
无序的线性表，查找的这个元素在表中位置随机，时间复杂度为o(n)；哈希表结构中的元素与它所在的位置存在一个对应关系，这样的话我们就可以通过这个元素直接找到它所在的位置，o(1)

定义

根据哈希表就是通过一个映射函数f(key)将一组数据散列存储在数组中的一种数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，查找速度快。
这个映射函数称做散列函数，存放记录的数组称做散列表。

最基本的几个数据结构中，数组可以通过下标直接访问数据，所以查询效率是最高的。。
哈希表本质上是个数组，两种实现方法：
1、数组+链表
2、数组+二叉树
数组中一般就是存放的单一的数据，而哈希表中存放的是一个键值对
哈希表就是通过将关键值key通过一个散列函数加工处理之后得到一个值，这个值就是数据存放的位置，我们就可以根据这个值快速的找到我们想要的数据

这里的学号是个key，我们之前也知道了，哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是用来确定这个键值对要存放在哈希表中的位置的，实际上这个值就是一个下标值，来确定放在数组的哪个位置上。
比如这里的学号是101011，那么经过哈希函数的计算之后得到了1，这个1就是告诉我们应该把这个键值对放到哪个位置，这个1就是数组的确切位置的下标，也就是需要放在数组中下表为1的位置，如图中所示。
我们经过哈希函数计算得出的1只是为了确定这个键值对该放在哪个位置而已.

HashMap和HashTable的区别

HashMap不是线程安全，为什么HashMap不是线程安全的？

哈希冲突

学号为102011的李四，他的学号经过哈希函数的计算也得出了1，那么也要放到数组中为1的位置，可是这个位置之前已经被张三占了，这种情况就是哈希冲突或者也叫哈希碰撞。

解决哈希冲突方法

一个是开放寻址法：当前位置被占用了，我们就看看该位置的后一个位置是否可用，以此类推

另一个是拉链法。
这时候这个1的位置存放的不单单是之前的那个键值对了，此时的键值对还额外的保存了一个next指针，这个指针指向数组外的另外一个位置，将李四安排在这里，然后张三那个键值对中的next指针就指向李四的这个位置，也就是保存的这个位置的内存地址。

哈希扩容：达到了总位置的百分之七十就需要扩容
哈希函数是核心。设计哈希函数方法：直接定址法，数字分析法，折叠法，随机数法和除留余数法

哈希表的扩容与Rehash

在哈希表长度不变的情况下，随着哈希表中插入的元素越来越多，发生哈希冲突的概率会越来越大，相应的查找的效率就会越来越低。这意味着影响哈希表性能的因素除了哈希函数与处理冲突的方法之外，还与哈希表的装填因子大小有关。
我们将哈希表中元素数与哈希表长度的比值称为装填因子。装填因子 α=

很显然，α的值越小哈希冲突的概率越小，查找时的效率也就越高。而减小α的值就意味着降低了哈希表的使用率。显然这是一个矛盾的关系，不可能有完美解。为了兼顾彼此，装填因子的最大值一般选在0.65~0.9之间。比如HashMap中就将装填因子定为0.75。一旦HashMap的装填因子大于0.75的时候，为了减少哈希冲突，就需要对哈希表进行扩容操作。比如我们可以将哈希表的长度扩大到原来的2倍。
这里我们应该知道，扩容并不是在原数组基础上扩大容量，而是需要申请一个长度为原来2倍的新数组。因此，扩容之后就需要将原来的数据从旧数组中重新散列存放到扩容后的新数组。这个过程我们称之为Rehash。

无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()  //去重
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans