哈希表

一.概念

哈希表（Hash Table）是一种常见的数据结构，用于实现键值对之间的映射关系。它通过哈希函数将键转换为索引，然后将值存储在对应索引的位置上，从而实现快速的数据查找、插入和删除操作,哈希表可以不经过任何比较，一次直接从表中得到要搜索的元素。 

如何建立?

1.插入元素 :根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

2.搜索元素 :对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若 关键码相等,则搜索成功

哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表

例如：数据集合{1，7，6，4，5，9}； 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

二.哈希冲突

1.概念:

不同关键字通过相同哈 希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2.如何解决:

由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

3.常见哈希函数:

1. 直接定制法:取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关 键字的分布情况

使用场景：适合查找比较小且连续的情况

2. 除留余数法:设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p