精华内容
下载资源
问答
  • 哈希原理

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

    哈希原理

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

    一、哈希的概念

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

    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(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源码

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

    千次阅读 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字符对应表:

    Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    Base 32 0 1 2 3 4 5 6 7 8 9 b c d e f
    Decimal 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
    Base 32 h j k m n p q r s t u v w x y
    展开全文
  • 一致性哈希原理: 含义:是一种哈希算法,本质就是在移除或添加一个节点的时候没尽可能小地改变已存在key的映射关系。 基本思想:使用相同的哈希算法将数据和结点都映射到环形哈希空间中, 主要处理流程: 1 把数据映射...

    一致性哈希原理:
    含义:是一种哈希算法,本质就是在移除或添加一个节点的时候没尽可能小地改变已存在key的映射关系。
    基本思想:使用相同的哈希算法将数据和结点都映射到环形哈希空间中,
    主要处理流程:
    1 把数据映射到哈希空间
    2 把结点映射到哈希空间
    可以使用节点id,或服务器ip作为关键字进行哈希
    3 把数据映射到结点
    在环形空间,沿着某个方向,从数据的key值出发,直到遇见一个结点机器,就将
    该数据存储在这个结点上。
    本质就是用数据的哈希值到结点的哈希列表上通过二分查找找到距离该数据哈希值最近的下标,
    然后获取到哈希列表在该下标对应的值,然后根据<哈希值,结点名称>的映射中找到处理该数据
    的结点名称。
    4 移除结点
    受影响的就是沿着环形列表中原先存储在这个结点的数据,现在需要将这些数据
    沿着环形方向映射到下一个结点上。
    5 增加结点
    将沿着环形方向,离该增加结点对应哈希值最近的数据映射到新添加的节点上
    6 虚拟结点
    为了解决分布不平衡问题,引入虚拟结点,该虚拟结点是实际结点在哈希空间的复制品,
    一个实际结点对应若干虚拟结点,因为随机性,虚拟结点会随机分布在整个哈希环中,
    使得平衡性提高


    参考:
    王道程序员求职宝典
     

    展开全文
  • minHash最小哈希原理

    2016-11-28 18:21:00
    minHash最小哈希原理 收藏 初雪之音 发表于 9个月前 阅读 208 收藏 9 点赞 1 评论 0 摘要: 在数据挖掘中,一个最基本的问题就是比较两个集合的相似度。通常通过遍历这两个集合...

    minHash最小哈希原理

    • 发表于 9个月前
    • 阅读 208
    • 收藏 9
    • 点赞 1
    • 评论 0
    摘要: 在数据挖掘中,一个最基本的问题就是比较两个集合的相似度。通常通过遍历这两个集合中的所有元素,统计这两个集合中相同元素的个数,来表示集合的相似度;这一步也可以看成特征向量间相似度的计算(欧氏距离,余弦相似度)。当这两个集合里的元素数量异常大(特征空间维数很大),同时又有很多个集合需要判断两两间的相似度时,传统方法会变得十分耗时,最小哈希(minHash)可以用来解决该问题。

    前言

           在数据挖掘中,一个最基本的问题就是比较两个集合的相似度。通常通过遍历这两个集合中的所有元素,统计这两个集合中相同元素的个数,来表示集合的相似度;这一步也可以看成特征向量间相似度的计算(欧氏距离,余弦相似度)。当这两个集合里的元素数量异常大(特征空间维数很大),同时又有很多个集合需要判断两两间的相似度时,传统方法会变得十分耗时,最小哈希(minHash)可以用来解决该问题。

    Jaccard相似度

           在本例中,我们仅探讨集合的相似度,先来看Jaccard相似度。假设有两个集合A,B,则

           Jaccard(A, B)= |A ∩ B| / |A ∪ B|,我们举一个例子:

     

           在上述例子中,sim(A,B)=2/7。

    minHash最小哈希

           假设现在有4个集合,分别为S1,S2,S3,S4;其中,S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d},所以全集U={a,b,c,d,e}。我们可以构造如下0-1矩阵:

           为了得到各集合的最小哈希值,首先对矩阵进行随机行打乱,则某集合(某一列)的最小哈希值就等于打乱后的这一列第一个值为1的行所在的行号。举一个例子:

           定义一个最小哈希函数h,用于模拟对矩阵进行随机行打乱,打乱后的0-1矩阵为

           如图所示,h(S1)=2, h(S2)=4, h(S3)=0, h(S4)=2。

           在经过随机行打乱后,两个集合的最小哈希值相等的概率等于这两个集合的Jaccard相似度,证明如下:

           现仅考虑集合S1和S2,那么这两列所在的行有下面3种类型:
           1、S1和S2的值都为1,记为X
           2、只有一个值为1,另一个值为0,记为Y
           3、S1和S2的值都为0,记为Z

           S1和S2交集的元素个数为x,并集的元素个数为x+y,所以sim(S1,S2) = Jaccard(S1,S2) = x/(x+y)。接下来计算h(S1)=h(S2)的概率,经过随机行打乱后,从上往下扫描,在碰到Y行之前碰到X行的概率为x/(x+y),即h(S1)=h(S2)的概率为x/(x+y)。

    最小哈希签名

    ---------------------------------------------------

     

    最小签名的计算

     

               其实得到上面的签名矩阵之后,我们就可以用签名矩阵中列与列之间的相似度来计算集合间的Jaccard相似度了;但是这样会带来一个问题,就是当一个特征矩阵很大时(假设有上亿行),那么对其进行行打乱是非常耗时,更要命的是还要进行多次行打乱。               为了解决这个问题,可以通过一些随机哈希函数来模拟行打乱的效果。具体做法如下:

     

               假设我们要进行n次行打乱,则为了模拟这个效果,我们选用n个随机哈希函数h1,h2,h3…hn(注意,这里的h跟上面的h不是同一个哈希函数,只是为了方便,就不用其他字母了)。处理过程如下:

     

    令SIG(i,c)表示签名矩阵中第i个哈希函数在第c列上的元素。开始时,将所有的SIG(i,c)初始化为Inf(无穷大),然后对第r行进行如下处理:

     

    1.      计算h1(r), h2(r)…hn(r);

     

    2.      对于每一列c:

     

    a)        如果c所在的第r行为0,则什么都不做;

     

    b)        如果c所在的第r行为1,则对于每个i=1,2…n,将SIG(i,c)置为原来的SIG(i,c)和hi(r)之间的最小值。

     

    (看不懂的直接看例子吧,这里讲的比较晦涩)

     

    例如,考虑上面的特征矩阵,将abcde换成对应的行号,在后面加上两个哈希函数,其中h1(x)=(x+1) mod 5,h2(x) = (3*x+1) mod 5,注意这里x指的是行号:


    接下来计算签名矩阵。一开始时,全部初始化为Inf:


    接着看特征矩阵中的第0行;这时S2和S3的值为0,所以无需改动;S1和S4的值为1,需改动。h1= 1,h2= 1。1比Inf小,所以需把S1和S4这两个位置对应的值替换掉,替换后效果如下:


    接着看第1行;只有S3的值为1;此时h1= 2,h2= 4;对S3那一列进行替换,得到:


    接着看第2行;S2和S4的值为1;h1=3,h2=2;因为签名矩阵S4那一列的两个值都为1,比3和2小,所以只需替换S2那一列:


    接着看第3行;S1,S3和S4的值都为1,h1=4, h2= 0;替换后效果如下:


    接着看第4行;S3值为1,h1=0, h2= 3,最终效果如下:


    这样,所有的行都被遍历一次了,最终得到的签名矩阵如下:


    基于这个签名矩阵,我们就可以估计原始集合之间的Jaccard相似度了。由于S2和S4对应的列向量完全一样,所以可以估计SIM(S1,S4)=1;同理可得SIM(S1,S3) = 0.5;


    局部敏感哈希算法(LSH)

     

             通过上面的方法处理过后,一篇文档可以用一个很小的签名矩阵来表示,节省下很多内存空间;但是,还有一个问题没有解决,那就是如果有很多篇文档,那么如果要找出相似度很高的文档,其中一种办法就是先计算出所有文档的签名矩阵,然后依次两两比较签名矩阵的两两;这样做的缺点是当文档数量很多时,要比较的次数会非常大。那么我们可不可以只比较那些相似度可能会很高的文档,而直接忽略过那些相似度很低的文档。接下来我们就讨论这个问题的解决方法。

     

             首先,我们可以通过上面的方法得到一个签名矩阵,然后把这个矩阵划分成b个行条(band),每个行条由r行组成。对于每个行条,存在一个哈希函数能够将行条中的每r个整数组成的列向量(行条中的每一列)映射到某个桶中。可以对所有行条使用相同的哈希函数,但是对于每个行条我们都使用一个独立的桶数组,因此即便是不同行条中的相同列向量,也不会被哈希到同一个桶中。这样,只要两个集合在某个行条中有落在相同桶的两列,这两个集合就被认为可能相似度比较高,作为后续计算的候选对;下面直接看一个例子:

     

    例如,现在有一个12行签名矩阵,把这个矩阵分为4个行条,每个行条有3行;为了方便,这里只写出行条1的内容。


    可以看出,行条1中第2列和第4列的内容都为[0,2,1],所以这两列会落在行条1下的相同桶中,因此不过在剩下的3个行条中这两列是否有落在相同桶中,这两个集合都会成为候选对。在行条1中不相等的两列还有另外的3次机会成为候选对,因为他们只需在剩下的3个行条中有一次相等即可。

             经过上面的处理后,我们就找出了相似度可能会很高的一些候选对,接下来我们只需对这些候选队进行比较就可以了,而直接忽略那些不是候选对的集合

    ---------------------------------------------------

           那么,怎样得到P( h(S1)=h(S2) )呢?我们仅需要进行N次哈希运算模拟N次随机行打乱,然后统计|h(S1)=h(S2)|,就有 P=|h(S1)=h(S2)| / N 了。有了上一章节的证明,我们就可以通过多次进行最小哈希运算,来构造新的特征向量,也就是完成了降维,得到的新矩阵称为最小哈希签名矩阵。举一个例子,假设进行2次最小哈希运算,h1(x)=(x+1) mod 5,h2(x) = (3*x+1) mod 5,可以得到签名矩阵SIG:

           计算得到sim(S1,S4)=1,sim(S1,S3)=0.5。当然本例数据量太小,签名矩阵的估计值跟真实Jaccard误差较大。

           这里提供一种仅扫描一次就可以得到最小签名矩阵的算法:

           令SIG(i,c)表示签名矩阵中第i个哈希函数在第c列上的元素。开始时,将所有的SIG(i,c)初始化为Inf(无穷大),然后对第r行进行如下处理:
    1. 计算h1(r), h2(r)…hn(r);
    2. 对于每一列c:
           a) 如果c所在的第r行为0,则什么都不做;
           b) 如果c所在的第r行为1,则对于每个i=1,2…n,将SIG(i,c)=min(SIG(i,c),hi(r))。

           再看不懂的可以参考minHash(最小哈希)和LSH(局部敏感哈希)

    MinHash的应用

           MinHash可以应用在推荐系统中,将上述0-1矩阵的横轴看成商品,竖轴看成用户,有成千上万的用户对有限的商品作出购买记录,具体可以参考基于协同过滤,NMF和Baseline的推荐算法一文。MinHash也可以应用在自然语言处理的文本聚类中,将上述0-1矩阵的横轴看成文档,竖轴看成词汇或n-gram。这里我提出一种基于依赖树的同义词聚类算法:

           假设现有没有语法错误的文本集,我们使用依赖树工具得到上图的边,先用TF-IDF逆文档频率过滤得到我们想要聚类的词汇,然后用倒排索引建立类似ESA的词汇-概念向量,例如:

           发展:nsubj(~,交通),advmod(~,比较),relcl(地方,~),mark(~,的)

           发达:nsubj(~,交通),advmod(~,比较),relcl(地方,~),mark(~,的)

           这样,就有待聚类的词汇有限,概念数量庞大的情形,应用minHash完成降维,再来聚类,具体可以参考从n-gram中文文本纠错,到依存树中文语法纠错以及同义词查找一文。

    LSH局部敏感哈希

           我们得到签名矩阵后,对集合还是需要进行两两比较,假如集合数量也极度庞大的话,我们希望仅比较那些相似度可能很高的集合,而直接忽略那些相似度很低的集合,LSH就可以用来解决该问题。

           LSH用到“桶”的概念,直接举一个例子,现有一个12行的签名矩阵,我们设置桶大小为3,则可分为4个桶,如下图:

           对于S2,我们仅需要寻找那些桶相同的集合来计算相似度,例如:

           我们仅需要计算sim(S2, S3),sim(S2, S4),sim(S2, S5),因为这些集合出现过与S2桶相同的情况。再不懂可以看minHash(最小哈希)和LSH(局部敏感哈希)一文。

    Reference

    minHash(最小哈希)和LSH(局部敏感哈希)

    MinHash (最小哈希)

    转载于:https://www.cnblogs.com/sddai/p/6110704.html

    展开全文
  • 全域哈希原理与实现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变换成固定长度的...
  • Vue学习笔记十一:路由的跳转原理(哈希原理) Vue版本:2.5.21 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-...
  • 一致性哈希原理说明

    万次阅读 2020-12-13 18:42:06
    一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。 但现在一致性hash算法在分布式系统中也得到了广泛应用,研究过memcached缓存数据库的人都知道,memcached服务器端本身不...
  • 一致性哈希原理应用

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

    2019-03-18 17:46:52
    原理 基本概念 一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,...
  • 实现集群软负载均衡时候可以使用。...一致性哈希原理 1、http://blog.csdn.net/sparkliang/article/details/5279393 一致性哈希的JAVA实现(hash采用了murmurhash算法) 2、http://www.blogj...
  • 本文总结了一致性哈希的算法原理和Java实现,并列举了其应用。作者:王克锋出处:https://kefeng.wang/2018/08/10/consistent-hashing/版权:自由转载-非商用-非衍生-保持署名,转载请标明作者和出处。 1 概述 1
  • 一致性哈希常用于分布式缓存中,本文主要介绍一致性哈希算法的原理及特点 1)一致性哈希算法原理 一致性哈希算法是将每个Node节点映射到同一个圆上。将各Node的key采用hash计算,可得到一个整数数组。将该数组...
  • 一致性哈希通过哈希环实现KEY到对应Node的映射: 具体算法过程为:先构造一个长为2^32的整数环,根据节点的Hash值将Node(服务器)分配到环的对应位置上,然后计算需要查询数据的键值KEY的哈希值,然后在哈希环上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,278
精华内容 3,311
关键字:

哈希原理