【数据结构】哈希表与哈希桶

这篇具有很好参考价值的文章主要介绍了【数据结构】哈希表与哈希桶。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

1.概念

2.哈希冲突

3.解决哈希冲突

3.1闭散列

3.2开散列(哈希桶)

4.模拟实现

4.1闭散列的模拟实现

4.1.1哈希表结构设计

 4.1.2插入

4.1.3删除 

4.2哈希桶的模拟实现

4.2.1哈希桶结构设计

4.2.2插入

4.2.3查找 

4.2.4删除


前言

本篇文章我们共同学习哈希结构,哈希结构追求更极致的搜索效率。

之前学习的结构中搜索的效率取决于搜索过程中元素的比较次数,因此顺序结构中查找的时间复杂度为O(N),平衡树中查找的时间复杂度为树的高度O(logN)。

那我们能不能构建一种数据结构,让搜索效率达到O(1)呢。

如果构造一种存储结构,该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时就能通过该函数很快找到该元素进而达到O(1)的查找效率。

接下来就让我们共同学习哈希结构。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。 

=========================================================================文章来源地址https://www.toymoban.com/news/detail-842169.html

GITEE相关代码:🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================


1.概念

哈希结构的本质就是利用了『 映射关系』。

向该结构当中插入和搜索元素的过程如下:

  • 插入元素: 根据待插入元素的关键码,用此函数计算出该元素的存储位置,并将元素存放到此位置。
  • 搜索元素: 对元素的关键码进行同样的计算,把求得的函数值当作元素的存储位置,在结构中按此位置取元素进行比较,若关键码相等,则搜索成功。

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

例如,集合{1, 7, 6, 4, 5, 9}

哈希函数设置为:hash( key ) = key % capacity ,其中capacity为存储元素底层空间的总大小。

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

用该方法进行存储,在搜索时就只需通过哈希函数判断对应位置是否存放的是待查找元素,而不必进行多次关键码的比较,因此搜索的速度比较快。

2.哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址,这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。

例如,在上述例子中,再将元素11插入当前的哈希表就会产生哈希冲突。 因为元素11通过该哈希函数得到的哈希地址与元素1相同,都是下标为1的位置。

hash( 11 ) = 11 % 10 = 1。

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

哈希函数设计原则:

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

常见哈希函数

一、直接定址法(常用)

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B

优点:简单、均匀

缺点:需要事先知道关键字的分布情况

使用场景:适合查找比较小且连续的情况

面试题:字符串中第一个只出现一次字符

二、除留余数法(常用)

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

三、平方取中法(了解)

假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;

再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址

平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况

