精华内容
下载资源
问答
  • 哈希结构
    千次阅读
    2019-08-24 16:23:24

    C++11中新增4个unordered系列关联式容器
    unordered_map说明

    • unordered_map存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与其对应的value.
    • 在unordered_map中,键值通常作为唯一标识元素,而映射值只是一个对象,其内容与此键关联,键和映射值的类型可能不同
    • unoedered_map并没有对<key, value>按照特定的顺序排序,为了能在常数范围内找到key所在的value, unordered_map将相同哈希值得键值放在相同的桶里
    • unordered_map容器通过key访问单个元素比mao快, 但他通常在遍历子集的返回迭代方面效率较低
    • unoodered_map实现直接访问操作符operator[]
      ,允许使用key作为参数直接访问value.

    unordered_map的容量

    函数声明功能介绍
    bool empty() const检测unordered_map是否为空
    size_t size()获取unordered_map的有效元素个数

    unordered_map的迭代器

    函数声明功能
    begin返回unordered_map第一个元素的迭代器
    end返回unordered_map最后一个元素下一个位置的迭代器
    cbegin返回unordered_map第一个元素的const迭代器
    cend返回unordered_map最后一个元素下一个位置的const迭代器

    unordered_map的元素访问

    函数声明功能
    operatot[]返回与key对应的value,没有一个默认值

    unordered_map的查询

    函数声明功能介绍
    iterator find(const K& key)返回key在哈希桶中的位置
    size_t count(const K& key)返回哈希桶中关键码为key的键值对的个数

    unordered_map的修改操作

    函数声明介绍
    insert向容器中插入键值对
    erase删除容器中的键值对
    void clear()清空容器中有效元素个数
    void swap(unordered_map&)交换两个容器中的元素
    size_t bucket(const K& key)返回元素key所在的桶号

    底层结构
    unordered_map系列的关联式容器之所以效率比较高,在于底层实现了哈希结构
    哈希结构
    定义hashfunc使元素的存储位置与它的关键码之间建立一对一映射的关系
    插入元素时,根据待插入元素的关键码,以hashfunc计算出该元素的存储位置,在结构中按此位置进行存放
    搜索元素时,对关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置去元素比较,若关键码相等,则搜索成功
    hash(key) = key % capacity
    哈希冲突
    不同关键字通过哈希函数计算出相同的哈希地址,此时称为哈希冲突,这两关键字称为同义字
    哈希函数
    hashfunc设计原则

    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许m个地址时,其值域必须在0-(m-1)之间

    • 哈希函数计算出来的地址能均匀分布在整个空间中

    • 哈希函数应该比较简单
      常见哈希函数
      1.直接定制法
      取关键字的某个线性函数为散列地址: hash (key) = A*Key +B,
      优点: 简单,均匀,缺点: 需要提前知道关键字的分布情况
      使用场景:适合查找小且连续的场景
      2.除留余数法
      设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p(尽量选择一个素数)作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
      哈希冲突解决
      两种常见的方法: 闭散列和开散列
      闭散列
      即: 开放定址法,当哈希表未满,在插入同义字时,可以把key值存放在下一个空位置(线性探测)
      线性探测: 从发生冲突的位置开始,依次向后探测,直到寻找下一个空位置为止.

    • 插入
      通过哈希函数获取插入元素在哈希表中的位置.
      如果该位置没有元素则插入新元素,如果该位置有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素.

    • 删除
      采用闭散列删除处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其它元素的的搜索.此时线性探测采用标记的伪删除来删除一个元素

    // 哈希表每个空间给个标记
    // EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
    enum State{EMPTY, EXIST, DELETE};
    

    线性探测优点 : 实现简单
    线性探测缺点 : 一旦发生哈希冲突 , 所有的冲突连接在一起,容易产生数据"堆积", 即: 不同关键占据了可利用空间,是寻找某关键码的位置需要多次比较,导致速率降低,因而进行二次探测
    开散列
    开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    开单列增容
    桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发
    生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增.

    更多相关内容
  • //构造一个键出来 充当哈希地址的求解 char element[20]; //数据类型 }DATA,*LPDATA; typedef struct hashTable { LPDATA* table; //便于初始化,以及判断当前hash地址是否存在冲突 int d.

    哈希地址

    • 哈希地址是一个逻辑地址,不是实际存在的地址,通过哈希函数得到哈希地址

    哈希函数

    • 哈希函数由自己决定,选什么函数都可以,假设用数组存储哈希的数据,在数组中用下标去描述位置,通过数据去构造哈希地址,地址就是数组下标

    • 图中哈希结构的最大容量为 7

    • 一般通过哈希构造函数把数据和下标建立联系

    • 取余法得到哈希地址:数据的哈希地址 == 数据 % p(最大容量),通过 % 7得到哈希地址

    • 通过哈希构造函数,得到哈希地址 88 % 7 == 4 ,余4把它放在数组下标是4的位置 (把当前元素放到以当前哈希地址为下标的容量的位置)

    • 直接定址法:数据是多少,构建出来的哈希地址就是多少,元素是 88,构建出来的哈希地址就是 88,数据就是地址,地址就是数据,图中的元素最小需要的数组长度为 89,浪费空间

    • 平方取中法:把原来的数据做平方,取中间一部分

    • 折叠法:把字符串转为ASCII码,是一个很大的数字,把数字折叠

    哈希冲突

    • 通过1个哈希函数所得到的地址可能存在重复(相同的元素)

    处理哈希冲突

    • 开放地址法:如果要把具有哈希冲突的元素 4 存到哈希结构中,要去数组后面找空的位置,假设数组下标为6的位置有空缺,就把 4 放在这个位置,开放地址法就是把其他空的位置去存储具有哈希冲突的元素

    • 邻接表法:图的方式存储采用的就是邻接表法,不开放后面的元素,以当前位置(存在冲突的位置)去创建一个链表出来,把具有冲突的元素放在当前链表中--->以当前元素当做链表的表头去存储元素

    构建数据类型

    • 如果要处理的是字符串类型的数据,构造一个键出来充当哈希结构的哈希地址的求解--->关联

    • 存字符串,没有整型数据,构建一个整型数据处理充当哈希结构的哈希地址的求解

    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    typedef struct pair 
    {
    	int key;			//键
    	char element[20];	//数据类型--->字符串类型
    }DATA,*LPDATA;
    

     哈希表的创建--->采用取余法

    • 得到的哈希地址是用取余法来做的--->数据%p

    • 通过取余法所求的哈希地址,所产生的地址个数的范围: [0,p-1]

    • divisior的作用:限定哈希地址的数目 & 存储哈希元素

    • 如果用结构体数组充当哈希地址,不好判断空的情况

    typedef struct hashTable 
    {
    	LPDATA* table;	   //数据用二级指针表示 便于初始化,以及判断当前hash地址是否存在冲突
    	int divisor;       //H(key)=key%p -->就是限定hash地址的数目 数据要%p需要传入p
    	int curSize;	   //当前元素个数
    }HASH,*LPHASH;

     哈希结构的结构体描述--->用结构体指针表示哈希结构 

    LPHASH createHashTable(int p) 
    {
    	LPHASH hash = (LPHASH)malloc(sizeof(HASH)); //动态内存申请
    	assert(hash);
        //给数据做初始化
    	hash->curSize = 0;
    	hash->divisor = p;
    	hash->table = (LPDATA*)malloc(sizeof(LPDATA)* hash->divisor); //容量由取余数决定
    	assert(hash->table);
    	for (int i = 0; i < hash->divisor; i++)    //多个一级指针
    	{
    		hash->table[i] = NULL;                 //二级指针申请内存后给每个一级指针做初始化
    	}
    	return hash;
    }

     插入数据

    • 注意先申请内存再插入元素

    • 用的是二级指针,刚刚只申请了一级指针的内存

    //要插入的表 要插入的数据
    void insertData(LPHASH hash, DATA data) 
    {
    	//做插入前先求hash地址--->调用哈希函数                  //不存在哈希冲突
    	int pos = search(hash, data.key);                    //找到要存储数据的哈希地址
    	if (hash->table[pos] == NULL)                        //当前下标没有数据 直接插入
    	{
    		hash->table[pos] = (LPDATA)malloc(sizeof(DATA)); //注意先申请内存再拷贝元素
    		memcpy(hash->table[pos], &data, sizeof(DATA));   //内存拷贝
    		hash->curSize++;
    	}
    	else                                                 //存在哈希冲突
    	{
    		if (hash->table[pos]->key == data.key)           //键相同回到原来位置 
    		{
    			strcpy(hash->table[pos]->element, data.element); //用覆盖元素的方式
    		}
    		else                                             //键不同回到原来位置说明满了
    		{
    			printf("hash表满了,无法插入!\n");             
    			return;
    		}
    	}
    }

     哈希函数 

    • 可能会存在哈希冲突,需要找合适的位置去存放元素,不一定是直接取余,直接取余得到的地址不一定能用

    • 传入键,通过键去找:因为是通过键去生成哈希地址

    • 找完一圈后回到原来的位置(通过取余法),说明没有合适的位置

    • 如果 curPos + 1中没有元素,把元素放在当前位置即可

    //要找的表 传入键
    int search(LPHASH hash, int key) 
    {
    	int pos = key % hash->divisor;  //不存在冲突的hash地址 正常情况
    	int curPos = pos;               //存在冲突 开放地址法做哈希地址的查找
    	do 
    	{
    		//key相同,采用覆盖的数据方式 不当做哈希冲突来做
    		if (hash->table[curPos] == NULL||hash->table[curPos]->key==key)
    			return curPos;          //判断当前位置能不能用 ==NUll说明可以用
    		curPos=(curPos + 1)%hash->divisor; //不为NULL往后走 如果后面为NULL就插到当前位置
    	} while (curPos != pos);        //当前Pos不等于原来Pos就一直去做查找
    	return curPos;                  
    }
    //!= 原来地址一直做查找 
    //== 原来地址:找完一圈后回到原来的位置说明它没有合适的位置 直接返回

    打印哈希表--->打印数组

    void printHash(LPHASH hash) 
    {
    	for (int i = 0; i < hash->divisor; i++) //用最大容量长度做打印
    	{
    		if (hash->table[i] == NULL) 
    		{
    			printf("NULL\n");
    		}
    		else                                //不为空打印元素
    		{
    			printf("%d:%s\n", hash->table[i]->key, hash->table[i]->element);
    		}
    	}
    }

     测试代码

    int main() 
    {
    	LPHASH hash = createHashTable(10);     //创建哈希表
    	DATA array[5] = { 1,"雷电",11,"春天",23,"四月",44,"baby",56,"virtual" };
    	for (int i = 0; i < 5; i++) 
    	{
    		insertData(hash, array[i]);        //把数据插到哈希表中
    	}
    	printHash(hash);                       //打印哈希表
    	return 0;
    }
    //测试代码
    
    NULL
    1:雷电
    11:春天
    23:四月
    44:baby
    NULL
    56:virtual
    NULL
    NULL
    NULL
    展开全文
  • 哈希结构 哈希概念 常见的K-V结构,实现了元素关键码与元素值的映射关系,但没有实现元素关键值与元素存储位置的映射关系,在遍历过程中,一般的顺序表或搜索二叉树要进行关键值的多次比较,其中顺序表的时间...

    哈希结构

    哈希概念

    常见的K-V结构,实现了元素关键码与元素值的映射关系,但没有实现元素关键值与元素存储位置的映射关系,在遍历过程中,一般的顺序表或搜索二叉树要进行关键值的多次比较,其中顺序表的时间复杂度为O(n),二叉搜索树的时间复杂度O(lgn)

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

    哈希函数

    常见哈希函数
    1. 直接定制法
    取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况 
    2. 除留余数法
    设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址

    哈希操作

    • 插入元素

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

    • 搜索元素

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

    • 删除元素

    根据待删除元素的关键码,以此函数计算出该元素的存储位置并按此位置进行删除

    • 哈希冲突解决

    • 闭散列(线性探测法)

    哈希表结构:在闭散列中,将哈希表底层结构设置为vector容器,容器中每一个元素为一个hashNode结构体,包括kv键值对和状态标志位

    初始化将其hashNode的状态设置为空

    template <class k,class v>
    struct HashNode
    {
    	pair<k, v> kv;
    	STATE state = EMPTY;
    };
    
    template <class k, class v>
    class HashTable
    {
    public:
    	typedef HashNode<k, v> Node;
    	HashTable(size_t n = 10)
    		:HSTable(n)
    		,_size(0)
    	{
    	}
    private:
    	vector<Node> HSTable;
    	size_t _size;
    };
    

    上述插入操作,可能会产生哈希冲突,通过线性探测法,从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止,插入一个新元素

    在查找过程值,要想找到发生冲突元素,就必须给标志位

    删除也类似,采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

    enum STATE{
    	EXIST  //已存在
    	,DELETE  //删除过
    	,EMPTY   //空位置
    };

    通过定义一个枚举类型,包括已存在不可插入状态(EXIST),空位置可插入状态(EMPTY),删除过的位置状态(DELETE)

    插入代码如下:

    
    	bool insert(const pair<k, v>& kv)
    	{
    		checkcapacity();
    		//计算hash位置
    		int idx = kv.first%HSTable.size();
    		//搜索
    		while (HSTable[idx].state != EMPTY)//其余两种状态都需要继续查找
    		{
    			//当前位置已经有数据,且与要插入新数据相同,则插入失败
    			if (HSTable[idx].state ==EXIST&& kv.first == HSTable[idx].kv.first)
    				return false;
    			++idx;
    			if (idx == HSTable.size() - 1)//向后查找过程到结尾 从头再开始找空位
    				idx = 0;
    		}
    		//此时找到空位置,插入新元素,状态置为已存在,hash表大小+1
    		HSTable[idx].kv = kv;
    		HSTable[idx].state = EXIST;
    		_size++;
    		return true;
    		//插满扩容
    		
    	}

    由于插入过程实际上是在vector容器基础上完成,如果需要插入元素足够多,可能导致当前所创造的哈希表插满,此时就需要检查容量,进行扩充操作

    扩容判断条件是:负载因子>0.7,此时认为产生冲突的可能性大,需要进行扩容

    扩容并非在原表基础上增大size,而是开辟新表,将原表已存在状态位置元素进行逐一存放,代码如下:

    void checkcapacity()
    	{
    		//负载因子控制是否增容
    		//负载因子越小,冲突越小,但空间浪费越大
    		if (HSTable.size()==0&&_size * 10 / HSTable.size() > 7)
    		{
    			//开新表
    			int newcap = HSTable.size() == 0 ? 10 : 2 * HSTable.size();
    			HashTable<k, v> newHST(newcap);
    			//直接拷贝会导致hash值计算前后不一致
    			//需要重新计算hash位置
    			for (int i = 0; i < HSTable.size(); i++)
    			{
    				if (HSTable[i].state == EXIST)
    				{
    					newHST.insert(HSTable[i].kv);
    				}
    			}
    			swap(newHST);
    		}
    	}
    	void swap(HashTable<k, v>& HT)
    	{
    		swap(HSTable,HT.HSTable);
    		swap(_size, HT._size);
    	}

    查找:由于hash冲突,直接通过索引查找难以找到发生hash冲突而通过线性探测法存放的元素,非空位置逐一查找,如果索引超过了表大小,需要循环从头开始

    Node* find(const k& key)
    	{
    		//计算hash位置
    		int idx = key%HSTable.size();
    		//搜索
    		while (HSTable[idx].state != EMPTY)
    		{
    			if (HSTable[idx].state == EXIST && key == HSTable[idx].first)
    				return &HSTable[idx];
    			++idx;
    			if (idx == HSTable.size() - 1)
    				idx = 0;
    		}
    		return nullptr;
    	}

    删除:删除并非真删除,释放元素,而是改变对应元素位置状态信息

    bool erase(const k& key)
    	{
    		Node* node = find(key);
    		if (node)
    		{
    			node->state = DELETE;
    			_size--;
    			return true;
    		}
    		return false;
    	}
    • 开散列(哈希桶)

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

    bool insert(const V& val)
    	{
    		checkcapacity();
    		KeyofValue kov;
    		int idx = kov(val) % _hst.size();
    
    		//查找
    		Node* cur = _hst[idx];
    		while (cur)
    		{
    			if (kov(cur->_val) == kov(val))
    			{
    				//key重复
    				return false;
    			}
    			cur = cur->_next;
    		}
    		//插入  头插
    		cur = new Node(val);
    		cur->_next = _hst[idx];
    		_hst[idx] = cur;
    		_size++;
    		return true;
    	}
    

    哈希桶通过建立新连接进行扩容操作:

    void checkcapacity()
    	{
    		if (_size == _hst.size())
    		{
    			int newcap = _size == 0 ? 10 : 2 * _size;
    			vector<Node*> newhst(newcap);
    			KeyofValue kov;
    			for (int i = 0; i < _hst.size(); i++)
    			{
    				Node* cur = _hst[i];
    				while (cur)
    				{
    					Node* next = cur->_next;
    					int idx = kov(cur->_val) % newhst.size();
    					//新表头插
    					cur->_next = newhst[idx];
    					newhst[idx] = cur;
    
    					cur = next;
    				}
    				//原表断开 置空
    				_hst[i] = nullptr;
    			}
    			swap(_hst,newhst);
    		}
    	}
    • 迭代器操作:

    迭代器的++步骤:

    #include<iostream>
    #include<vector>
    using namespace std;
    
    template <class V>
    struct HashNode
    {
    	V _val;
    	HashNode<V>* _next;
    
    	HashNode(const V& val)
    		:_val(val)
    		,_next(nullptr)
    	{
    
    	}
    };
    
    //hash表的前置声明
    template<class K, class V, class KeyofValue>
    class HSTable;
    
    
    //hash表迭代器  封装单链表节点
    template<class K, class V, class KeyofValue>
    struct HashIterator{
    	typedef HashNode<V> Node;
    	typedef HSTable<K, V, KeyofValue> ht;
    	typedef HashIterator<K, V, KeyofValue> Self;
    	//成员:节点指针,哈希表指针
    	Node* _node;
    	ht* _hptr;
    
    	HashIterator(Node* node,ht* hptr)
    		:_node(node)
    		,_hptr(hptr)
    	{
    
    	}
    
    	Self& operator++()
    	{
    		if (_node->_next)
    		{
    			_node = _node->_next;
    		}
    		//找下一个非空链表头结点
    		else
    		{
    			//计算当前节点在hash表中位置
    			KeyofValue kov;
    			int idx = kov(_node->_val) % _hptr->_hst.size();
    			//从下一位置开始查找
    			++idx;
    			for (int; idx < _hptr->_hst.size(); idx++)
    			{
    				if (_hptr->_hst[idx])
    				{
    					_node = _hptr->_hst[idx];//找到非空链表头结点给node记录
    					break;
    				}
    			}
    			if (idx = _hptr->_hst.size())//此时走到end位置  将node节点置为空
    			{
    				_node = nullptr;
    			}
    		}
    		return *this;
    	}
    };
    
    
    
    template<class K,class V,class KeyofValue>
    class HSTable
    {
    public:
    	typedef HashNode<V> Node;
    	typedef HashIterator<K, V, KeyofValue> iterator;
    
    	//由于迭代器需要访问其私有成员_hst  声明为友元类
    	friend HashIterator<K, V, KeyofValue>;
    	HSTable(int n=10)
    		:_hst(n)
    		,_size(0)
    	{
    
    	}
    
    	iterator begin()
    	{
    		for (int i = 0; i < _hst.size(); i++)
    		{
    			if (_hst[i])
    			{
    				return iterator(_hst[i], this);
    			}
    			else
    				return iterator(nullptr,this);
    
    		}
    	}
    	iterator end()
    	{
    		return iterator(nullptr, this);
    	}
    
    
    private:
    	vector<Node*> _hst;
    	int _size;
    };
    

    哈希表的应用

    • 位图

    位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。

    比如Tencent的一道面试题:

    给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中

    此题解法较多,一般容易想到的就是暴力求解,直接遍历查询,但海量数据导致时间复杂度过大,无法实际中应用;稍微进阶一些的会想到采用二分查找,虽然相比较于直接遍历,把时间复杂度从O(n)提升到O(lgn),但对于40亿数据还是难以实现

    而通过位图可以实现:数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:

    代码实现如下:

    #include<iostream>
    #include<vector>
    using namespace std;
    
    /*
    位图应用:
    (1)存放不重复数据简单信息,不需要存放数据本身   优点:节省空间,查找效率高
    
    */
    class bitset
    {
    public:
    	//位图内存大小与数据范围有关
    	bitset(size_t range)
    		:_bit(range/32+1)
    	{
    
    	}
    	//存储信息
    	void set(size_t num)
    	{
    		//计算整数位置
    		int idx = num / 32;
    		//计算比特位置
    		int bitidx = num % 32;
    		//对应比特位置1  按位或运算
    		_bit[idx] |= (1 << bitidx);  //把1向左移动bixidx位置  或运算之后  将其置为1
    	}
    	//查找信息
    	bool test(size_t num)
    	{
    		//计算整数位置
    		int idx = num / 32;
    		//计算比特位置
    		int bitidx = num % 32;
    		//对应比特位右移bitidx后 与1 与运算  如果为1 则为1  否则为0
    		return (_bit[idx] >> bitidx)&1;		
    	}
    
    	//删除信息
    	void reset(size_t num)
    	{
    		//计算整数位置
    		int idx = num / 32;
    		//计算比特位置
    		int bitidx = num % 32;
    		//对应比特位置10
    		_bit[idx] &= ~(1 << bitidx);
    	}
    private:
    	//数组
    	vector<int> _bit;
    	//默认bit位个数为 32 位
    };
    • 布隆过滤器

    布隆过滤器是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

    布隆过滤器的实现依然需要借助位图的实现来完成,依然依靠0-1进行标记数据是否存在

    注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。

    • 查找:

    布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。

    • 删除:

    布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。
    比如:删除上图中"tencent"元素,如果直接将该元素所对应的二进制比特位置0,“baidu”元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

    代码如下:

    //布隆过滤器
    // 假设布隆过滤器中元素类型为K,每个元素对应3个哈希函数
    template<class T, class KToInt1, class KToInt2,class KToInt3>
    class BloomFilter
    {
    public:
    	BloomFilter(size_t size) // 布隆过滤器中元素个数
    		: _bmp(3 * size), _bitcount(3 * size)
    	{}
    
    	//存储信息:使用多个bit位存储
    	void set(const T& val)
    	{
    		KToInt1 k1;
    		KToInt2 k2;
    		KToInt3 k3;
    		int idx1 = k1(val) % _bitcount;
    		int idx2 = k2(val) % _bitcount;
    		int idx3 = k3(val) % _bitcount;
    		
    		_bmp.set(idx1);
    		_bmp.set(idx2);
    		_bmp.set(idx3);
    	}
    
    	bool test(const T& val)
    	{
    		KToInt1 k1;
    		KToInt2 k2;
    		KToInt3 k3;
    		int idx1 = k1(val) % _bitcount;
    		int idx2 = k2(val) % _bitcount;
    		int idx3 = k3(val) % _bitcount;
    
    		if (!_bmp.test(idx1))
    			return false;//三个有一个为0 肯定不存在  三个均为1  可能存在(不能说一定存在)
    		if (!_bmp.test(idx2))
    			return false;
    		if (!_bmp.test(idx3))
    			return false;
    		if (_bmp.test(idx1) && _bmp.test(idx2) && _bmp.test(idx3))
    			return true;
    	}
    private:
    	bitset _bmp;
    	size_t _bitcount; // bit位的个数
    };
    
    struct KToInt1
    {
    	//hash函数计算方式1  
    };
    
    struct KToInt2
    {
    	//hash函数计算方式2 
    };
    
    struct KToInt3
    {
    	//hash函数计算方式3 
    };
    void test()
    {
    	BloomFilter<string, KToInt1, KToInt2, KToInt3> bf(10);
    }

     

    展开全文
  • 本程序主要应用了hash结构,为提高效率,并未选择拉连法解决冲突, 发生冲突时利用 双备用hash 函数查找,如果失败再利用线性探查法查找 存储位置的方法 同时,程序设计了用户选项,选择可能出现单词数量,为...
  • 带通配符查询的Winnowing多哈希结构
  • 哈希结构 我们理想的搜索方法是:不进行元素比较,而是对每个元素的存储格式进行改造,通过某种方式,将元素与存储结构建立一一对应的关系。这样就可以通过这种关系快速地找到对应的元素。 插入时: 让插入的元素...
  • 哈希结构

    千次阅读 2013-07-19 03:26:07
    是时候说说哈希结构了。记得以前被人问过哈希结构,问题是:哈希结构最差效率是发生在什么时候?这个问题其实没太多意义,一般只有大学论文喜欢研究这种问题,因为在现实工程中,除非故意或者写错代码才有可能发生...

    是时候说说哈希结构了。记得以前被人问过哈希结构,问题是:哈希结构最差效率是发生在什么时候?这个问题其实没太多意义,一般只有大学论文喜欢研究这种问题,因为在现实工程中,除非故意或者写错代码才有可能发生最差的效率情况。这篇文章将把哈希结构(我所理解的)来个大起底,照遍哈希结构的各个角落,最后,给出自己的哈希结构类。

     

    一步步开始吧。

    l  为什么要有哈希结构?

    大学老师最喜欢的事情就是照本宣科,很少老师(甚至程序员)会问为什么有这种数据结构。知道为什么有哈希结构有助于知识连贯性和理解。

    那么为什么会有哈希结构呢?在学哈希结构的之前,基本都会先接触树,二叉树,平衡二叉树最后到红黑树,这些数据结构时而为了排序用,时而用来查找用。就我所知,红黑树就主要用于存储结构,方便快速查询存储中的数据。那么作为后续的哈希结构,其主要是更强更快的查询,设计哈希的目的,是为了能尽量逼近O(1)时间的查询。

     

    l  哈希的思想

    为了尽量逼近O(1)时间查询,设想查询数据时如同取数组元素一样直接使用数组下标取到数组元素:

    Value = Array[key];

    这个时候就是O(1)时间。因此哈希的主要思想就是:将查找值转为数组下标值,一般来说就是整型int。这个转化过程就是哈希函数,哈希函数是哈希结构效率的核心,越是能将转化后得到的数组下标值均匀的分散在数组各个地方的哈希函数,查找时间越是逼近O(1)。

    为什么只是逼近O(1)而不是O(1)呢?理论上是可以做到O(1)的,但说查找,研究查找,只有超大型数据才有意义,但在有限的数组大小情况下,按O(1)标准存储完所有数据几乎不可能,比如设计一个哈希函数将英文单词转为数组下标int型,若设计一个26(26个字母嘛)进制的数据类型,10个字母长度的单词经过哈希函数转化后得到的整型数据已经是很大的数据了,已经放不下了。

    因此,哈希允许有冲突。所谓冲突,就是两个不同的查询数据,经过哈希函数转化后,其数组下标值是一样的,也就是说他们都想放到数组的同一个位置上。

    解决冲突的方法一般有两种:

    1.        链表法;这个是最最常用的方法,简单也最实用。当发生冲突时,就用一个链表连在发生冲突的位置上,后续冲突的数据都挂在链表上。

    2.        线性探测法;当发生冲突时把冲突元素放到下一个相邻位置,若仍然冲突(即下一个位置已经被霸占),则继续找下一个位置。这种方法实现复杂,最重要的是相比第一种,效率比较低,因为发生随着发生冲突的次数增多,数组最终被填满,这个时候必须重新申请一个更大的数组,一般其情况下,为了保证效率,当填入的数据个数达到数组大小的一半时,就要重新生成更大的数组了。

    其实还有第三种处理冲突的方法,就是二次哈希,也就是说,发生冲突的时候就用另一个哈希函数算出数组下标值,放到另一个哈希结构中。

    说到这,开篇的问题已经有答案了,若哈希函数完全无法将查找数据区分成均匀的数组下标,全部统统冲突在同一个位置,这个时候,哈希结构就会退化为一根链表(或简单的数组),查询的时间就会变成O(N)。

     

    l  如何设计哈希函数

    哈希函数必须保证生成的数组下标能均匀分散,一般采取的方法是取模法。取模的原理很简单,就是把查询值转成整型后对某个整数取模。这个整数,就是哈希结构里面的数组大小。根据一些学术论文的统计,这个整数最好是素数,这个时候区分度更好,并且,其越大,区分度也越好。

     

    现在,就开始写一个自己的哈希结构。这个结构是基于链表法解决冲突的,这个方法是最简单也是最实用的。


    template <class Key, class Value, class F>
    class CListHash
    

    Key就是查询关键字,Value就是对应需要查找的值,F是哈希函数类。F这个类应该提供operator()()函数,在CListHash类里面使用这个函数类对象计算哈希值:

    class CGetHashCode{
    public:
    	int operator()(const int M, const std::string& strWord){
    		int iSum = 0;
    		for (std::string::const_iterator iter = strWord.begin(); iter != strWord.end(); ++iter){
    			char c;
    			if (*iter >= 'A' && *iter <= 'Z'){
    				c = *iter - 'A' + 'a';
    			}else{
    				c = *iter;
    			}
    			iSum |= 1 << (c - 'a');
    		}
    
    		return iSum % MODE;
    	}
    };

    这个只是对F模板的一个具体演示,CGetHashCode这个类中operator()()函数接受M和一个string类,其目的是为了将一个单词转为数组下标,即索引值。这个算法是我自己想出来的,和一般的技术书籍方法不一样,其思想就是按字母表的顺序将一个int(32位)中相应的位设为1,例如b是字母表的第二个字母,则对int的第二位设置为1,最后对M取模。这个时候,当M足够大时,冲突只会发生在字母集一样顺序不一样的单词中(包含重复字母),例如:read,dear和dare。不知道这样的冲突率算不算高,我没进行统计。这里只是演示哈希结构。

    在CListHash中我自己写了一个链表的节点类,并实现了自己的链表,这个当然不打算使用STL的东西:

    struct ValueNode{
    		Value* valueArray;
    		Key k;
    		int N;
    		int current;
    		ValueNode* pNext;
    
    		ValueNode():valueArray(NULL), pNext(NULL), N(0), current(-1){
    
    		}
    		~ValueNode(){
    			delete[] valueArray;
    		}
    
    		void put(const Value& v){
    			if (0 == N){
    				N = 1;
    				current = 0;
    				valueArray = new Value[N];
    				valueArray[current] = v;
    			}else{
    				if (current + 1 == N){
    					N *= 2;
    					Value* newValueArray = new Value[N];
    					for (int i = 0; i <= current; ++i){
    						newValueArray[i] = valueArray[i];
    					}
    					delete[] valueArray;
    					++current;
    					newValueArray[current] = v;
    					valueArray = newValueArray;
    				}else{
    					++current;
    					valueArray[current] = v;
    				}
    			}
    		}
    
    		void remove(const Value& v){
    			for (int i = 0; i <= current; ){
    				if (v == valueArray[i]) {
    					for (int j = i; j < current; ++j){
    						valueArray[j] = valueArray[j + 1];
    					}
    					--current;
    				}else{
    					++i;
    				}
    			}
    		}
    	};

    这个节点类,和vector类似,当往里面存值时,会按2的倍数增长(vector不是按2的倍数增长,但肯定会增长很多)。

    之所以不用STL,首先STL是一个通用库,为了兼顾各种用途,会损失效率,我想,简单代码一般会比兼顾各种情况的复杂代码效率会高点的,更重要的是,可以锻炼自己最基本的写代码能力。

    这个类实际上是写在CListHash里面的,声明为private,外部无法访问。
    const int m_iBufferSize;
    ValueNode** m_Buffer;

    其实就是一个动态的数组,数组大小正是之前所说的M,同样是private属性。数组存放每个索引的第一个链表节点。

    外部遍历每个Key值对应的Value,这个就是遍历类:

    public:
    	class Iterator{
    		Value* m_pValues;
    		friend class CListHash;
    	public:
    		Iterator():m_pValues(NULL){
    
    		}
    
    		Iterator(const Iterator& iter):m_pValues(iter.m_pValues){
    
    		}
    
    		Iterator& operator++(){
    			++m_pValues;
    			return *this;
    		}
    
    		Value operator++(int){
    			Iterator newIter(*this);
    			++m_pValues;
    			return newIter;
    		}
    
    		const Value& operator*(){
    			return *m_pValues;
    		}
    
    		bool operator==(const Iterator& other){
    			return m_pValues == other.m_pValues;
    		}
    
    		bool operator!=(const Iterator& other){
    			return m_pValues != other.m_pValues;
    		}
    	};

    接下来就是哈希结构的实现了:

    public:
    	CListHash(const int size):m_iBufferSize(size){
    		m_Buffer = new ValueNode*[m_iBufferSize];
    		for (int i = 0; i < m_iBufferSize; ++i){
    			m_Buffer[i] = NULL;
    		}
    	}
    
    	void put(const Key& k, const Value& v){
    		int iIndex = F()(m_iBufferSize, k);
    		if (NULL == m_Buffer[iIndex]){
    			m_Buffer[iIndex] = new ValueNode();
    			m_Buffer[iIndex]->put(v);
    			m_Buffer[iIndex]->k = k;
    		}else{
    			ValueNode* p;
    			ValueNode* pre;
    			for (p = m_Buffer[iIndex], pre = m_Buffer[iIndex];
    					NULL != p;
    					pre = p, p = p->pNext){
    				if (k == p->k){
    					break;
    				}
    			}
    			if (NULL != p){
    				p->put(v);
    			}else{
    				pre->pNext = new ValueNode();
    				pre->pNext->put(v);
    				pre->pNext->k = k;
    			}
    		}
    	}
    
    	bool get(const Key& k, Iterator& begin, Iterator& end){
    		int iIndex = F()(m_iBufferSize, k);
    
    		for (ValueNode* p = m_Buffer[iIndex]; NULL != p; p = p->pNext){
    			if (k == p->k){
    				begin.m_pValues = p->valueArray;
    				end.m_pValues = p->valueArray + p->current + 1;
    				return true;
    			}
    		}
    
    		return false;
    	}
    
    	void removeKey(const Key& k){
    		int iIndex = F()(m_iBufferSize, k);
    		ValueNode* pre = NULL;
    		for (ValueNode* p = m_Buffer[iIndex]; NULL != p; pre = p, p = p->pNext){
    			if (k == p->k){
    				if (NULL == pre){
    					m_Buffer[iIndex] = p->pNext;
    					delete p;
    					break;
    				}else{
    					pre->pNext = p->pNext;
    					delete p;
    					break;
    				}
    			}
    		}
    	}
    
    	void removeValue(const Key& k, const Value& v){
    		int iIndex = F()(m_iBufferSize, k);
    		for (ValueNode* p = m_Buffer[iIndex]; NULL != p; p = p->pNext) {
    			if (k == p->k){
    				p->remove(v);
    				break;
    			}
    		}
    	}
    

    实现还是很简单的,哈希的效率是体现在哈希函数的设计上,而不是具体数据结构上。

    以下是测试代码:

    #include "ListHash.h"
    #include <iostream>
    #include <string>
    #include <Windows.h>
    #include <set>
    #include <assert.h>
    
    bool isAlpha(const char c){
    	if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')){
    		return true;
    	}
    	return false;
    }
    
    // 0x2fffffff
    const int MODE = 102131;//12287
    
    struct Position{
    	int iLine;
    	int iIndex;
    };
    
    class CGetHashCode{
    public:
    	int operator()(const int M, const std::string& strWord){
    		int iSum = 0;
    		for (std::string::const_iterator iter = strWord.begin(); iter != strWord.end(); ++iter){
    			char c;
    			if (*iter >= 'A' && *iter <= 'Z'){
    				c = *iter - 'A' + 'a';
    			}else{
    				c = *iter;
    			}
    			iSum |= 1 << (c - 'a');
    		}
    
    		return iSum % MODE;
    	}
    };
    
    int main(){
    	HANDLE hFile = CreateFileA("Alice.txt",
    								GENERIC_READ,
    								FILE_SHARE_READ,
    								NULL,
    								OPEN_EXISTING,
    								FILE_ATTRIBUTE_NORMAL,
    								NULL);
    	if (INVALID_HANDLE_VALUE == hFile){
    		std::cerr << "cannot get vailid file handle" << std::endl;
    		return 1;
    	}
    
    	typedef CListHash<std::string, Position*, CGetHashCode> SearchHash;
    	SearchHash hash(MODE);
    	typedef std::set<std::string> SetTest;
    	SetTest setTest;
    
    	const DWORD dwMustRead = 4 * 1024;// 4k
    	char cRead[dwMustRead];
    	DWORD dwHasRead;
    	BOOL bReadEnd;
    	std::string strWord;
    	int iLine = 0, iIndex = 0;
    	bool bNewWord = false;
    	while (TRUE){
    		bReadEnd = ReadFile(hFile, (LPVOID)cRead, dwMustRead, &dwHasRead, NULL);
    		if (0 == dwHasRead){
    			break;
    		}
    		for (DWORD d = 0; d < dwHasRead; ++d){
    			if (isAlpha(cRead[d])){
    				bNewWord = true;
    				strWord += cRead[d];
    			}else{
    				if (bNewWord){
    					Position* p = new Position();
    					p->iLine = iLine;
    					p->iIndex = iIndex;
    					hash.put(strWord, p);
    					setTest.insert(strWord);
    					strWord.clear();
    					++iIndex;
    					bNewWord =false;
    				}
    				if ('\n' == cRead[d]){
    					++iLine;
    				}
    			}
    		}
    	}
    
    	// dump
    	hash.dump();
    
    	for (SetTest::iterator iter = setTest.begin(); iter != setTest.end(); ++iter) {
    		SearchHash::Iterator begin;
    		SearchHash::Iterator end;
    		if (hash.get(*iter, begin, end)){
    			std::cout << *iter << "->";
    			while (begin != end) {
    				Position* position = *begin;
    				std::cout << "(" << position->iLine << ", " << position->iIndex << ") ";
    				delete position;
    				++begin;
    			}
    			std::cout << std::endl;
    
    			hash.removeKey(*iter);
    		}
    
    		assert(!hash.get(*iter, begin, end));
    	}
    
    	hash.dump();
    
    	Position* position = new Position;
    	position->iIndex = 1998;
    	position->iLine = 2007;
    	hash.put("test", position);
    
    	position = new Position;
    	position->iIndex = 30;
    	position->iLine = 29;
    	hash.put("jack", position);
    
    	position = new Position;
    	Position * pToBeDeleted = position;
    	position->iIndex = 2013;
    	position->iLine = 2015;
    	hash.put("test", position);
    	hash.put("test", position);
    
    	position = new Position;
    	position->iIndex = 8888;
    	position->iLine = 3333;
    	hash.put("test", position);
    
    	hash.removeValue("test", pToBeDeleted);
    
    	SearchHash::Iterator begin;
    	SearchHash::Iterator end;
    	if (hash.get("test", begin, end)) {
    		std::cout << "********** test ****************" << std::endl;
    		while (begin != end) {
    			assert(pToBeDeleted != *begin);
    			Position* p = *begin;
    			std::cout << "(" << p->iLine << ", " << p->iIndex << ") ";
    			++begin;
    		}
    		std::cout << std::endl;
    	}
    
    	CloseHandle(hFile);
    
    	return 0;
    }
    
    
    

    测试是给一本名叫《爱丽丝梦游仙境》的小说中的所有单词建立索引,同时测试CListHash各个函数是否正常工作。可能有人问为什么没有遍历函数,仅仅提供遍历结果的函数,若想遍历当中的所有Key值呢?我是这么想的,哈希的存在不为排序,也不为存储,仅仅为快速查找,因此,我没有提供对Key值的遍历,仅提供了Key对应的Value值遍历函数,更不会有任何排序设计。哈希仅为查找而存在(实际上哈希结构还可以用来描述图,以后再说)。

    我也没有实现operator[]这看上去直观的函数符重载,因为看上去直观,却有左右值的困惑。若operator[]返回临时对象,则无法用做左值,效率亦不高,operator[]若返回引用则内部需要new,这么做毫无意义。


    展开全文
  • 2.按照学号字段建一个哈希表,实现按学号进行查找 务必用哈希结构实现 3.按照姓名字段构建哈希表结构,实现姓名的模糊查询。姓名取中文姓氏作为哈希地址 4.排序 实现多关键字排序 5.分别使用堆排和快排显示成绩前10...
  • 哈希(hash索引)结构和b+树结构的简单介绍。
  • 主要用到数据结构中的哈希表,使用文件IO的操作设计了一个图书管理系统,系统分为分有一个主界面和多个子界面,实现后的效果可以界面切换自如,子界面中设计有学生入口以及老师入口,分别模拟不同的操作,功能都是...
  • 1实验目的 1) 复习顺序查找二分查找分块查找的基本算法及适用场合 2) 掌握哈希查找的基本方法及适用场合并能在解决实际问题时灵活应用 3) 巩固在散列查找时解决冲突的方法及特点 2实验内容 1) 哈希表查找的实现用...
  • 哈希表的结构和特点 hashtable 散列表 查询非常快 结构有很多种 容易理解的顺序表+链表 主结构是顺序表,每个顺序表的节点再单独引出一个链表 哈希表添加数据 计算哈希码(调用hashCode(),结果是一个int值,...
  • 哈希表的数据结构

    2018-06-29 13:57:45
    哈希表的数据结构哈希表的数据结构哈希表的数据结构哈希表的数据结构
  • (5)输出学生的选课信息 通过调用学生信息哈希表,可以实现输出该学生的所有基本信息。(学生的基本信息包括:姓名,班级,性别,学号,选课信息等等) (6)输出课程的选课系统 通过调用课程信息哈希表,可以实现...
  • 散列表的设计实验报告 1题目 散列表的设计:针对某个集体中人名设计一个散列表使得平均查找长度不超过R,并完成相应的建表和查表程序 2基本要求 假设人名为中国人姓名的汉语拼音形式待填入哈希表的人名共30个取平均...
  • 任务要求:针对姓名信息进行初始化哈希表,可以进行显示哈希表,查找元素。 设计思想:哈希函数用除留余数法构造,用线性探测再散列处理冲突。 设人名为中国人姓名的汉语拼音的形式,有30个待入的人名,取平均查找...
  • java数据结构——哈希

    千次阅读 2018-10-13 09:42:53
    哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表,也称为哈希表。...
  • 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 [测试数据] 取读者周围较熟悉的30个人名
  • 网络数据的采集和存储是智能路由控制的基础,为智能路由提供了大量的网络...基于真实网络流量数据的实验证明了相比目前普遍使用的单级哈希存储结构,多级哈希存储结构在存储碰撞率和负载率两方面存在显著的性能优势。
  • 洛阳理工学院实验报告 系部 计算机与信息工程系 班级 学号 姓名 课程名称 数据结构 实验日期 2014.4.23 实验名称 实验5图的遍历的实现 成绩 实验目的 掌握图的邻接矩阵和邻接表两种存储结构掌握图的深度优先和广度...
  • 数据结构 C语言作业/练习 代码完美运行
  • 哈希结构的缺点

    万次阅读 2016-10-02 01:08:42
    哈希表也有一些缺点:它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序虽必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的...
  • 哈希表是我们经常频繁使用的数据结构,所以它的知识点比较重要,如HashMap啊,就是哈希结构哈希表的底层是数组+链表结构的,非常之聪明,两者优点结合,数组查询快,链表增删快,并且hash采用算法分析定位地址,...
  • [c++11]hash哈希结构模板

    千次阅读 2017-02-18 23:22:12
    [c++11]hash哈希结构模板一、哈希结构模板hash简介c++11新增的哈希结构模板定义于头文件 :template struct _Bitwise_hash : public unary_function, size_t> {...};哈希结构模板定义一个函数对象(重载了operator()...
  • 红黑树与哈希表的比较(数据结构!)

    千次阅读 2020-04-11 10:22:31
    哈希表这种结构很好的结合了数组和链表这两种数据结构的优点,他提供元素的相对随机访问能力,如果不发生数据碰撞(即理想状况下,则访问每个元素的时间复杂度都是O(1),这是利用了数组的优点。并且在理想状况下增加...
  • 哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。 有两种不同类型的哈希表:哈希集合(理解为set)和哈希映射(理解为dictionary)。 哈希集合是集合数据结构的实现之一,用于存储非重复值。 哈希...
  • 福 建 工 程 学 院 课 程 设 计 课程 题目 专业 班级 座号 姓名 算法与数据结构 哈希表 网络工程 xxxxxx 班 xxxxxxxxxxxx xxxxxxx 2011 年 12 月 31 日 实验题目哈希表 一 要解决的问题 针对同班同学信息设计一个...
  • 数据结构哈希

    千次阅读 2022-01-24 17:03:11
    数据结构哈希表(解决冲突常用方法)1.什么是哈希表2.构造哈希函数3.解决哈希冲突3.1.开放定址法(开地址法)3.2.链地址法(拉链法) 1.什么是哈希表 散列表(Hash table,也叫哈希表),是根据关键 码值(Key ...
  • 下面小编就为大家带来一篇浅谈innodb的索引页结构,插入缓冲,自适应哈希索引。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • Redis系列-4.哈希(Hash)结构

    千次阅读 2017-09-20 13:21:14
    Redis系列-4.哈希(Hash)结构文章中可能有地方描述偏差,欢迎留言指证Redis系列-4哈希Hash结构 基本 常用命令设置值 获取值 统计field个数 ...判断field是否存在 ...redis本身就是key-value型,哈希结构相当于在v

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 328,518
精华内容 131,407
关键字:

哈希结构