基本信息

---

下载

文档摘要

---

第14课哈希的概念

学习目标1、了解哈希的概念2、学习哈希的概念和基本思想3、学习基数排序算法4、学习解决哈希冲突的方法

知识讲授

（一）哈希（Hash）的概念【问题引入】读入n（n=105）个正整数，查询某个数是否在这n个数中出现，一共查询m次。显然，这个问题可以先对n个数进行快速排序，然后对于每次询问都进行二分查找解决，时间复杂度为O（mlog2n）。但是这种解法只适用于“离线”的场景——数据输入完毕以后进行查询。如果要实现“在线”查询，即在输入数据过程中随时查询某个元素是否在输入的数据中存在，并且多次查询。这样，我们可能需要每输入一个数据都进行一次快排或者插入排序，这样做的效率并不