#1.Hash表
哈希表(Hash table,也叫散列表),是根据key而**直接**进行访问的数据结构。也就是说,它通过把key映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
以数据中每个元素的关键字K为自变量,通过散列函数H(k)计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。
哈希表存储的是键值对,其查找的时间复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的,因此,哈希表查找的时间复杂度为O(1)。
#2.哈希表的构造方法
##2.1直接定址法
取关键字或者关键字的某个**线性函数**值作为哈希地址,即
H(Key)=Key或者H(Key)=a*Key+b(a,b为整数)
这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,直到找到H(Key)的位置没有值了就把元素放进去.
此法仅适合于:地址集合的大小 等于 关键字集合的大小
##2.2 数字分析法
分析一组数据,比如一组员工的出生年月,这时我们发现出生年月的前几位数字一般都相同,因此,出现冲突的概率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果利用后面的几位数字来构造散列地址,则冲突的几率则会明显降低.
因此数