首页 > 其他分享 >树哈希 Hints

树哈希 Hints

时间:2024-11-07 20:46:51浏览次数:1  
标签:hash 函数 hsh 加减 哈希 Hints

简化代码

注意 hash 的值具有可加减的特性,可以极大程度的简化代码。

同时可以维护可能作为答案的 “匹配池” 中的 hash 值,这样就不用进行(超级 dirty work 的)树加减了。

树哈希是一种集合哈希(?),所以支持加减!!!

hash 函数

我也不知道为什么大家都在用这个 hash 函数

ull shift(ull x) {return x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= mask, x;}
mask = mtrnd() * mtrnd();

当然,这个函数够随机就行(应该)。

特征值

  1. 无根树 hash 也可以采取“把以每个节点为根得到的 hsh 值都加起来(注意用另一个 hsh 函数)”(这个不知道好不好,但是好写,可能不够强)
  2. 重心
  3. 深度/节点大小

标签:hash,函数,hsh,加减,哈希,Hints
From: https://www.cnblogs.com/SkyMaths/p/18533948

相关文章

  • 代码随想录一刷day7 哈希表day1
    遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。常见三种实现哈希表的数据结构:数组set集合map映射下面是setmap的红黑树是一种平衡二叉搜索树,所以k......
  • 代码随想录第七天|哈希表part02--454.四数相加II、383. 赎金信、15. 三数之和、18. 四
    资源引用:leetcode题目:454.四数相加Ⅱ(454.四数相加II-力扣(LeetCode))383.赎金信(383.赎金信-力扣(LeetCode))15.三数之和(15.三数之和-力扣(LeetCode))18.四数之和(18.四数之和-力扣(LeetCode))例行碎碎念:今天也追赶上了一些进度,虽然生病感冒,但今天很好的坚持了从早到晚......
  • 代码随想录之哈希表刷题总结
    1.哈希表理论基础哈希表-(hashtable),数组其实就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。如下图:1.1哈希函数把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。哈希函数如下图......
  • windows如何获取文件的哈希值
    在Windows系统中,可以使用以下几种方法来获取文件的哈希值:使用PowerShell在PowerShell中运行以下命令即可计算文件的SHA256哈希值:  Get-FileHash-Path<文件路径>-AlgorithmSHA256 其中 <文件路径> 是待计算哈希值的文件的完整路径。使用ce......
  • 算法专题:哈希表
    目录1、1.两数之和1.1算法原理1.2算法代码2、面试题01.02.判定是否互为字符重排2.1算法原理 2.2算法代码3、217.存在重复元素3.1算法原理  3.2算法代码4、219.存在重复元素II4.1算法原理4.2算法代码5、49.字母异位词分组5.1算法原理 5.2算......
  • 哈希函数与数据完整性 (^=◕ᴥ◕=^)
    哈希函数与数据完整性:保护猫咪世界的小鱼干(^=◕ᴥ◕=^)在数字世界中,我们总是希望确保传输和存储的数据没有被篡改,就像猫咪们想保护它们珍贵的小鱼干不被“偷吃”一样。为此,哈希函数(HashFunctions)成为了一个强大而可靠的工具。哈希函数能生成独特的数据“指纹”,用以验证数据的......
  • 哈希算法(闭散列) - 线性探测 / 二次探测(缺支持string数据插入)
    一.哈希初步1.哈希的思想哈希算法的思想是将要存储的顺序按照一定规律进行存储,查询时也依据此规律进行查询相对于string字符串,会选择开辟一个大小为26的数组,将字母(仅小写)按照Ascall码表进行映射,统计其出现的次数相对于没有规律的数据而言,常采用取模的方法(%数组大小),......
  • C语言数据结构之哈希表(HASHTABLE)的实现
    C语言数据结构之哈希表(HASHTABLE)的实现哈希表的每个节点保存的数据格式为key:value,其中key为字符串,根据字符串内容采用不同方法(哈希函数)生成一个无符号整型哈希码,根据表的长度,采用取余法,将数据存入表单元,如果此表单元中已存在数据,则以此表单元为链表头,向链表追加数据,这......
  • 哈希表
    #include<stdio.h>#include<iostream>#include<algorithm>#include<vector>#include<random>#include<time.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>#include<unordered_m......
  • 用哈希表封装myunordered_map和myunordered_set
    在学习这个之前,已经学习过,myunordered_map和myunordered_set的基本用法和哈希表怎么用哈希思想模拟实现;因此为了更深入的了解myunordered_map和myunordered_set与哈希表的内容,我们来自己用哈希表模拟实现myunordered_map和myunordered_set;这种模拟实现和之前模拟实现map与set......