精华内容
下载资源
问答
  • 常见的存储结构及其优缺点

    千次阅读 2020-03-24 01:29:47
    逻辑关系映射到物理存储映射方式有4种:顺序、链式、索引、哈希,相应地就产生了四种存储结构:顺序存储结构、链式存储结构、索引存储结构、哈希存储结构。 顺序存储 特点:存储空间地址连续,数据元素依次存放...

    逻辑关系映射到物理存储的映射方式有4种:顺序、链式、索引、哈希,相应地就产生了四种存储结构:顺序存储结构、链式存储结构、索引存储结构、哈希存储结构

    顺序存储

    • 特点:存储空间的地址连续,数据元素依次存放;利用物理相邻表示(存储)逻辑关系。
    • 优点:存储密度大;可以随机访问,在O(1)内查询、修改元素。
    • 缺点:表示关系能力弱;维护关系困难(逻辑关系发生变化,物理上难同步),在O(n)内插入和删除数据;存储空间必须一次获得(适用性差)。

    链式存储

    • 特点: 占用空间任意,元素任意存放;在存放元素的同时,还存放与其有关系的元素的地址(指针)。
    • 优点:空间任意;显式地存储关系;表示关系的能力强;在O(1)内插入、删除元素(只需改变结点的指针),便于动态管理内存。
    • 缺点:空间开销大,占用空间较多,存储密度小;必须通过指针来访问元素,在O(n)内查找、修改元素。

    索引存储

    • 特点:存储空间是多段连续空间,在存储结点信息的同时,还建立附加的索引表,索引表由若干索引项组成。
    • 优点:顺序和链式结合;数据检索速度快,保证数据的唯一性。
    • 缺点:创建索引和维护索引需要时间,而且索引也会占用一定的物理空间;对数据增删查改的同时也要对索引进行维护。

    哈希存储

    • 特点:又称散列存储,数据元素的存储位置和关键码(在数据结构中,指的是数据元素中能起标识作用的数据项)之间有着确定对应关系,其基本思想是由结点的关键码值决定结点的存储地址,除了用于查找外还可以用于存储,存储空间是连续空间。(有的HASH函数为取模函数)
    • 优点:利用数据的某一特征访问和存储,访问速度快,在O(1)内遍历元素。
    • 缺点:好的HASH很难;有时会产生冲突。
    展开全文
  • 1.顺序存储 平均时间复杂度为O(n) 空间复杂度为O(0)查找,删除,增加时间复杂度为O(0),修改时间复杂度为O(1)优点:存储空间紧凑,容易进行查找缺点:插入删除需要移动大量元素。需要分配大量空间2.索引存储...

    1.顺序存储  

    平均时间复杂度为O(n)   空间复杂度为O(0)

    查找,删除,增加的时间复杂度为O(0),修改的时间复杂度为O(1)

    优点:存储空间紧凑,容易进行查找

    缺点:插入删除需要移动大量元素。需要分配大量空间

    2.索引存储

    元素个数为M 索引数为N   查找的时间复杂度为O(M/N)  插入删除增加的时间复杂度为O(1)

    本质为一个指针数组,数组的每一个元素可以是动态数组,链表,树或者图

    #pragma once
    template<class T>
    class myvector
    {
    public:
    	myvector();
    	~myvector();
    	void push_back(T t);
    	T* find(T t);
    	void show();
    	void change(T* pos, T t);
    	void del(T t);
    	void insert(int pos,T t);
    	T operator [](int i);
    public:
    	T* p;
    	int n;
    	int reallen;
    };
    #include "myvector.h"
    #include <iostream>
    
    using namespace std;
    /*
    myvector();
    ~myvector();
    void push_back(T t);
    T *find(T t);
    void show();
    void change(T *pos, T t);
    void del(T t);
    void insert(T *pos,T t);
    */
    
    template<class T>
    myvector<T>::myvector()
    {
    	p = nullptr;
    	n = reallen = 0;
    }
    
    template<class T>
    myvector<T>::~myvector()
    {
    	if (p != nullptr)
    	{
    		delete[]p;
    		n = reallen = 0;
    	}
    
    }
    //从尾部插入数据
    template<class T>
    void myvector<T>::push_back(T t)
    {
    	if (p == nullptr)
    	{
    		p = new T;
    		*p = t;
    		n = reallen = 1;
    	}
    	else
    	{
    		T* ptemp = new T[n + 1];
    		for (int i = 0;i < n;i++)
    		{
    			ptemp[i] = p[i];
    		}
    		delete[]p;
    
    		p = ptemp;
    
    		p[n] = t;
    
    		reallen += 1;
    		n += 1;
           
    	}
    }
    //查找数据元素返回位置
    template<class T>
    T* myvector<T>::find(T t)
    {
    	for (int i = 0;i < reallen;i++)
    	{
    		if (p[i] == t)
    		{
    			return p + i;
    		}
    	}
    	return nullptr;
    }
    //打印数据元素
    template<class T>
    void myvector<T>::show()
    {
    	if (p == nullptr)
    	{
    		return;
    	}
    	for (int i = 0;i < reallen;i++)
    	{
    		cout << "p[" << i<<"]="<<p[i] << endl;
    	}
    
    }
    //改变数据元素
    template<class T>
    void myvector<T>::change(T *pos, T t)
    {
    		if (pos == nullptr)
    		{
    			 return;
    		}
    		else
    		{
    			*pos = t;
    		}
    }
    //删除数据
    template<class T>
    void myvector<T>::del(T t)
    {
    	int pos = -1;
    	for (int i = 0;i < reallen;i++)
    	{
    		if (p[i] == t)
    		{
    			pos = i;
    			break;
    		}
    	}
    	if (pos != -1)
    	{
    		if (pos == reallen - 1)
    		{
    			reallen -= 1;
    		}
    		else
    		{
    			for (int i = pos;i < reallen - 1;i++)
    			{
    				p[i] = p[i + 1];
    			}
    		}
    	}
    }
    //插入数据
    template<class T>
    void myvector<T>::insert(int pos, T t)
    {
    	if (pos>0 && pos<= n)
    	{
    		
    	//重新分配内存并拷贝
    			
    	  T *ptemp = new T[n + 1];//重新分配内存
     
          for (int i = 0; i < n; i++)
    	  {
    		  *(ptemp + i) = *(p + i);//拷贝  
    	  }
    	  
    	  delete []p;
    	  p = ptemp;
    	  reallen += 1;
    	  n += 1;
    		
    	}
    	for(int i = reallen-2;i>=pos;i--)	
    	  {
    		p[i+1] = p[i];//往前移动
    		}
    		p[pos] = t;	
    }
    //重载操作符
    template<class T>
    T myvector<T>::operator[](int i)
    {
    	if (i < 0 || i >= reallen)
    	{
    		return NULL;
    	}
    	return  p[i];
    }
    #include "myvector.h"
    #include "myvector.cpp"
    #include<iostream>
    //顺序存储
    using namespace std;
    void main1()
    {
    	myvector<int> myv;
    
    	myv.push_back(12);
    	myv.push_back(15);
    	myv.push_back(13);
    	myv.push_back(10);
    
    	myv.insert(2,9);
    
    	cout<<myv.find(12)<<endl;
    
    	myv.change(myv.find(13),8);
    	myv.show();
    
    
    	cin.get();
    
    }
    //索引存储
    void main()
    {
    	myvector<int> mv1;
    	mv1.push_back(1);
    	mv1.push_back(2);
    	mv1.push_back(3);
    	mv1.push_back(4);
    	mv1.push_back(5);
    	myvector<int> mv2;
    	mv2.push_back(11);
    	mv2.push_back(12);
    	mv2.push_back(13);
    	mv2.push_back(14);
    	mv2.push_back(15);
    
    	myvector<myvector<int>*> mvv;
    	//存储的是vector类型的地址,通过地址查找相应内存块获得数据
    	mvv.push_back(&mv1);
    	mvv.push_back(&mv2);
    	mvv[0]->show();
    	mvv[1]->show();
    
    
    	cin.get();
    
    
    	
    
    }

    3.链式存储:

    明确元素位置后,增加,插入,删除,修改的时间复杂度都为O(1), 查找的时间复杂度为O(n)

    优点:增加,删除

    缺点:查找复杂

    #pragma once
    
    template <class T>
    class node
    {
    public:
    	node();
    	~node();
    public:
    	T data;
    	node* pnext;
    };
    #pragma once
    #include "node.h"
    template<class T>
    class list
    {
    public:
    	list();
    	~list();
    	void add(T t);
    	void show();
    	node<T>* find(T t);
    	void change(node<T> *pos,T newt);//修改
    	void insert(T oldt,T newt);
    	bool deletel(T t);
    	void deletesame();//删除相同元素
    	bool deleteall();
    	bool clear();
    	void rev();
    	void sort();
    	int getnum();
    	void merge(list<T> &ll);
    
    	 
    
    
    public:
    	node<T> *phead;
    };
    #include "node.h"
    #include<iostream>
    using namespace std;
    template<class T>
    node<T>::node()
    {
    }
    template<class T>
    node<T>::~node()
    {
    }
    #include "list.h"
    #include "node.h"
    #include "node.cpp"
    #include<iostream>
    using namespace std;
    template<class T>
    list<T>::list()
    {
    	this->phead = nullptr;
    	cout << "list creat" << endl;
    }
    
    template<class T>
    list<T>::~list()
    {
    	cout << "list ruin" << endl;
    }
    //增加结点
    template<class T>
    void list<T>::add(T t)
    {
    	node<T> *p = new node<T>;//分配结点
    	p->data = t;
    	p->pnext = nullptr;
    	if (phead == nullptr)
    	{
        	this->phead = p;
    	}
    	else
    	{
    		node<T> *pt=phead;
    		while(pt->pnext!=nullptr)
    		{
    			pt= pt->pnext;
    		}
    		pt->pnext= p;
    	}
    
    }
    //打印结点
    template<class T>
    void list<T>::show()
    {
    	node<T> *ptemp = phead;
    	if (phead == nullptr)
    	{
    		cout << "null"<<endl;
    		return;
    	}
    	while (ptemp!= nullptr)
    	{
    		cout << ptemp->data << "->";
    
    		ptemp = ptemp->pnext;
    	}
    	cout << endl;
    }
    //查找结点
    template<class T>
    node<T>* list<T>::find(T t)
    {
    	node<T> *p = phead;
    	while (p != nullptr)
    	{
    		if (p->data == t)
    		{
    			return p;
    		}
    		p = p->pnext;
    	}
    	return nullptr;
    
    }
    //改变结点的值
    template<class T>
    void list<T>::change(node<T> *pos, T newt)
    {
    	if (pos == nullptr)
    	{
    		return;
    	}
    	pos->data = newt;
    }
    //结点的插入运算,在指定结点前面插入结点,
    template<class T>
    void list<T>::insert(T oldt, T newt)
    {
    	node<T> *p = this->find(oldt);//查找指定结点的位置
    	if (p != nullptr)
    	{
    		node<T> *p1, *p2;
    		p1 = phead;
    		p2 = p1->pnext;
    		while (p2!=p)
    		{
    			p1= p2;
    			p2 = p1->pnext;
    		}
    		//插入新的节点
    		node<T> *pnew = new node<T>;
    		pnew->data = newt;
    		p1->pnext = pnew;
    		pnew->pnext = p2;
    	}
    
    
    }
    //删除结点
    template<class T>
    bool list<T>::deletel(T t)
    {
    	cout << "delete "<< t<<endl;
    	node<T> *p = this->find(t);
    	//判断所删除的数据是否存在,链表是否为空
    	if (phead == nullptr || p== nullptr)
    	{
    		return false;
    	}
    	else
    	{
    		if (p == phead)//判断所删除的结点是否为头结点
    		{
    			phead = p->pnext;
    			delete p;
    			return true;
    		}
    		//找到所删除的结点以及指向它的结点,令指向他的结点指向该结点的下一个结点,并删除该结点
    		node<T> *p1=phead,*p2=p1->pnext;
    		while(p2!=p)
    		{
    			p1 = p2;
    			p2 = p1->pnext;
    		}
    		p1->pnext = p2->pnext;
    		delete p2;
    		return true;
    	}
    	return false;
    }
    //删除相同结点
    template<class T>
    void list<T>::deletesame()//删除相同元素
    {
    	cout << "deletesame" << endl;
    	//将链表的值从头结点开始依次与后面结点的值比较,用指针pf记录被比较结点的前一个结点,如果比较值相等则删除后面的结点,让前一个结点指向被删除结点的后一个结点。
    		for (node<T> *pt1 = phead;pt1 != nullptr;pt1 = pt1->pnext)
    		{
    			node<T> *pf = pt1;//记录前一个结点
    			for (node<T> *pt2 = pf->pnext;pt2 != nullptr;pt2 = pf->pnext)
    			{
    
    				if (pt1->data==pt2->data)
    				{
    					//删除相等结点,让前一个结点指向被删除结点的后一个结点
    					pf->pnext = pt2->pnext;
    					delete pt2;
    				}
    				else
    				{
    					pf = pt2;//如果值不相等则向后移动
    				}
    			}
    		}
    		/*
    		node<T> *p1,*p2;
    		p1=phead->pnext;
    		p2=phead;
    		while(p1!=nullptr)
    		{
    		  if(p1->data==p2->data)
    		  {
    		    p2->pnext=p1->pnext;
    			delete p1;
    			p1=p2->pnext;
    		  }
    		  else
    		  {
    		    p2=p1;
    			p1=p1->pnext;
    		  }
    		}
    		
    		
    		
    		*/
    }
    //删除所有结点
    template<class T>
    bool list<T>::deleteall()
    {
    	cout << "deleteall" << endl;
    	node<T> *ptemp=nullptr;
    	while (phead->pnext!=nullptr)
    	{
    		ptemp = phead->pnext;
    		delete phead;
    		phead = ptemp;
    		this->show();
    	}
    	delete phead;
    	phead=nullptr;
    	return true;
    }
    //清空链表
    template<class T>
    bool list<T>::clear()
    {
    	node<T> *p1, *p2;
    	p1 = phead->pnext;
    	while (p1!=nullptr)
    	{
    		p2 = p1->pnext;
    		delete p1;
    		p1=p2
    	}
    	delete phead;
    	phead = nullptr;
    	return true;
    }
    //链表反转
    /*
         a  ->  b  ->  c  ->  d  ->  e    
    	 p1 <-  p2     p3
    	        p1 <-  p2     p3
    			       p1 <-  p2     p3
    				          p1 <-  p2     p3
    						         p1     p2     p3
    nullptr<-phead				   phead  nullptr
    */
    template<class T>
    void list<T>::rev()
    {
    	cout << "rev " << endl;
    	if (phead == nullptr || phead->pnext == nullptr)
    	{
    		return;
    	}
    	else
    	{
    		node<T> *p1, *p2,*p3;
    		p1 = phead;
    		p2 = p1->pnext;
    		while (p2!=nullptr)
    		{
    			p3 = p2->pnext;
    			p2->pnext = p1;
    
    			p1 = p2;
    			p2 = p3;
    		}
    		phead->pnext = nullptr;
    		phead= p1;
    
    	}
    }
    //对链表进行排序
    template<class T>
    void list<T>::sort()
    {
    	cout << "sort" << endl;
    	if (phead == nullptr || phead->pnext == nullptr)
    	{
    		return;
    	}
    	else
    	{
    		for (node<T> *pt1 = phead;pt1 != nullptr;pt1 = pt1->pnext)
    		{
    			
    			for (node<T> *pt2 = pt1->pnext;pt2 != nullptr;pt2 = pt2->pnext)
    			{
    				if (pt1->data > pt2->data)
    				{
    					pt1->data = pt1->data + pt2->data;
    					pt2->data= pt1->data - pt2->data;
    					pt1->data = pt1->data - pt2->data;
    					continue;
    				}
    			}
    		}
    	}
    }
    //获取链表结点个数
    template<class T>
    int list<T>::getnum()
    {
    	int num = 0;
    	node<T> *p = phead;
    	while (p != nullptr)
    	{
    		num++;
    		p = p->pnext;
    	}
    	cout << "count=" << num<<endl;
    	return num;
    }
    //链表的连接
    template<class T>
    void list<T>::merge(list<T> &ll)
    {
    	cout << "merge连接" << endl;
    	node<T> *p=phead;
    	while (p->pnext!=nullptr)//找到最后一个结点
    	{
    		p = p->pnext;
    	}
    	p->pnext = ll.phead;
    	
    }
    #include<iostream>
    #include<string>
    #include "list.h"
    #include "list.cpp"//模板类必须将实体包含,或者生成库
    using namespace std;
    //链表的实现
    void main1()
    {
    	list<int> *l1=new list<int>;
    	l1->add(22222);
    	l1->add(1);
    	l1->add(11);
    	l1->add(11);
    	l1->add(111);
    	l1->add(11);
    	l1->add(1111);
    	l1->add(11111);
    	l1->show();//打印链表数据
    
    	list<int> l2;
    	l2.add(2);
    	l2.add(3);
    	l2.add(66666);
    	l1->merge(l2);
    	l1->show();
    
    	l1->rev();
    	l1->show();
    
    	l1->deletesame();
    	l1->show();//打印链表数据
    	
    	l1->sort();
    	l1->show();//打印链表数据
    
    	l1->getnum();
    
    	l1->change(l1->find(11), 12);//替换结点数据
    	
    	l1->deletel(1);//删除
    
    	l1->show();//打印链表数据
    
    	l1->deleteall();
    
    	l1->show();
    
    	delete l1;
    	cin.get();
    }
    //十字链表
    //链表存储的数据链表
    void main()
    {
    	list<int> *l1 = new list<int>;
    	l1->add(22222);
    	l1->add(1);
    	l1->add(11);
    	l1->add(11);
    	l1->add(111);
    	//l1->show();//打印链表数据
    
    	list<int> *l2=new list<int>;
    	l2->add(2);
    	l2->add(3);
    	l2->add(66666);
    
    	list<list<int>*> *l3 = new list<list<int>*>;
    	l3->add(l1);
    	l3->add(l2);
    
    	l3->phead->data->show();
    	l3->phead->pnext->data->show();
    
    	cin.get();
    
    }
    
    

    4.哈希存储

    容易查找,不易于插入和删除 O(1)

    #pragma once
    
    template<class T>
    class hashnode
    {
    public:
    	int key;//代表索引
    	T data;//数据
    	//int count;//查找次数
    };
    /*
    索引 
    数据
    */
    #pragma once
    #include "hashnode.h"
    #include<string>
    using namespace std;
    template<class T>
    class mhash
    {
    public:
    	hashnode<T> *p;///哈希表
    	int n;//长度
    public:
    	mhash();
    	~mhash();
    	int myhash(int data);
    	void init(T *pt,int nt);
    	bool isin(int key,T t);
    	hashnode<T> * find(int key);
    	
    };
    
    #include "mhash.h"
    #include<string>
    using namespace std;
    
    template<class T>
    mhash<T>::mhash()
    {
    	this->n = 10;
    	this->p = new hashnode<T>[this->n];
    }
    
    template<class T>
    mhash<T>::~mhash()
    {
    	delete[]p;
    }
    //获得哈希表索引值
    template<class T>
    int mhash<T>::myhash(int data)
    {
    	return data % n;
    }
    //哈希表简单初始化
    template<class T>
    void mhash<T>::init(T *pt,int nt)
    {
    	for (int i = 0;i <10;i++)
    	{
    		p[i].key = pt[i]%n;
    		p[i].data = pt[i];
    		//p[i].count = 0;
    	}
    }
    //判断数据是否存在
    template<class T>
    bool mhash<T>::isin(int key,T t)
    {
    	if (p[key].data ==t)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    //查找
    template<class T>
    hashnode<T> * mhash<T>::find(int data)
    {
    	int res = myhash(data);
    	return p +res;
    }
    #include<iostream>
    #include "mhash.h"
    #include "mhash.cpp"
    #include "hashnode.h"
    
    using namespace std;
    //哈希表简单原理
    void main()
    {
    	mhash<int> myh;
    
    	int a[10] = {10,11,22,33,44,55,66,77,88,99};
    
    	myh.init(a,10);
    	cout << myh.isin(4,44) << endl;
    	hashnode<int> *p = myh.find(99);
    	cout << p->key << endl;
    	cout << p->data<< endl;
    
    	cin.get();
    }



    展开全文
  • 哈希的优缺点哈希的核心思想? 线性表和树数据的存储位置和数据的具体数值之间不存在任何关系。因此,在面对查找问题时,这些数据结构必须采取逐一比较的方法去实现。而哈希表的设计采用了函数映射的思想,将...

    目录

    哈希的核心思想?

    哈希表函数有哪些?

    哈希冲突怎么解决?

    开放定址法

    链地址法

    再哈希法 

    建立公共溢出

    哈希的优缺点?


    哈希的核心思想?

    线性表和树数据的存储位置和数据的具体数值之间不存在任何关系。因此,在面对查找问题时,这些数据结构必须采取逐一比较的方法去实现。而哈希表的设计采用了函数映射的思想,将记录的存储位置与记录的关键字关联起来。这样的设计方式,能够快速定位到想要查找的记录,而且不需要与表中存在的记录的关键字比较后再来进行查找。

    如果有一种方法,可以实现“地址 = f (关键字)”的映射关系,那么就可以快速完成基于数据的数值的查找了。这就是哈希表的核心思想。 f为hash函数。

    从本质上来看,哈希冲突只能尽可能减少,不能完全避免。这是因为,输入数据的关键字是个开放集合。只要输入的数据量够多、分布够广,就完全有可能发生冲突的情况。因此,哈希表需要设计合理的哈希函数,并且对冲突有一套处理机制。

    哈希表函数有哪些?

    第一,直接定制法:哈希函数为关键字到地址的线性函数。如,H (key) = a*key + b。 这里,a 和 b 是设置好的常数。

    第二,数字分析法:假设关键字集合中的每个关键字 key 都是由 s 位数字组成(k1,k2,…,Ks),并从中提取分布均匀的若干位组成哈希地址。

    第三,平方取中法:如果关键字的每一位都有某些数字重复出现,并且频率很高,我们就可以先求关键字的平方值,通过平方扩大差异,然后取中间几位作为最终存储地址。

    第四,折叠法:如果关键字的位数很多,可以将关键字分割为几个等长的部分,取它们的叠加和的值(舍去进位)作为哈希地址。

    第五,除留余数法:预先设置一个数 p,然后对关键字进行取余运算。即地址为 key mod p。

    哈希冲突怎么解决?

    开放定址法

    即当一个关键字和另一个关键字发生冲突时,使用某种探测技术在哈希表中形成一个探测序列,然后沿着这个探测序列依次查找下去。当碰到一个空的单元时,则插入其中。

    常用的探测方法是线性探测法。

    比如有一组关键字 {12,13,25,23},采用的哈希函数为 key mod 11。当插入 12,13,25 时可以直接插入,地址分别为 1、2、3。而当插入 23 时,哈希地址为 23 mod 11 = 1。然而,地址 1 已经被占用,因此沿着地址 1 依次往下探测,直到探测到地址 4,发现为空,则将 23 插入其中。如下图所示:

    链地址法

    将哈希地址相同的记录存储在一张线性链表中。

    例如,有一组关键字 {12,13,25,23,38,84,6,91,34},采用的哈希函数为 key mod 11。如下图所示:

    再哈希法 

    当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。

    建立公共溢出

     

    哈希的优缺点?

    哈希表相对于其他数据结构有很多的优势。它可以提供非常快速的插入-删除-查找操作,无论多少数据,插入和删除值需要接近常量的时间。在查找方面,哈希表的速度比树还要快,基本可以瞬间查找到想要的元素。

    哈希表也有一些不足。哈希表中的数据是没有顺序概念的,所以不能以一种固定的方式(比如从小到大)来遍历其中的元素。在数据处理顺序敏感的问题时,选择哈希表并不是个好的处理方法。同时,哈希表中的 key 是不允许重复的,在重复性非常高的数据中,哈希表也不是个好的选择。

    哈希表在我们平时的数据处理操作中有着很多独特的优点,不论哈希表中有多少数据,查找、插入、删除只需要接近常量的时间,即 O(1)的时间级。

    实际上,这只需要几条机器指令。哈希表运算得非常快,在计算机程序中,如果需要在一秒钟内查找上千条记录通常使用哈希表(例如拼写检查器),哈希表的速度明显比树快,树的操作通常需要 O(n) 的时间级。哈希表不仅速度快,编程实现也相对容易。如果不需要有序遍历数据,并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

    展开全文
  • 提高Redis使用性能秘诀KEY尽量少原则,能放在1个KEY就放入1个KEY,KEY开销很大尽量减少与Redis发生交互次数,能批量就批量,能事务、管道就事务、管道从业务架构分析确定使用哪种数据类型,从全局出发,...

    一.提高Redis使用性能秘诀

    KEY尽量少的原则,能放在1个KEY的就放入1个KEY,KEY开销很大
    尽量减少与Redis发生的交互次数,能批量的就批量,能事务、管道的就事务、管道
    从业务架构分析确定使用哪种数据类型,从全局出发,如果类型选错了再改变就很不容易
    使用每一个Redis命令注意是O(1),还是O(N),切记滥用,认准每个命令的特性再使用也不迟
    使用PHP Redis的C语言扩展,性能远远高于PHP脚本编写的文件
    时刻清醒你往Redis里存储了什么,频繁交互、相对静态的小数据存储至Redis是理想的,300万用户所有不常用的信息都无脑塞进去不但浪费内存(有可能服务器128G内存不够用必须要老大花钱买内存),还影响Redis性能,增大管理成

    二.Redis各大类型特性注意事项一览表

    字符串(Strings) 哈希(Hashes) 列表(Lists) 集合(Sets) 有序集合(Sorted sets)
    512MB/Value 4294967295/Hash 4294967295/List 4294967295/Set 4294967295/Stored
    Key【唯一】
    Value【重复】
    Key【唯一】
    Hash key【唯一】
    Value【重复】
    Key【唯一】
    Index【唯一】
    Value【重复】
    Key【唯一】
    Value【唯一】
    Key【唯一】
    Value【唯一】
    Score【重复】
    Value【唯一】
     无序  key无序
    Hash key按先后进入顺序有序
     key无序
    Index按先后进入顺序有序
     key无序
    Value无序
     key无序
    按Score值排序有序
     简单存储,持久化的memcached,计数器、灵活操作字符串  Json KV结构,单表存储,缓存,对象存储  队列系统,时间轴系统设计,显示极端数据,先进先出,后进后出  以key为班级,Value老师,可以求出不同班级中老师的交集、并集  以key为班级,Score为分数,Value为学生的考试成绩排行榜报表等分组统计功能
     最原始的缓存系统,性能高,任意1个的性能O(1)  类似关系型数据库操作,性能高,任意1个的性能O(1)  操作首尾数据,统计长度很快O(1),中间数据操作性能不高O(N)  类似数组下标访问元素,添加,删除,查找任意1个的复杂度都是O(1)  Sets升级版,有分组+统计等功能,添加,删除,查找任意1个的复杂度都是O(log(1))
     简单的数据交互  简单的数据交互  简单的数据交互  支持服务端数据运算  支持服务端数据运算

    转载于:https://www.cnblogs.com/zouzhe0/p/7426510.html

    展开全文
  • 常见数据结构优缺点比较

    千次阅读 2017-12-11 11:17:08
    数据结构是对在计算机内存中的数据的一种安排,数据结构包括数组,链表,栈,二叉树,哈希表等等,数据结构和技术与如何处理现实世界...今天不展开常见数据结构的原理,仅仅比较他们的优缺点。 数据结构 优点 缺点
  • memcacha与redis的优缺点

    2020-08-05 01:43:32
    Redis 和 Memcached 都是基于内存的数据存储系统。 Memcached是高性能分布式内存缓存服务,其本质上就是一个内存key-value...Memcached仅支持简单的key-value结构的数据记录 Redis支持list、set、sorted set、has
  • 索引根据实现数据结构可以分为B-Tree索引,哈希索引,空间数据索引(R-Tree),全文索引等 B-Tree索引 B-Tree索引是使用最频繁一种索引,也是我们平时常常说一种索引。它是使用B-Tree数据结构存储数据。 ...
  • 链表及链表与数组区别优缺点

    千次阅读 2020-04-19 11:45:28
    链表的概念   链表是一种物理存储结构上非连续,非顺序的...实际中更多是作为其他数据结构的子结构,比如说哈希桶等等。   带头双向循环链表:结构最复杂,一般单独存储数据。实际中经常使用的链表数据结构...
  • 文章目录1. 哈希概念2. 哈希冲突3....顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应关系,因此在查找一个元素时,必须要经过关键码多次比较。顺序查找时间复杂度为 O(N)O(N)O(N),...
  • 哈希表是一种以键-值(key-value)形式存储数据的结构,我们只需要输入查找键key,就可以得到对应值value。哈希的思路是,把值放在数组里,用一个哈希函数把key换成一个确定位置,然后把value
  • 文章目录顺序存储与哈希索引SSTable和LSM treeB-Tree存储结构的比对小结 本篇主要讨论的是不同存储结构(主要是LSM-tree和B-tree),它们应对的不同场景,所采用的底层存储结构,以及对应用以提升效率的索引。 所谓...
  • Redis是一款开源、高性能键-值存储(key-value store)。它常被称作是一款数据结构服务器(data structure server)。 reids数据类型: 字符串(strings)类型 列表(lists) 集合(sets) 有序集合(sorted ...
  • MySQL: Hash索引优缺点

    千次阅读 2019-06-24 11:46:24
    因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找速度非常快 缺点: 1、不能避免读取行 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中值来避免读取行。...
  • Redis优缺点

    千次阅读 2015-03-27 23:18:37
    一:redis简介:1:键-值存储 通常被称作是一款数据结构服务器2:支持数据类型:字符串、哈希、列表、集合、有序集合等 。对这些数据类型,可以执行原子操作。3:为了获得优异性能,redis采用内存中数据集方式...
  • 研究现有索引算法,并找出其优缺点。 实施现有索引编制技术,并研究和比较何时使用特定索引编制方法。 第二阶段: 优化索引编制方法。 第三阶段: 计算时空复杂度因子并找出优化索引方法返回结果准确...
  • Hash应用Hash复杂度散列表查找步骤散列函数(哈希函数)——散列地址哈希优缺点优点:缺点:散列三种方法1、除法散列法2、平方散列法3、斐波那契(Fibonacci)散列法散列冲突解决方案:扩展代码应用 ...
  • 同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为。 布隆过滤器即可以解决存储空间的问题, 又可以解决时间复杂度的问题. 布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成...
  • 在讨论哈希表之前,我们先回顾一下数组和链表来实现对数据的存储的优缺点: **数组:**占用空间连续。 寻址容易,查询速度快。但是,增加和删除效率非常低。 **链表:**占用空间不连续。 寻址困...
  • Redis支持丰富数据结构类型,字符串,散列(哈希),集合,有序集合,还支持订阅发布,地理位置等等。实际运用中可以redis,memcache结合,memcache可作为session存储的方式,session都是KV类型键值对。Redis 提供...
  • 哈希表、散列表

    2020-11-18 23:53:24
    在介绍哈希表的时候,先来比较一下数组和链表的优缺点: 数组:寻址容易,但插入和删除元素比较麻烦; 链表:插入和删除元素容易,但寻址比较麻烦。 那么有没有一种数据结构是既能结合这两种的优点同时也能避免这...
  • 优点是对数据元素的存储没有要求,顺序存储或链式存储皆可。 2,查找算法平均长度计算 对于无序表: 查找成功平均查找长度为(n+1)/2 查找失败平均查找长度为n+1 对于有序表: 查找成功平均查找长度为(n+1...
  • 目录 【树结构】 【二叉树基础】 ...平衡了数组和链表的优缺点。但其存在哈希关键值的冲突(两个以上数据经过哈希运算得到了同一个哈希值),此时要采取方案,如:数组+链表 的形式处理冲突。且哈希表数组长度.
  • 本文将详细分析各种存储结构的优缺点,以此来说明为什么MySQL采用B+树 众所周知 常见的存储结构有 顺序表 哈希表 搜索二叉树 红黑树 B树 B+树 1 顺序表 顺序表 分为数组和链表 数组 查找时间复杂度O(1) 优点:...
  • 对于数据结构的学习不单单需要知道各种数据结构的优缺点和应用场景,对于数据结构的源码和算法也是蕴含着很多可以学习的东西。 1、Map(映射类) Map是按照Key-Value进行存储的数据结构,主要实现有HashMap,...
  • 哈希的优缺点:  首先我们要从哈希说起,对于数据的存储,查询,插入,哈希表肯定是最好的选择,他的时间复杂度接近于O(1)。但是为了减少哈希冲突,也就是为了时间复杂度尽量小,就要空间利用率相对低。这就是用...
  • 数据结构知识点汇总

    2019-04-14 09:19:23
    数据结构的基本功能 八种常见数据机构 数组Array 栈Stack 队列Queue 链表LinkedList 树Tree 哈希表Hash 堆Heap 图Graph 数据结构优缺点 数据结构 优点 缺点 数组 插入快 查找慢,删除慢...
  • Java 数据结构和算法 概述

    千次阅读 2017-04-22 18:37:33
    数据结构 数据结构是对在计算机内存中(有时在磁盘中)的数据的一种安排,数据结构包括...数据结构的概述还可以从数据结构的优缺点来看待数据结构; 数据结构 优点 缺点 数组 插入快,如果知道下标可以快速的存

空空如也

空空如也

1 2 3 4
收藏数 78
精华内容 31
热门标签
关键字:

哈希存储结构的优缺点