精华内容
下载资源
问答
  • 全域哈希原理与实现1-hash哈希介绍2-Universal hashing全域哈希法3-构造一个全域哈希H\mathcal{H}H4-python实现 1-hash哈希介绍 hash函数y=h(k)y=h(k)y=h(k),把任意长度的输入kkk通过散列算法hhh变换成固定长度的...
  • 哈希原理

    千次阅读 多人点赞 2020-03-10 12:20:03
    哈希原理 C++11提供的unordered系列的容器之所以在查找方面能够达到O(1)O(1)O(1)的复杂度,是因为其底层使用了哈希的结构 一、哈希的概念: 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此...

    哈希原理

    C++11提供的unordered系列的容器之所以在查找方面能够达到 O ( 1 ) O(1) O(1)的复杂度,是因为其底层使用了哈希的结构

    一、哈希的概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为 O ( N ) O(N) O(N),平衡树中为树的高度,即 O ( l o g   2 N ) O(log~2 N) O(log 2N)搜索的效率取决于搜索过程中元素的比较次数

    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素

    当向该结构中:

    1. 插入元素
      根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放

    2. 搜索元素
      对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

    该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)

    在这里插入图片描述

    用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快

    问题:按照上述哈希方式,向集合中插入元素44,会出现什么问题?

    二、哈希冲突

    对于两个数据元素的关键字ki 和kj (i != j),有 ki != kj ,但有:Hash( ki) == Hash(kj),即:不同关键字通过 相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞

    把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢?

    三、哈希函数

    引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:

    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0 到m-1之间
    • 哈希函数计算出来的地址能均匀分布在整个空间中
    • 哈希函数应该比较简单

    常见哈希函数

    1. 直接定制法–(常用)
      取关键字的某个线性函数为散列地址Hash(Key)= A*Key + B
      优点:简单、均匀 。
      缺点:需要事先 知道关键字的分布情况
      使用场景:适合查找比较小且连续的情况

    2. 除留余数法--(常用)
      设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函 数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址

    3. 平方取中法
      假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况

    4. 折叠法
      折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加 求和,并按散列表表长,取后几位作为散列地址。
      折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况

    5. 随机数法
      选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为 随机数函数。
      通常应用于关键字长度不等时采用此法

    6. 数学分析法

    四、解决哈希冲突的方法

    1. 闭散列

    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那 么可以把key存放到冲突位置中的“下一个” 空位置中去

    那如何寻找下一个空位置呢?

    1. 线性探测
      比如前面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,因此44理论 上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突
      线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止
    • 插入
      a.通过哈希函数获取待插入元素在哈希表中的位置
      b.如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探 测找到下一个空位置,插入新元素
      c.d.e.
    • 删除
      采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他 元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响因此线性探测采用标 记的伪删除法来删除一个元素
    // 哈希表每个空间给个标记
    // EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
    enum State{EMPTY, EXIST, DELETE}
    

    线性探测的实现

    // 注意:假如实现的哈希表中元素唯一,即key相同的元素不再进行插入
    // 为了实现简单,此哈希表中我们将比较直接与元素绑定在一起
    template<class K, class V>
    class HashTable
    {
    	struct Elem
    	{
    		pair<K, V> _val;
    		State _state;
    	};
    	
    public:
    	HashTable(size_t capacity = 3)
    	: _ht(capacity)
    	, _size(0)
    	{
    		for(size_t i = 0; i < capacity; ++i)
    		_ht[i]._state = EMPTY;
    	}
    	
    	bool Insert(const pair<K, V>& val)
    	{
    		// 检测哈希表底层空间是否充足
    		// _CheckCapacity();
    		size_t hashAddr = HashFunc(key);
    		// size_t startAddr = hashAddr;
    		while(_ht[hashAddr]._state != EMPTY)
    		{
    			if(_ht[hashAddr]._state == EXIST &&
     				    _ht[hashAddr]._val.first == key)
    				return false;
    			hashAddr++;
    			if(hashAddr == _ht.capacity())
    				hashAddr = 0;
    		/*
    		// 转一圈也没有找到,注意:动态哈希表,该种情况可以不用考		虑,哈希表中元素个数
    		到达一定的数量,哈希冲突概率会增大,需要扩容来降低哈希冲突,	因此哈希表中元素是不会存满的
    		if(hashAddr == startAddr)
    				return false;
    		*/
    		}
    		// 插入元素
    		_ht[hashAddr]._state = EXIST;
    		_ht[hashAddr]._val = val;
    		_size++;
    		return true;
    	}
    	
    	int Find(const K& key)
    	{
    		size_t hashAddr = HashFunc(key);
    		while(_ht[hashAddr]._state != EMPTY)
    		{
    			if(_ht[hashAddr]._state == EXIST && 					
    				_ht[hashAddr]._val.first == key)
    				return hashAddr;
    				
    			hashAddr++;
    		}
    		return hashAddr;
    	}
    	
    	bool Erase(const K& key)
    	{
    		int index = Find(key);
    		if(-1 != index)
    		{
    			_ht[index]._state = DELETE;
    			_size++;
    			return true;
    		}
    		return false;
    	}
    	
    	size_t Size()const;
    	
    	bool Empty() const;
    	
    	void Swap(HashTable<K, V, HF>& ht);
    	
    private:
    	size_t HashFunc(const K& key)
    	{
    		return key % _ht.capacity();
    	}
    	
    private:
    	vector<Elem> _ht;
    	size_t _size;
    };
    

    思考:哈希表什么情况下进行扩容?如何扩容

    在这里插入图片描述

    void CheckCapacity()
    {
    	if(_size * 10 / _ht.capacity() >= 7)
    	{
    		HashTable<K, V, HF> newHt(GetNextPrime(ht.capacity));
    		for(size_t i = 0; i < _ht.capacity(); ++i)
    		{
    			if(_ht[i]._state == EXIST)
    				newHt.Insert(_ht[i]._val);
    		}
    		Swap(newHt);
    	}
    }
    

    线性探测优点:实现非常简单,

    线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据 了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。如何缓解呢?

    2.二次探测

    线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系,因为找空位置的方式就 是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:Hi = (H0 + i^2)%m, 或者: Hi = (H0 + i^2)% mH(i + 1) = (H0 + (i + 1)^2)% m,所以H(i + 1) = Hi + 2i + 1。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行 计算得到的位置,m是表的大小。

    对于前面如果要插入44,产生冲突,使用解决后的情况为:

    在这里插入图片描述

    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置 都不会被探查两次因此只要表中有一半的空位置,就不会存在表满的问题在搜索时可以不考虑表装 满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容

    因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷

    2. 开散列

    1. 开散列概念
      开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码 归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结 点存储在哈希表中

    在这里插入图片描述
    从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素

    1. 开散列实现
    template<class V>
    struct HashBucketNode
    {
    	HashBucketNode(const V& data)
    	: _pNext(nullptr), _data(data)
    	{}
    	HashBucketNode<V>* _pNext;
    	V _data;
    };
    // 本文所实现的哈希桶中key是唯一的
    
    template<class V>
    class HashBucket
    {
    	typedef HashBucketNode<V> Node;
    	typedef Node* PNode;
    public:
    	HashBucket(size_t capacity = 3)
    	: _size(0)
    	{ 
    		_ht.resize(GetNextPrime(capacity), nullptr);
    	}
    	// 哈希桶中的元素不能重复	
    	PNode* Insert(const V& data)
    	{
    		// 确认是否需要扩容。。。
    		// _CheckCapacity();
    		// 1. 计算元素所在的桶号
    		size_t bucketNo = HashFunc(data);
    		// 2. 检测该元素是否在桶中
    		PNode pCur = _ht[bucketNo];
    		while(pCur)
    		{
    			if(pCur->_data == data)
    				return pCur;
    			pCur = pCur->_pNext;
    		}
    		// 3. 插入新元素
    		pCur = new Node(data);
    		pCur->_pNext = _ht[bucketNo];
    		_ht[bucketNo] = pCur;
    		_size++;	
    		return pCur;
    	}
    	// 删除哈希桶中为data的元素(data不会重复),返回删除元素的下一个节点
    	PNode* Erase(const V& data)
    	{
    		size_t bucketNo = HashFunc(data);
    		PNode pCur = _ht[bucketNo];
    		PNode pPrev = nullptr, pRet = nullptr;
    		while(pCur)
    		{
    			if(pCur->_data == data)
    			{
    				if(pCur == _ht[bucketNo])
    					_ht[bucketNo] = pCur->_pNext;
    				else
    					pPrev->_pNext = pCur->_pNext;
    				pRet = pCur->_pNext;
    				delete pCur;
    				_size--;
    				return pRet;
    			}
    		}
    	return nullptr;
    	}
    	
    	PNode* Find(const V& data);
    
    	size_t Size()const;
    
    	bool Empty()const;
    
    	void Clear();
    
    	bool BucketCount()const;
    
    	void Swap(HashBucket<V, HF>& ht;
    
    	~HashBucket();
    
    private:
    
    	size_t HashFunc(const V& data)
    	{
    		return data%_ht.capacity();
    	}
    private:
    	vector<PNode*> _ht;
    	size_t _size; // 哈希表中有效元素的个数
    }
    1. 开散列增容
      桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容,那该条件

    怎么确认呢?开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容

    void _CheckCapacity()
    {
    	size_t bucketCount = BucketCount();
    	if(_size == bucketCount)
    	{
    		HashBucket<V, HF> newHt(bucketCount);
    		for(size_t bucketIdx = 0; bucketIdx < bucketCount; 			
    							++bucketIdx)
    		{
    			PNode pCur = _ht[bucketIdx];
    			while(pCur)
    			{
    				// 将该节点从原哈希表中拆出来
    				_ht[bucketIdx] = pCur->_pNext;
    				// 将该节点插入到新哈希表中
    				size_t bucketNo = newHt.HashFunc(pCur->_data);
    				pCur->_pNext = newHt._ht[bucketNo];
    				newHt._ht[bucketNo] = pCur;
    				pCur = _ht[bucketIdx];
    			}
    		}
    		newHt._size = _size;
    		this->Swap(newHt);
    	}
    }
    
    1. 开散列的思考

    只能存储key为整形的元素,其他类型怎么解决?

    // 哈希函数采用处理余数法,被模的key必须要为整形才可以处理,此处提供将key转化为整形的方法
    // 整形数据不需要转化
    template<class T>
    class DefHashF
    {
    public:
    	size_t operator()(const T& val)
    	{
    		return val;
    	}
    };
    
    // key为字符串类型,需要将其转化为整形
    class Str2Int
    {
    public:
    	size_t operator()(const string& s)
    	{
    		const char* str = s.c_str();
    		unsigned int seed = 131; // 31 131 1313 13131 131313
    		unsigned int hash = 0;
    		while (*str)
    		{
    			hash = hash * seed + (*str++);
    		}
    	return (hash & 0x7FFFFFFF);
    	}
    };
    
    // 为了实现简单,此哈希表中我们将比较直接与元素绑定在一起
    template<class V, class HF>
    class HashBucket
    {
    	// ……
    private:
    	size_t HashFunc(const V& data)
    	{
    		return HF()(data.first)%_ht.capacity();
    	}
    };
    

    除留余数法,最好模一个素数,如何每次快速取一个类似两倍关系的素数?

    const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    {
    	53ul, 97ul, 193ul, 389ul, 769ul,
    	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	1610612741ul, 3221225473ul, 4294967291ul
    };
    
    size_t GetNextPrime(size_t prime)
    {
    	size_t i = 0;
    	for(; i < PRIMECOUNT; ++i)
    	{
    		if(primeList[i] > prime)
    			return primeList[i];
    	}
    	return primeList[PRIMECOUNT - 1];
    }
    

    开散列与闭散列比较

    应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上: 由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间

    最后最后再说一下开散列和闭散列能否用vector自定义的扩容方式
    答案是不可以

    • vector底层的扩容方式为:申请新空间–>拷贝元素—>释放旧空间,
    • 在闭散列和开散列中共同的问题是:在计算哈希地址的时候用到data%capacity,而vector是直接拷贝过来,在完成扩容后,capacity已经改变,再去用data%capacity就无法正确找到元素
    • 而在开散列中,vector每个元素存放的是每个哈希链的首地址,在释放旧空间的时候就已经把哈希链释放掉了,在新空间中却仍然在使用,就会发生错误

    五、模拟实现哈希

    github源码

    展开全文
  • 感知哈希原理及实现

    千次阅读 2016-04-17 17:55:34
    1、基于低频的均值哈希  一张图片就是一个二维信号,它包含了不同频率的成分。如下图所示,亮度变化小的区域是低频成分,它描述大范围的信息。而亮度变化剧烈的区域(比如物体的边缘)就是高频的成分,它描述...

    1、基于低频的均值哈希

           一张图片就是一个二维信号,它包含了不同频率的成分。如下图所示,亮度变化小的区域是低频成分,它描述大范围的信息。而亮度变化剧烈的区域(比如物体的边缘)就是高频的成分,它描述具体的细节。或者说高频可以提供图片详细的信息,而低频可以提供一个框架。

          而一张大的,详细的图片有很高的频率,而小图片缺乏图像细节,所以都是低频的。所以我们平时的下采样,也就是缩小图片的过程,实际上是损失高频信息的过程。

           均值哈希算法主要是利用图片的低频信息,其工作过程如下:

    (1)缩小尺寸:去除高频和细节的最快方法是缩小图片,将图片缩小到8x8的尺寸,总共64个像素。不要保持纵横比,只需将其变成8*8的正方形。这样就可以比较任意大小的图片,摒弃不同尺寸、比例带来的图片差异。

    (2)简化色彩:将8*8的小图片转换成灰度图像。

    (3)计算平均值:计算所有64个像素的灰度平均值。

    (4)比较像素的灰度:将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

    (5)计算hash值:将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。(我设置的是从左到右,从上到下用二进制保存)。

           计算一个图片的hash指纹的过程就是这么简单。刚开始的时候觉得这样就损失了图片的很多信息了,居然还能有效。简单的算法也许存在另一种美。如果图片放大或缩小,或改变纵横比,结果值也不会改变。增加或减少亮度或对比度,或改变颜色,对hash值都不会太大的影响。最大的优点:计算速度快!

            这时候,比较两个图片的相似性,就是先计算这两张图片的hash指纹,也就是64位0或1值,然后计算不同位的个数(汉明距离)。如果这个值为0,则表示这两张图片非常相似,如果汉明距离小于5,则表示有些不同,但比较相近,如果汉明距离大于10则表明完全不同的图片。


    //均值Hash算法
    string HashValue(Mat &src)
    {
    	string rst(64, '\0');
    	double dIdex[64];
    	int k = 0;
    	double mean = 0.0;
    	Mat img;
    
    	//描述一个像素点,如果是灰度,那么只需要一个数值来描述它,就是单通道。 
    	//如果有RGB三种颜色来描述它,就是三通道
    	if (src.channels() == 3)
    	{
    		//1,计算灰度值
    		cvtColor(src, src, CV_BGR2GRAY);
    		img = Mat_<double>(src);
    	}
    	else
    	{
    		img = Mat_<double>(src);
    	}
    
    	//2,将图片缩小到8x8的尺寸,总共64个像素,去除图片的细节
    	resize(img, img, Size(8, 8));
    
    	/*3,计算平均值。*/
    	for (int i = 0; i < 8; ++i) {
    		for (int j = 0; j < 8; ++j)
    		{
    			dIdex[k] = img.at<double>(i, j);
    			mean += img.at<double>(i, j) / 64;
    			++k;
    		}
    	}
    
    	/* 4,计算哈希值,将每个像素的灰度,与平均值进行比较。大于或等于平均值记为1,小于平均值记为0*/
    
    	for (int i = 0; i<64; ++i)
    	{
    		if (dIdex[i] >= mean)
    		{
    			rst[i] = '1';
    		}
    		else
    		{
    			rst[i] = '0';
    		}
    	}
    
    	return rst;
    }
    



    2、增强版:pHash

           均值哈希虽然简单,但受均值的影响非常大。例如对图像进行伽马校正或直方图均衡就会影响均值,从而影响最终的hash值。存在一个更健壮的算法叫pHash。它将均值的方法发挥到极致。使用离散余弦变换(DCT)来获取图片的低频成分。

           离散余弦变换(DCT)是种图像压缩算法,它将图像从像素域变换到频率域。然后一般图像都存在很多冗余和相关性的,所以转换到频率域之后,只有很少的一部分频率分量的系数才不为0,大部分系数都为0(或者说接近于0)。下图的右图是对lena图进行离散余弦变换(DCT)得到的系数矩阵图。从左上角依次到右下角,频率越来越高,由图可以看到,左上角的值比较大,到右下角的值就很小很小了。换句话说,图像的能量几乎都集中在左上角这个地方的低频系数上面了。

           pHash的工作过程如下:

    (1)缩小尺寸:pHash以小图片开始,但图片大于8*8,32*32是最好的。这样做的目的是简化了DCT的计算,而不是减小频率。

    (2)简化色彩:将图片转化成灰度图像,进一步简化计算量。

    (3)计算DCT:计算图片的DCT变换,得到32*32的DCT系数矩阵。

    (4)缩小DCT:虽然DCT的结果是32*32大小的矩阵,但我们只要保留左上角的8*8的矩阵,这部分呈现了图片中的最低频率。

    (5)计算平均值:如同均值哈希一样,计算DCT的均值。

    (6)计算hash值:这是最主要的一步,根据8*8的DCT矩阵,设置0或1的64位的hash值,大于等于DCT均值的设为”1”,小于DCT均值的设为“0”。组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。

           结果并不能告诉我们真实性的低频率,只能粗略地告诉我们相对于平均值频率的相对比例。只要图片的整体结构保持不变,hash结果值就不变。能够避免伽马校正或颜色直方图被调整带来的影响。

            与均值哈希一样,pHash同样可以用汉明距离来进行比较。(只需要比较每一位对应的位置并算计不同的位的个数)


    //pHash算法
    string pHashValue(Mat &src)
    {
    	Mat img, dst;
    	string rst(64, '\0');
    	double dIdex[64];
    	double mean = 0.0;
    	int k = 0;
    	if (src.channels() == 3)
    	{
    		//1,计算灰度值
    		cvtColor(src, src, CV_BGR2GRAY);
    		img = Mat_<double>(src);
    	}
    	else
    	{
    		img = Mat_<double>(src);
    	}
    
    	/* 2,缩放尺寸*/
    
    	resize(img, img, Size(32, 32));
    
    
    
    	/* 3,离散余弦变换,DCT系数求取*/
    
    	dct(img, dst);
    
    
    	/* 4,求取DCT系数均值(左上角8*8区块的DCT系数)*/
    
    	for (int i = 0; i < 8; ++i) {
    		for (int j = 0; j < 8; ++j)
    		{
    			dIdex[k] = dst.at<double>(i, j);
    			mean += dst.at<double>(i, j) / 64;
    			++k;
    		}
    	}
    
    
    	/* 5,计算哈希值。*/
    
    	for (int i = 0; i<64; ++i)
    	{
    		if (dIdex[i] >= mean)
    		{
    			rst[i] = '1';
    		}
    		else
    		{
    			rst[i] = '0';
    		}
    	}
    
    	return rst;
    }


    展开全文
  • 哈希原理与常见哈希函数

    千次阅读 2020-01-09 18:11:06
    一,什么是哈希 哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。 转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过...

    一,什么是哈希

    哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。

    哈希函数

    1.哈希特点

    (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。

    F(x)=rand() :每次返回一个随机值,是不好的哈希
    

    (2)散列性:不同的值的哈希值尽量不同,理想情况下每个值对应于不同的数字。

    F(x)=1 : 不管输入什么都返回1,是不好的哈希
    
    2.冲突怎么解决

    把一个大的集合映射到一个固定大小的集合中,肯定是存在冲突的。这个是抽屉原理或者叫鸽巢理论。

    桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

    (1)拉链法:

    链表地址法是使用一个链表数组来存储相应数据,当hash遇到冲突的时候依次添加到链表的后面进行处理。Java里的HashMap是拉链法解决冲突的典型应用场景。

    Java8 HashMap

    Java8的HashMap中,使用一个链表数组来存储数据,根据元素的哈希值确定存储的数组索引位置,当冲突时,就链接到元素后面形成一个链表,Java8中当链表长度超过8的时候就变成红黑树以优化性能,红黑树也可以视为拉链法的一种变形。

    (2)开放地址法

    开放地址法是指大小为 M 的数组保存 N 个键值对,其中 M >N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。

    线性探测法,就是比较常用的一种“开放地址”哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。简单来说就是:一旦发生冲突,就去寻找下 一个空的散列表地址,只要散列表足够大,空的散列地址总能找到。

    Java8中的HashTable就是用线性探测法来解决冲突的。

        public synchronized V put(K key, V value) {
            // Make sure the value is not null
            if (value == null) {
                throw new NullPointerException();
            }
    
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    
            addEntry(hash, key, value, index);
            return null;
        }
    
        private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            if (count >= threshold) {
                // Rehash the table if the threshold is exceeded
                rehash();
    
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // Creates the new entry.
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }
    
    

    (2)冲突解决示例

    举个例子,假如散列长度为8,哈希函数是:y=x%7。两种解决冲突的方式如下:

    拉链法解决冲突
    拉链法

    线性探测法解决冲突
    线性探测法

    二,几个常见哈希算法

    1.MD5

    MD5哈希算法是将任意字符散列到一个长度为128位的Bit数组中,得出的结果表示为一个32位的十六进制数字。

    MD5哈希算法有以下几个特点:

    1. 正像快速:原始数据可以快速计算出哈希值
    2. 逆向困难:通过哈希值基本不可能推导出原始数据
    3. 输入敏感:原始数据只要有一点变动,得到的哈希值差别很大
    4. 冲突避免:很难找到不同的原始数据得到相同的哈希值

    算法过程:

    1. 数据填充:

    将原数据的二进制值进行补齐。

    (1)填充数据:使得长度模除512后得到448,留出64个bit来存储原信息的长度。填充规则是填充一个1,后面全部是0。

    (2)填充长度数据:计算原数据的长度数据,填充到最后的64个bit上,如果消息长度数据大于64bit就使用低64位的数据。

    第一步:填充数据

    1. 迭代计算:

    将填充好的数据按照每份512的长度进行切分,对每一份依次进行处理,每份的处理方式是使用四个函数进行依次进行计算,每个函数都有四个输入参数,输出也是四个数字,输出的数字作为下一份数据的输入,所有份数的数据处理完毕,得到的四个数字连接起来就是最终的MD5值。

    以下图片是整个迭代计算的过程示意图,其中四个初始参数和四个函数定义如下:

    //四个初始参数值
    A=0x67452301;
    B=0xefcdab89;
    C=0x98badcfe;
    D=0x10325476;
    
    //四个函数的定义
    // a、b、c、d是每次计算时候的四个参数
    F=(b&c)|((~b)&d);
    F=(d&b)|((~d)&c);
    F=b^c^d;
    F=c^(b|(~d));
    

    第二步:数据计算

    1. md5的java实现
    package com.chybin.algorithm.chapter2;
    
    /**
     * Create By 鸣宇淳 on 2019/12/26
     **/
    public class MD5{
        /*
         *四个链接变量
         */
        private final int A=0x67452301;
        private final int B=0xefcdab89;
        private final int C=0x98badcfe;
        private final int D=0x10325476;
        /*
         *ABCD的临时变量
         */
        private int Atemp,Btemp,Ctemp,Dtemp;
    
        /*
         *常量ti
         *公式:floor(abs(sin(i+1))×(2pow32)
         */
        private final int K[]={
                0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
                0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
                0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
                0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
                0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
                0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
                0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
                0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
                0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
                0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
                0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
                0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
                0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
        /*
         *向左位移数,计算方法未知
         */
        private final int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
                12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
                4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
                15,21,6,10,15,21,6,10,15,21,6,10,15,21};
    
    
        /*
         *初始化函数
         */
        private void init(){
            Atemp=A;
            Btemp=B;
            Ctemp=C;
            Dtemp=D;
        }
        /*
         *移动一定位数
         */
        private    int    shift(int a,int s){
            return(a<<s)|(a>>>(32-s));//右移的时候,高位一定要补零,而不是补充符号位
        }
        /*
         *主循环
         */
        private void MainLoop(int M[]){
            int F,g;
            int a=Atemp;
            int b=Btemp;
            int c=Ctemp;
            int d=Dtemp;
            for(int i = 0; i < 64; i ++){
                if(i<16){
                    F=(b&c)|((~b)&d);
                    g=i;
                }else if(i<32){
                    F=(d&b)|((~d)&c);
                    g=(5*i+1)%16;
                }else if(i<48){
                    F=b^c^d;
                    g=(3*i+5)%16;
                }else{
                    F=c^(b|(~d));
                    g=(7*i)%16;
                }
                int tmp=d;
                d=c;
                c=b;
                b=b+shift(a+F+K[i]+M[g],s[i]);
                a=tmp;
            }
            Atemp=a+Atemp;
            Btemp=b+Btemp;
            Ctemp=c+Ctemp;
            Dtemp=d+Dtemp;
    
        }
        /*
         *填充函数
         *处理后应满足bits≡448(mod512),字节就是bytes≡56(mode64)
         *填充方式为先加一个0,其它位补零
         *最后加上64位的原来长度
         */
        private int[] add(String str){
            int num=((str.length()+8)/64)+1;//以512位,64个字节为一组
            int strByte[]=new int[num*16];//64/4=16,所以有16个整数
            for(int i=0;i<num*16;i++){//全部初始化0
                strByte[i]=0;
            }
            int    i;
            for(i=0;i<str.length();i++){
                strByte[i>>2]|=str.charAt(i)<<((i%4)*8);//一个整数存储四个字节,小端序
            }
            strByte[i>>2]|=0x80<<((i%4)*8);//尾部添加1
            /*
             *添加原长度,长度指位的长度,所以要乘8,然后是小端序,所以放在倒数第二个,这里长度只用了32位
             */
            strByte[num*16-2]=str.length()*8;
            return strByte;
        }
        /*
         *调用函数
         */
        public String getMD5(String source){
            init();
            int strByte[]=add(source);
            for(int i=0;i<strByte.length/16;i++){
                int num[]=new int[16];
                for(int j=0;j<16;j++){
                    num[j]=strByte[i*16+j];
                }
                MainLoop(num);
            }
            return changeHex(Atemp)+changeHex(Btemp)+changeHex(Ctemp)+changeHex(Dtemp);
    
        }
        /*
         *整数变成16进制字符串
         */
        private String changeHex(int a){
            String str="";
            for(int i=0;i<4;i++){
                str+=String.format("%2s", Integer.toHexString(((a>>i*8)%(1<<8))&0xff)).replace(' ', '0');
    
            }
            return str;
        }
        /*
         *单例
         */
        private static MD5 instance;
        public static MD5 getInstance(){
            if(instance==null){
                instance=new MD5();
            }
            return instance;
        }
    
        private MD5(){};
    
        public static void main(String[] args){
            String str=MD5.getInstance().getMD5("123");
            System.out.println(str);
        }
    }
    
    2.SHA

    SHA类似MD5,也是一种信息摘要算法,也是将任意长度的字符串转换为固定长度的数字的算法。SHA算法是一个家族,有五个算法:SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512。这些变体除了生成摘要的长度、循环运行的次数等一些微小差异外,算法的基本结构是一致的。

    SHA-1算法的结果是一个160个bit的数字,比MD5的128个bit要长32位,碰撞几率要低了2^32倍。可是SHA-1和MD5一样已经被人破解,已经不安全了。

    SHA-256从名字上看就表明了它的值存储在长度为256的bit数组中的,SHA-512信息摘要长度是512个bit。

    SHA-224是SHA256的精简版本,SHA-384是SHA-512的精简版本,精简版本主要用在安全等级要求不太高的场景,比如只是验证下文件的完整性。使用什么版本的SHA取决于安全要求和算法速度,毕竟长度越长算法计算时间约长,但是安全等级高。

    在这里插入图片描述

    SHA算法过程:

    SHA算法的底层原理和MD5很相似,只是在摘要分段和处理细节上有少许差别,他们都是第一步将原数据进行填充,填充到512的整数倍,填充的信息包括10数据填充和长度填充,第二步切分为相同大小的块,第三步进行对每一块迭代,每块进行N轮运算,最终得到的值拼接起来就是最终的哈希值。

    以下是MD5、SHA-1、SHA-2系列的算法过程比较:

    MD5算法过程示意图:

    MD5是对每一块数据分为四个部分,用四个函数进行运算。最终生成128位的哈希值。

    MD5算法过程

    SHA-1算法过程示意图:

    SHA-1是将每一块数据分为五个部分。

    SHA-1算法过程

    SHA-2算法过程示意图:

    SHA-2是分为八个部分,算法也更加复杂。

    SHA-2算法过程

    3.SimHash

    SimHash是Google提出的一种判断文档是否重复的哈希算法,他是将文本转换为一个64位的哈希值,然后计算两个哈希值的距离,如果小于n(n一般是3)就认为这两个文本是相似的。

    之所以能够这样判断是否相似是因为SimHash算法不同于MD5之类的算法,SimHash算法是局部敏感的哈希算法,MD5算法是全局敏感的哈希算法。在MD5中原数据只要有一个字符的变化,哈希值就会变化很大,而在SimHash算法中,原数据变化一小部分,哈希值也只有很小一部分的变化,所以只要哈希值很类似,就意味着原数据就很类似。

    算法实现:

    参考这个博客【[Algorithm] 使用SimHash进行海量文本去重】

    (1)第一步:哈希

    1. 分词: 将文本进行分词,并给单词分配权重。
    2. hash: 对每个次进行hash计算,得到哈希值。
    3. 加权: 对每个单词的has进行加权。
    4. 合并: 把上一步加权hash值合并累计起来。
    5. 降维: 把上一步累加起来的值变为01。如果每一位大于0 记为 1,小于0 记为 0。

    (2)第二步:计算海明距离

    两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。

    举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。

    异或就是如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。两个simhash值进行异或,得出的结果中1的个数就是海明距离。

    simhash计算过程

    判断两个文本是否相似,就计算两个simhash哈希值的海明距离,根据经验,如果海明距离小于3就可以判定两个文本是相似的。

    4.GeoHash

    GeoHash 算法将经纬度哈希为一个数字,然后将数字base32编码为一个字符串。

    比如:北海公园的经纬度是:(39.928167,116.389550),对应的GeoHash值可以为wx4g、wx4g0、wx4g0s、wx4g0s8、wx4g0s8q。GeoHash值代表的是这个经纬度点所在的一个矩形区域,长度越长矩形面积约小,表示的越精确。

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    两个位置的GeoHash值前部分一样的位数越多,说明两个位置离得越近,百度地图的查找附近、滴滴打车查找附近的车辆功能就可以使用这个算法。

    GeoHash算法过程

    下面对于北海公园的经纬度(39.928167,116.389550)进行编码,了解下算法过程。

    (1)第一步:纬度编码

    将整个地球从水平方向上进行逐步切分,确定纬度39.928167在哪个区域中。

    纬度范围是-90到90,每次平均分为两份,进行逐步细化地迭代。

    1. 第一次迭代:处于-90到0的标记为0,0到90的标记为1,39.928167处于1的区间,所以最终结果的第一位是1。
    2. 第二次迭代:对上一步标记为1的部分平分,0到45标记为0,45到90标记为1,39.928167标记为1处于0的区间,所以最终结果的第二位是0。
    3. 第三次迭代:对上一步标记为0的部分平分,0到22.5标记为0,22.5到45标记为1,39.928167标记为1处于0的区间,所以最终结果的第三位是0
    4. 第四次迭代:对上一步标记为0的部分平分,22.5到33.75标记为0,33.75到45标记为1,39.928167标记为1处于1的区间,所以最终结果的第三位是1。

    经过N次迭代后,得到一个长度为N的二进制值,比如得到的值为1011100011,这个就是对纬度进行的编码最终值。

    纬度编码示意图

    (2)第二步:经度编码

    对经度的编码过程跟对纬度编码过程十分类似,不同点是经度范围是-180到180,对经度116.389550经过N次迭代后得到编码值。比如得到1101001011。这个就是对经度编码的最终值。

    (3)第三步:合并经纬度

    对纬度编码值、经度编码值进行合并,合并规则是奇数位放纬度、偶数位放经度,合并为一个新的二进制串。

    (4)第四步:转换为字符串

    将上一步合并的二进制11100 11101 00100 01111每5位一段转换为十进制,结果是28、29、4、15,Base32编码后为wx4g。这个就是北海公园的经纬度(39.928167,116.389550)最终的GeoHash编码值。

    以下图表是二进制数字、base32字符对应表:

    Decimal0123456789101112131415
    Base320123456789bcdef
    Decimal16171819202122232425262728293031
    Base32hjkmnpqrstuvwxy
    展开全文
  • 一致性哈希原理及特点

    千次阅读 2018-01-23 18:44:48
    一致性哈希常用于分布式缓存中,本文主要介绍一致性哈希算法的原理及特点 1)一致性哈希算法原理 一致性哈希算法是将每个Node节点映射到同一个圆上。将各Node的key采用hash计算,可得到一个整数数组。将该数组...

    一致性哈希常用于分布式缓存中,本文主要介绍一致性哈希算法的原理及特点

    1)一致性哈希算法原理

    一致性哈希算法是将每个Node节点映射到同一个圆上。将各Nodekey采用hash计算,可得到一个整数数组。将该数组排序后,首尾相连即是一个圆。如下图所示,Nodekey分布在圆的不同弧段上。同理,若有一请求keyhash后落入该圆的某一弧段(下图三角点所示),顺时针方向寻得离其最近的节点即为其服务节点(下图Node2)。这样每个节点覆盖了圆上从上一节点到其本身的一段弧段区间。如某一节点失效,之前落入其弧段区间的请求即会顺时针移到与其相邻的节点(下图如Node2失效,之前落入Node3Node2弧段的请求会落入Node1)。而未落入失效弧段区间的节点则不受影响(之前落入Node2Node3弧段的请求,当Node2失效后不受影响)。增加节点的场景与此类似,新的节点承载一段新区间,这样,落入失效节点至新节点弧段的请求会被新节点所承载。



    在节点固定的情况下,为了增加节点在圆上分布的均匀性与分散性,可以设置节点的replicas(副本数)。下图将replicas设置为2,各节点承载的弧段范围已更加精细且于整体而言分布更加分散。所以适当调节replicas参数可以提高算法的均衡性。


    2)一致性哈希的特点

    1平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

    2单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。 

    3分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。 

    4负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    实现代码:http://blog.csdn.net/skh2015java/article/details/79142915

    参考及推荐阅读地址:

    http://blog.csdn.net/cywosp/article/details/23397179/

    https://leileiluoluo.com/posts/consistent-hashing-and-high-available-cluster-proxy.html




    展开全文
  • 哈希原理

    千次阅读 2019-07-08 18:05:07
    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后...
  • Hashtable中key/value键值对均为object类型,所以Hashtable可以支持任何类型的key/value键值对 <BR><BR>在哈希表中添加一个key/value键值对:HashtableObject.Add(key,value); 在哈希表中去除某个key/value键值对:...
  • 一致性哈希原理说明

    万次阅读 2020-12-13 18:42:06
    一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。 但现在一致性hash算法在分布式系统中也得到了广泛应用,研究过memcached缓存数据库的人都知道,memcached服务器端本身不...
  • 一致性哈希通过哈希环实现KEY到对应Node的映射: 具体算法过程为:先构造一个长为2^32的整数环,根据节点的Hash值将Node(服务器)分配到环的对应位置上,然后计算需要查询数据的键值KEY的哈希值,然后在哈希环上...
  • 9张图,带你了解一致性哈希原理

    千次阅读 多人点赞 2021-10-19 21:35:10
    假设我们使用的哈希算法得到的哈希值返回值是int类型,则本身相当于已经取过模。 因此我们标记出三台机器在环上的位置 这个时候,需要将文件映射到环上,使用一样的哈希函数,即hash(文件名)。假设这里有4个文件,...
  • C++ 哈希表的原理

    2021-01-15 15:01:56
    其基本的原理就是把任意长度的输入、通过Hash算法变成固定长度的输出。 这个映射的规则就是对应的Hash算法,而原始数据映射后的二进制串就是哈希值 比如常用加密方式:MD5和SHA都是Hash算法: echo md5("这是一个...
  • 一致性哈希原理详解(虚拟节点)

    万次阅读 2018-03-20 15:56:58
    转自:http://www.cnblogs.com/haippy/archive/2011/12/10/2282943.html一致性Hash算法背景 一致性哈希算法在1997年由麻省理工学院的Karger...一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2...
  • 一致性哈希原理应用

    千次阅读 2021-01-27 14:09:28
    文章目录一致性哈希前言一、基本概念/原理二、优势1.服务器故障宕机节点减少2.扩容/动态添加服务器三、存在问题及解决方案1.哈希环偏斜2.新增节点数据命中问题四、应用场景总结 前言 本文主要讲明一致性哈希的 ...
  • 一致性哈希算法的原理与实现

    万次阅读 多人点赞 2018-08-13 14:08:29
    分布式系统中对象与节点的映射关系,传统方案是使用对象的哈希值,对节点个数取模,再映射到...本文总结了一致性哈希的算法原理和Java实现,并列举了其应用。 作者:王克锋 出处:https://kefeng.wang/2018/08/1...
  • redis之Hash哈希类型以及存储原理

    千次阅读 2020-03-28 18:51:36
    2.Hash哈希类型的相关命令 2.1.命令参考地址:http://redisdoc.com/hash/hexists.html 2.2.设置key的单个field属性值:hset gaoxinfu en_name frank 127.0.0.1:6379> hset gaoxinfu en_name frank (integer) 1 ...
  • 一致性哈希原理: 含义:是一种哈希算法,本质就是在移除或添加一个节点的时候没尽可能小地改变已存在key的映射关系。 基本思想:使用相同的哈希算法将数据和结点都映射到环形哈希空间中, 主要处理流程: 1 把数据映射...
  • C++哈希表的原理和使用

    千次阅读 2020-08-18 14:48:02
    我们把这种对应关系f称为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块存储空间中,这块连续空间称为散列表或哈希表(Hash-Table)。 2、散列表的构造方法 2.1、直接定址法 直接定址法使用下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 140,011
精华内容 56,004
关键字:

哈希原理