哈希表

 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)⽽直接进 ⾏访问的数据结 构。也就是说，它通过把关键码值映射到表中 ⼀个位置来访问记录，以加快查找的速度 。这 个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表 M，存在函数 f(key)，对任意 给定的关键字值 key，代 ⼊函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈 希(Hash）表，函数 f(key)为哈希(Hash) 函数。

散列函数

 能使对 ⼀个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

链式哈希表

• 是由 ⼀组链表构成，每个链表都可以看做是 ⼀个“桶”，我们将所有的元素通过散列的 ⽅式放 到具体的不同的桶中。
• 插 ⼊元素时，⾸先将其键传 ⼊ ⼀个哈希函数，函数通过散列的 ⽅式告知元素属于哪个“桶”，然 后在相应的链表插 ⼊元素。
• 查找或删除元素时，⽤同们的 ⽅式先找到元素的“桶”，然后遍历相应的链表，直到发现我们想要的元素。
• 链表长度：因为每个“桶”都是 ⼀个链表，如果表变得太 ⼤，它的性能将会降低。
  *** 哈希扩容：Bucket 桶不够的话需要重新扩容，历史的数据需要重新 hash。**
• 哈希冲突碰撞： 不同的元素经过 hash 后命中相同的位置。