数据结构---散列表、散列函数

1、概述

　　　　1.1、散列表  是实现   字典操作的有效数据结构；

　　　　1.2、如何实现？

　　　　　　　　使用  一个    长度与实际存储的关键字数目成比例的    数组实现；

　　　　1.3、直接寻址表

　　　　　　　　数组的下标  与  元素的关键字  相同；

　　　　1.4、散列表

　　　　　　　　1.4.1、数组的下标   与   hash(元素关键字)   相同；

　　　　　　　　1.4.2、优势：

　　　　　　　　　　　　　　缩小 数组的下标范围、减少数组使用空间；

　　　　　　　　1.4.3、问题：

　　　　　　　　　　　　　　hash冲突

　　　　　　　　　　　 解决：

　　　　　　　　　　　　　　链接法（eg:链表）、开放寻址法

　　　　1.5、散列函数

　　　　　　　　1.5.1、如何设计一个好的散列函数？

　　　　　　　　　　　　a,除法散列法

　　　　　　　　　　　　　　　　h(k)=k 取模 m （m：常数）；

　　　　　　　　　　　　b,乘法散列法

　　　　　　　　　　　　　　　　I、k*A（A：0<A<1）    ->     取小数部分

　　　　　　　　　　　　　　　　II、I的结果  *  m（m：常数），向下取整；

 　　　　　　　　　　　　c,全域散列法

　　　　1.6、完全散列

　　　　　　　　1.6.1、集合静态

　　　　　　　　　　　　　　静态：一旦各关键字存入表中，关键字集合将不再进行变化；

数据结构---散列表、散列函数

原文：https://www.cnblogs.com/anpeiyong/p/12612599.html