四、折叠法(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况

五、随机数法(了解)

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

六、数学分析法(了解)

设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如:

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是相同的,那么我们可以选择后面的四位作为哈希地址。

如果这样的抽取方式还容易出现冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环位移(如1234改成2341)、前两数与后两数叠加(如1234改成12+34=46)等操作。

数字分析法通常适合处理关键字位数比较大的情况,或事先知道关键字的分布且关键字的若干位分布较均匀的情况。

注意:无法避免哈希冲突,哈希函数设计的越精妙,产生哈希冲突的可能性越低。


3.解决哈希冲突

3.1闭散列

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

1. 线性探测

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

如图,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。

线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

插入

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

删除

  • 采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。
  • 因此线性探测采用标记的伪删除法来删除一个元素。
    // 哈希表每个空间给个标记
    // EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
    enum State{EMPTY, EXIST, DELETE};

我们将数据插入到有限的空间,那么空间中的元素越多,插入元素时产生冲突的概率也就越大,冲突多次后插入哈希表的元素,在查找时的效率必然也会降低。介于此,哈希表当中引入了负载因子(载荷因子)。

负载因子 = 表中有效数据个数 / 空间的大小

虽然负载因子越小,冲突概率就会变低,查找效率会变高,但是负载因子越小,也就意味着空间的利用率越低,此时大量的空间实际上都被浪费了。对于闭散列(开放定址法)来说,负载因子是特别重要的因素,一般控制在0.7~0.8以下,超过0.8会导致在查表时CPU缓存不命中(cache missing)按照指数曲线上升。

因此,一些采用开放定址法的hash库,如JAVA的系统库限制了负载因子为0.75,当超过该值时,会对哈希表进行增容。

  • 优点:实现非常简单。
  • 缺点:一旦发生冲突,所有的冲突连在一起,容易产生数据『 堆积』,即不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要多次比较(踩踏效应),导致搜索效率降低。

2.二次探测 

线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:

Hi=(H0 + i^2) % m       (i=1,2,3,...)

  • H0:通过哈希函数对元素的关键码进行计算得到的位置。
  • Hi:冲突元素通过二次探测后得到的存放位置。
  • m:表的大小。

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

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

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

采用二次探测为产生哈希冲突的数据寻找下一个位置,相比线性探测而言,采用二次探测的哈希表中元素的分布会相对稀疏一些,不容易导致数据堆积,但也因此,闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。


3.2开散列(哈希桶)

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

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

这样看来,对于开散列来说,不同哈希值的元素之间不会互相干扰。 

并且哈希桶的负载因子可以更大,空间利用率高。

极端情况:所有元素的哈希值均相同,最终都放到了同一个哈希桶中,此时该哈希表增删查改的效率就退化成了O(N),对于这种情况,有这样一种解决方案:『 桶中种树』。

【数据结构】哈希表与哈希桶,数据结构,哈希算法,数据结构,散列表

为了避免出现这种极端情况,当桶当中的元素个数超过一定长度,有些地方就会选择将该桶中的单链表结构换成红黑树结构。

但有些地方也会选择不做此处理,因为随着哈希表中数据的增多,该哈希表的负载因子也会逐渐增大,最终会触发哈希表的增容条件,此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表,此时同一个桶当中冲突的数据个数也会减少,因此不做处理问题也不大。


4.模拟实现

4.1闭散列的模拟实现

4.1.1哈希表结构设计

前面在讲解线性探测的部分时,提到过我们不能直接删除哈希表中的元素,而是采用伪标记的删除法,这里我们展开讲解一下:

闭散列又称开放定址法,当两个元素的哈希值冲突时我们采用线性探测的方式来解决冲突。

那么查找某个元素时,如何判断可以找到还是找不到?

根据线性探测的思想,明显是当遇到空时,就证明找不到了。

可当我们要删除某个元素时,如果直接删除,他所在的位置变成空值,那将来在查找『 因为它而产生的哈希冲突后移的元素』时,可能会受到该位置为空的影响,提前结束查找操作。

所以这里不能简单的直接删除,并且也不能用某个具体的值代表空值,这样会导致哈希表存储不了这个值,所以最有效的方式就是给每个元素设置一个状态。

  1. EMPTY(无数据的空位置)。
  2. EXIST(已存储数据)。
  3. DELETE(原本有数据,但现在被删除了)。
//枚举:标识每个位置的状态
enum State
{
	EMPTY,
	EXIST,
	DELETE
};

//哈希表每个位置存储的结构
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY; //状态
};

 并且为了在插入元素时好计算当前哈希表的负载因子,我们还应该时刻存储整个哈希表中的有效元素个数,当负载因子过大时就应该进行哈希表的增容。

//哈希表
template<class K, class V>
class HashTable
{
public:
	//...
private:
	vector<HashData<K, V>> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

 4.1.2插入

向哈希表中插入数据的步骤如下:

  1. 查看哈希表中是否存在该键值的键值对,若已存在则插入失败。
  2. 判断是否需要调整哈希表的大小,若哈希表的大小为0,或负载因子过大都需要对哈希表的大小进行调整。
  3. 将键值对插入哈希表。
  4. 哈希表中的有效元素个数加一。

其中,哈希表的调整方式如下:

  1. 若哈希表的大小为0,则将哈希表的初始大小设置为10(在构造时完成)。
  2. 若哈希表的负载因子大于0.7,则先创建一个新的哈希表,该哈希表的大小为原哈希表的两倍,之后遍历原哈希表,将原哈希表中的数据插入到新哈希表,最后将原哈希表与新哈希表交换即可。

注意: 在将原哈希表的数据插入到新哈希表的过程中,需要重新计算哈希值,不能只是简单的将原哈希表中的数据对应的挪到新哈希表中,而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置,然后再进行插入。

将键值对插入哈希表的具体步骤如下:

