系列文章目录

前言

一、HASH概述

• 哈希冲突

字符串Hash

• 字符串Hash

树哈希

---

前言

补昨日

一、HASH概述

Hash其实是一种散列技术，散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。即：存储位置=f（关键字）。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。

哈希冲突

在理想的情况下，每一个 关键字，通过哈希函数计算出来的地址都是不一样的。但是在实际情况中，我们常常会碰到两个关键字key1≠key2,但是f(key1) = f(key2), 这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。

字符串Hash

字符串Hash

Hash[r]=s[1]*pr+s[2]*pr-1…s[r]*p0 

Hash[l-1]=s[1]*pl-1+s[2]*pl-2…s[l-1]*p0

Hash[l~r]=s[l]*pr-l+s[l+1]*pr-l-1…s[r]*p0

void get_hash(){ 
	return ((hash[r]-hash[l-1]*pow(p,r-l+1))%mod+mod)%mod; 
} 

• 双哈希

树哈希