【数据结构笔记】散列

今天不列条条了，直接说。

散列的提出是基于一些对插入，删除，查找的效率要求较高而对含有排序信息的操作不关心的场合。

散列执行前面几个操作的平均时间是常数级的。

 

散列函数就是把关键字映射到散列表的函数，对于优秀的散列函数，这种映射应该是均匀的。一个好的办法是要求表的大小为素数。

 

在散列中存在着一个比较重要的问题---冲突，因为待映射集合总是比散列表要大的，所以存在多个元素映射到同一位置的情况，这个就是冲突，解决冲突的算法有很多，基本上是在时间效率和空间效率上进行博弈，下面笔记几个常用的，嘿嘿，也是比较简单的。

 

分离连接法:基本思想就是把映射到同一位置的元素组成一个链表，把这个链表的头指针放在散列表的相应位置，对于这种方法，我们希望散列表的装填因子约接近于1越好。

 

开放定址法：基本思想就是“这个位置有人了那我就找另一个”，怎么“找”很关键，可以直接放入下一个空闲地址，这个称为“线性探测法”，也可以使用平方函数计算下一个位置，这个称为“平方探测法”，在使用这些方法时我们希望装填因子是小于0.5的，否则很有可能造成新的元素无法插入或插入效率很低了。

 

散列有很多丰富的应用，编译器使用散列表跟踪源代码中声明的变量，散列表是这种问题的理想应用，因为只有插入和查找操作要运行，而且标识符都不长，散列值可以快速算出。在游戏编制中，可以通过散列表记录位置信息，这样当程序再经过同样的位置时可以直接查找提取出信息而不用重新计算。