  1. 通过哈希函数计算出对应的哈希地址。
  2. 若产生哈希冲突,则从哈希地址处开始,采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。
  3. 将键值对插入到该位置,并将该位置的状态设置为EXIST。

注意: 产生哈希冲突向后进行探测时,一定会找到一个合适位置进行插入,因为哈希表的负载因子是控制在0.7以下的,也就是说哈希表永远都不会被装满。

//插入函数
bool Insert(const pair<K, V>& kv)
{
	//1、查看哈希表中是否存在该键值的键值对
	HashData<K, V>* ret = Find(kv.first);
	if (ret) //哈希表中已经存在该键值的键值对(不允许数据冗余)
	{
		return false; //插入失败
	}

	if _n * 10 / _table.size() >= 7) //负载因子大于0.7需要增容
	{
		//增容
		//a、创建一个新的哈希表,新哈希表的大小设置为原哈希表的2倍
		HashTable<K, V> newHT;
		newHT._table.resize(2 * _table.size());
		//b、将原哈希表当中的数据插入到新哈希表
		for (auto& e : _table)
		{
			if (e._state == EXIST)
			{
				newHT.Insert(e._kv);
			}
		}
		//c、vector的交换函数swap交换这两个哈希表
		_table.swap(newHT._table);
	}

	//3、将键值对插入哈希表
	//a、通过哈希函数计算哈希地址
	size_t hashi= kv.first%_table.size(); //除数不能是capacity
	//b、找到一个状态为EMPTY或DELETE的位置
	while (_table[hashi]._state == EXIST)
	{
        ++hashi;
		hashi %= _table.size(); //防止下标超出哈希表范围
	}
	//c、将数据插入该位置,并将该位置的状态设置为EXIST
	_table[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	
	//4、哈希表中的有效元素个数加一
	_n++;
	return true;
}

4.1.3删除 

删除哈希表中的元素非常简单,我们只需要进行伪标记的删除法即可,也就是将待删除元素所在位置的状态设置为DELETE。

在哈希表中删除数据的步骤如下:

  1. 查看哈希表中是否存在该键值的键值对,若不存在则删除失败。
  2. 若存在,则将该键值对所在位置的状态改为DELETE即可。
  3. 哈希表中的有效元素个数减一。

注意: 虽然删除元素时没有将该位置的数据清0,只是将该元素所在状态设为了DELETE,但是并不会造成空间的浪费,因为我们在插入数据时是可以将数据覆盖到状态为DELETE的位置的。

//删除函数
bool Erase(const K& key)
{
	//1、查看哈希表中是否存在该键值的键值对
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		//2、若存在,则将该键值对所在位置的状态改为DELETE即可
		ret->_state = DELETE;
		//3、哈希表中的有效元素个数减一
		_n--;
		return true;
	}
	return false;
}

4.2哈希桶的模拟实现

4.2.1哈希桶结构设计

在开散列的哈希表中,哈希表的每个位置存储的实际上是某个单链表的头结点,即每个哈希桶中存储的数据实际上是一个结点类型,该结点类型除了存储所给数据之外,还需要存储一个结点指针用于指向下一个结点。

//每个哈希桶中存储数据的结构
template<class K, class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	//构造函数
	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};

注意:哈希桶的结构设计中不需要状态字,因为不同哈希值的元素不会互相影响。 

哈希表的开散列实现方式,在插入数据时也需要根据负载因子判断是否需要增容,所以我们也应该时刻存储整个哈希表中的有效元素个数,当负载因子过大时就应该进行哈希表的增容。 

//哈希表
template<class K, class V>
class HashTable
{
public:
	//...
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

4.2.2插入

向哈希表中插入数据的步骤如下:

  1. 查看哈希表中是否存在该键值的键值对,若已存在则插入失败。
  2. 判断是否需要调整哈希表的大小,若哈希表的大小为0,或负载因子过大都需要对哈希表的大小进行调整。
  3. 将键值对插入哈希表。
  4. 哈希表中的有效元素个数加一。

其中,哈希表的调整方式如下:

