学了哈希$hash$,字符串哈希

有点难

滚动哈希函数的本质：进制转换法

基数转换法（经典，重要）把key看作其他进制（十三进制），转换成十进制。

哈希函数选取的总原则：尽量减少地址冲突，同时要考虑哈希函数的计算时间复杂度。

越随机越好（尽量构造一一映射）

所以哈希函数的构造也是一门（数学）学问 在 OI 中，最常见的情况是 key 为整数的情况。

当键值的范围比较小的时候，可以直接把键值作为数组的下标。

转载于zfj课件

这周我们开始疯狂复习数据结构，还学了​并查集​。并查集就是​键与值的映射​。

还学了​哈希​。

哈希分为数值哈希和字符串哈希。数值哈希有取余法和​进制转换法​。字符串哈希原理就是进制转换法，用了秦九韶算法实现。

哈希的思想就是​化繁为简​，将复杂的键映射在简单的值上。

转载于hyr博客

这周学习了哈希与字符串哈希，做了门票和字串查找

哈希就是哈希函数搞哈希值

学习了进制转换法和滚动哈希

滚动哈希要推公式

转载于lty博客

今天讲了亿些题目

A1369. 合并果子(fruit)

用优先队列把消耗体力小的排前面依次合并

A1371. 看病

优先队列按照病情严重程度排序

A1372. 小明的账单

两个队列一个从大到小一个从小到到，依次输出

A1373. 鱼塘钓鱼(fishing）

优先队列按照鱼塘中鱼的多少排序

A1344. 【例4-4】最小花费

dijkstra套壳……加个百分比

P1629. 邮递员送信

dijkstra反向存图或floyd

转载于yzz博客

第14课 哈希与字符串哈希

这周学了哈希和字符串哈希

哈希

哈希表，又称散列表。使用​映射​，将索引转换到具体的值。

传入的索引通过哈希函数映射到哈希表中的值。

哈希函数通常有​除余法​、基数转换法

字符串哈希

将字符串传入哈希函数存入哈希表。

使用​滚动哈希算法​，将字符串特定位置（如 S[L, R]），转成哈希值，存入哈希表。

时间非常快，查找时间为 O(1)。

转载于hmz博客