  1. 若哈希表的大小为0,则将哈希表的初始大小设置为10(构造时完成)。
  2. 若哈希表的负载因子已经等于1了,则先创建一个新的哈希表,该哈希表的大小为原哈希表的两倍,之后遍历原哈希表,将原哈希表中的数据插入到新哈希表,最后将原哈希表与新哈希表交换即可。

注意:我们只需要遍历原哈希表的每个哈希桶,通过哈希函数将每个旧哈希桶中的结点重新挂到新哈希表即可,不用进行结点的创建与释放。

//插入函数
bool Insert(const pair<K, V>& kv)
{
	//1、查看哈希表中是否存在该键值的键值对
	if (Find(kv.first)) //哈希表中已经存在该键值的键值对(不允许数据冗余)
	{
		return false; //插入失败
	}

	//2、判断是否需要调整哈希表的大小
	if (_n == _table.size()) //负载因子超过1
	{
		//增容
		//a、创建一个新的哈希表,新哈希表的大小设置为原哈希表的2倍
		vector<Node*> newTables(_tables.size()*2, nullptr);
		
		//b、将原哈希表当中的结点插入到新哈希表
		for (size_t i = 0; i < _table.size(); i++)
		{
            //取出旧表中的节点,重新计算挂到新表桶中
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = cur->_kv.first % newTables.size(); 

				//将该结点头插到新哈希表中编号为index的哈希桶中
				cur->_next = newTables[hashi ];
				newTables[hashi] = cur;

				cur = next;
			}
			_table[i] = nullptr; //该桶取完后将该桶置空

		}
		//c、交换这两个哈希表
		_table.swap(newTables);
	}

	//3、将键值对插入哈希表
	size_t hashi= kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index(除数不能是capacity)
	Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点

	//将该结点头插到新哈希表中编号为index的哈希桶中
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;

	//4、哈希表中的有效元素个数加一
	_n++;
	return true;
}

4.2.3查找 

在哈希表中查找数据的步骤如下:

  1. 先判断哈希表的大小是否为0,若为0则查找失败。
  2. 通过哈希函数计算出对应的哈希地址。
  3. 通过哈希地址找到对应的哈希桶中的单链表,遍历单链表进行查找即可。
//查找函数
HashNode<K, V>* Find(const K& key)
{
	if (_table.size() == 0) //哈希表大小为0,查找失败
	{
		return nullptr;
	}

	size_t hashi = key % _table.size();

	//遍历编号为index的哈希桶
	HashNode<K, V>* cur = _table[hashi];
	while (cur) //直到将该桶遍历完为止
	{
		if (cur->_kv.first == key) //key值匹配,则查找成功
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr; //直到该桶全部遍历完毕还没有找到目标元素,查找失败
}

4.2.4删除

在哈希表中删除数据的步骤如下:

  1. 通过哈希函数计算出对应的哈希桶编号。
  2. 遍历对应的哈希桶,寻找待删除结点。
  3. 若找到了待删除结点,则将该结点从单链表中移除并释放。
  4. 删除结点后,将哈希表中的有效元素个数减一。
//删除函数
bool Erase(const K& key)
{
	//1、通过哈希函数计算出对应的哈希桶编号hashi(除数不能是capacity)
	size_t hashi = key % _table.size();
	//2、在编号为index的哈希桶中寻找待删除结点
	Node* prev = nullptr;
	Node* cur = _table[hashi];
	while (cur) //直到将该桶遍历完为止
	{
		if (cur->_kv.first == key) //key值匹配,则查找成功
		{
			//3、若找到了待删除结点,则删除该结点
			if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
			{
				_table[hashi] = cur->_next; //将第一个结点从该哈希桶中移除
			}
			else //待删除结点不是哈希桶的第一个结点
			{
				prev->_next = cur->_next; //将该结点从哈希桶中移除
			}
			delete cur; //释放该结点
			//4、删除结点后,将哈希表中的有效元素个数减一
			_n--;
			return true; //删除成功
		}
		prev = cur;
		cur = cur->_next;
	}
	return false; //直到该桶全部遍历完毕还没有找到待删除元素,删除失败
}

🐸思考🐸

除留余数法是映射哈希值的有效方法,但是这里我们考虑的都是整型情况下,那如果是字符串呢?如果key值是字符串,字符串可没办法取余数,而我们最终是一定要实现泛型编程的,我们怎样才能构建出一个通用的映射关系呢?


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

到了这里,关于【数据结构】哈希表与哈希桶的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图——邻接表与邻接矩阵

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中, G表示一个图,V是顶点的集合,E是边的集合 。 在图中数据元素,我们则称之为顶点(Vertex)。 图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是

    2024年02月02日
    浏览(41)
  • 【数据结构 | 入门】线性表与链表 (问题引入&实现&算法优化)

    🤵‍♂️ 个人主页: @计算机魔术师 👨‍💻 作者简介:CSDN内容合伙人,全栈领域优质创作者。 本文是浙大数据结构学习笔记专栏 这里我们引入一个问题,最常见的多项式,我们如何使用编程将多项式表示出来呢? 我们可以使用数组来表示,但是会随着一个问题,如下图底

    2024年01月21日
    浏览(67)
  • 【数据结构与算法分析】反转链表与顺序表(内含源码,思路清晰)

      顺序表和链表都是数据结构中常见的线性表。它们的主要区别在于 内存管理方式不同 。   顺序表(Array)是由一系列元素按照一定顺序依次排列而成,它使用连续的内存空间存储数据。顺序表使用一个数组来存储数据,数组中的每个元素都可以通过下标来访问。顺序

    2024年02月07日
    浏览(101)
  • 【数据结构与算法】之8道顺序表与链表典型编程题心决!

                                                                                    个人主页:秋风起,再归来~                                                                                             数据结构与算

    2024年04月14日
    浏览(51)
  • Java学数据结构(4)——散列表Hash table & 散列函数 & 哈希冲突

    1.散列表,key,散列函数; 2.哈希冲突的解决; 3.string中的hashCode; 查找树ADT,它允许对元素的集合进行各种操作。本章讨论散列表(hash table)ADT,不过它只支持二叉查找树所允许的一部分操作。散列表的实现常常叫作散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和

    2024年02月10日
    浏览(52)
  • 一篇就能学懂的散列表,让哈希表数据结构大放光彩

    目录 1.散列表的基本概念 2.散列表的查找 3.散列函数的构造方法 1.直接定址法 2.除留余数法 4.散列表解决冲突的方法 1.开放定址法 2.链地址法 基本思想 :记录的存储位置与之间存在的对应关系 对应关系——hash函数 Loc(i) = H(keyi) Hash:哈希——翻译为:散列、杂凑(感

    2024年02月09日
    浏览(52)
  • 【数据结构与算法】顺序表与链表(单链表和双链表)超详解图示与源码。

                                                       大家好,今天我们来学习数据结构中的顺序表与链表!源码在最后附上 首先我们先来认识一下 顺序表 :                                       **如上图所示:很多人会以为数组就是顺序表,顺序表就是数组,这

    2024年02月21日
    浏览(55)
  • 【数据结构与算法】前缀和+哈希表算法

    关于前缀和和哈希这两个概念大家都不陌生,在之前的文章中也有过介绍:前缀和与差分算法详解 而哈希表最经典的一题莫过于 两数之和 题目链接 题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它

    2024年02月01日
    浏览(110)
  • 数据结构,查找算法(二分,分块,哈希)

    一、查找算法         1、二分查找:(前提条件: 必须有序的序列) 2、分块查找:(块间有序,块内无序)     索引表  +  源数据表     思路:     (1)先在索引表中确定在哪一块中     (2)再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(56)
  • 【数据结构】哈希表(算法比赛向)

    目录 一:介绍 一:什么是哈希表 二、哈希表的应用 二:存储结构 a.拉链法: b.开放寻址法: 三:扩展 a.字符串哈希: 例题:      一:什么是哈希表 1、哈希表也叫散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插

    2023年04月25日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包