❶ 散列查找堆积现象为什么不影响存储效率
一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。
哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址 即key1≠key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。
注：这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数) 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。 现实中哈希函数是需要构造的，并且构造的好才能使用的好。
对于动态查找表而言，1) 表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key)作为关键字为key的录在表中的位置，通常称这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数)
哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。
现实中哈希函数是需要构造的，并且构造的好才能使用的好。
用途：加密，解决冲突问题。。。。
用途很广，比特精灵中就使用了哈希函数，你可 以自己看看。
具体可以学习一下数据结构和算法的书。
字符串哈希函数（着名的ELFhash算法）
int ELFhash(char *key)
{ unsigned long h=0;
while(*key)
{ h=(h<<4)+*key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}
❷ 队列和散列表跟数据的存储结构有关还是无关
队列和散列表的实现方式和存储结构有关，不同的存储结构会影响它们的实现方式和性能表现。
队列是一种先进先出（FIFO）的数据结构，主要有两种实现方式：数组和链表。用数组实现的队列叫做顺序队列，用链表实现的队列虚大叫做链式队列。对于顺序队列，队列元素是顺序存储在连续的内存空间中的，队列的头部和尾部分别指向队列的第一个元素和最后一个元素。对于链式队列，队列元素是通过指针连接起来的，队列的头部指向链表的头结点，尾部指向链表的尾结点。
散列表是一种根据关键字直接访问数据的数据结构，主要有两种实现方式：开放地址法和链表法。开放地差橘竖址法使用数组来存储数据，通过哈希函数将数据的关键字映射到数组的索引上，如果这个位置已经有数据了，就根据一定的规则在数组中寻找下一个空闲位置。链表法使用链表来存储数据，如果哈希函数将多个数据的关键字映射到了同一个索引上，那么就将它们存储在同一个链表伍察中。
因此，队列和散列表的实现方式和性能表现与数据的存储结构密切相关。选择合适的实现方式和存储结构可以提高数据结构的性能和效率。
❸ 第十九节-散列表（中）
散列函数的设计的好坏，决定了散列冲突的概率大小，也直接决定了散列表的性能。
过于复杂的散列函数，会消耗过多的计算时间，也就间接影响到散列表的性能。
这样才能避免或者最小化散列冲突。即便是出现冲突，散列到每个槽的数据也会分布得比较均匀，不会出现某个槽内的数据特别多的情况。
这些因素有关键字的长度、特点、分布、还有散列表的大小等。
通过分析传入散列函数的 key 的特征规律，设计相应的专用散列函数。比如处理使用散列函数处理手悉派机号码，考虑到手机号码前几位重复性很大，后几位比较随机，我们就可以取手机号码后几位作为散列值。
比如对字符串进行散列，可以将字符串中每个字母的 ASCII 值进行“进位”相加，然后再跟散列表的大小求余、取模，作为散列值。比如，对因为单词 nice 进行散列：
hash("nice")=(("n" - "a") * 26*26*26 + ("i" - "a")*26*26 + ("c" - "a")*26+ ("e"-"a")) / 78978
装载睁搏贺因子的定义为 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度 ，根据这个公式，可以推出，装载因子越大且散列表的长度不变，则散列表中的元素越多，空闲位置越少，散列冲突的概率会变大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
对没有频繁插入和删除的静态数据集合来说，我们很容易根据数据的特点、分布等，设计出完美的、极少冲突的散列函数。
对于动态散列表来说，数据集合频繁变动，负载因子可能随着时间不断变大。这时就要动态扩容。
动态扩容的过程，简单来说，就是申请一个新的散列表，然后把原来的数据搬运到新的散列表中，但是不是简单的搬运，而是每个元素都要根据新的散列表重新存储位置。
这个过程，运用平摊分析法，每个插入操作的时间复杂度仍是 O(1)。
扩展一下，当散列表的装载因子小于某个阈值时，我们也可以依样画葫芦，进行动态缩容。
大部分情况下，动态扩容的散列表插入一个数据都很快，但在特殊情况下，装载因子达到扩容的阈值，此时，再插入数据，就会触发漫长的银唤扩容过程，在特定的场合，这样漫长的等待过程是不可接受的。
举个直观的例子，假设原来散列表有 1GB 的数据，现在进行扩容，就需要对这 1GB 的数据进行再散列，这个扩容的时间，看起来就很耗时。
在这种情况下，“一次性”扩容的机制就不适合了。此时，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子达到扩容的阈值后，我们只申请新空间，但不立即将老的数据全部搬移到新的散列表中。
当有新的数据插入时，我们就将新数据插入新散列表中，同时从旧散列表中拿出一个数据放入到新的散列表。每次插入一个数据到散列表，我们都重复以上的过程。经过多次操作后，老的散列表中的数据就一点一点全部搬移到新的散列表中了。没有了一次性全部搬移，插入操作就不会出现一次很慢的情况了。
这期间的插入操作，可以先从新的散列表中查，查不到再去旧的散列表中查。甚至，可以在每次查询操作中也穿插一条数据搬移。
上节讲了两种主要的散列冲突的解决办法，开放寻址法和链表法。这两种冲突的解决办法在实际的软件开发中很常用。比如， Java 中的 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。
这种实现方式，散列表中的数据都存放在数组中，可以有效利用 CPU 的缓存加快查询速度。序列化过程比较简单。链表法包含指针，序列化就比较麻烦。
缺点是，删除数据比较麻烦，需要使用特殊标记。所有数据都存在一个数组中，冲突的代价很大。
总结，数据量小、装载因子小，适合开放寻址法。这也是 ThreadLocalMap 采用开放寻址法解决散列冲突的原因。
链表法的优点是内存利用率高。链表节点可以在需要的时候再创建，并不需要想开放寻址法那样实现申请好。
链表法对冲突的容忍性更高，装在因子可以大于 1，甚至再散列冲突很平均的情况下，即使装载因子达到 10，查找效率也不会大幅度衰退。更进一步，对链表法进行改造，使用红黑树或者跳表解决散列冲突，那即使是极端情况下，所有数据都存放在一个槽内，查询时间也是衰退到 O(logn) 的数量级。
缺点是，需要维持链表的指针引用，若是存放小对象，那么指针占用的内存就会对比起来挺多，而且链表法也容易造成内存碎片。
总结起来就是，基于链表法的散列冲突方法适合存储大对象、大数据量的散列表，而且比起开放寻址法，它更加灵活，支持更多的优化策略。
分析 HashMap
HashMap 的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量多少，就可以依此设置合适的初始容量。
最大装载因子默认是 0.75。当 HashMap 中元素个数超过 0.75 * capacity 时，就会启动扩容，每次扩容后的容量是原来的两倍。
关于 0.75 这个数字的由来，可以查看这篇文章 https://blog.csdn.net/reliveIT/article/details/82960063 。
HashMap 底层采用链表法解决冲突。在 JDK 1.8 之前，冲突的元素插入链表首端，在 JDK 1.8 之后，插入尾端。
另外，在 JDK 1.8 之后，当链表长度超过 8 时，会启动树化，当树中元素少于 6 个时，会退化回链表。
HashMap 的二次哈希，使用的是除留余数法。
因为 A % B = A & (B - 1)，所以，(h ^ (h >>> 16)) & (capitity -1) = (h ^ (h >>> 16)) % capitity。
设计这样的散列表应该从三个方面考虑
❹ 数据结构与算法之美笔记——散列表（上）
摘要:
我们已经知道随机访问数组元素时间复杂度只有 ，效率极高，当我们想利用数组的这个特性时就需要将元素下标与存储信息对应。例如，一个商店只有四件商品，依次编号 0 至 3，这样就可以将四件商品信息按照编号对应下标的方式存储到数组中，依据编号就可以快速从数组中找到相应商品信息。
如果一段时间之后，商店盈利并且重新进货 100 件商品，商家想对大量商品在编号上区分类别，这时陵锋颂候需要使用类别编号加顺序编号的方式标识每件商品，这种编号变得复杂，并不能直接对应数组下标，此时的商品编号又该如何对应数组下标以实现快速查找商品的功能？这时候我们可以将类别编号去除之后按照顺序编号对应数组下标，同样也能享受数组高效率随机访问的福利。这个例子中，商品编号称为“ 键 ”或“ 关键字 ”，将键转化为数组对应下标的方法就是“ 散列函数 ”或“ Hash 函数 ”，由散列函数生成的值叫做“ 散列值 ”或“ Hash 值 ”，而这样的数组就是散列表。
从散列表的原理来看，数据通过散列函数计算得到散列值是关键，这个步骤中散列函数又是其中的核心，一个散列函数需要遵守以下三个原则。
因为散列函数生成的散列值对应数组下标，而数组下标就是非负整数，所以需要满足第一个原则；两个相等的数据经过散列算法得到的散列值肯定相等，否则利用散列值在散列表中查找数据就无从谈起；至于第三个原则虽然在情理之中，却不那么容易做到，即使是被广泛运用的散列算法也会出现散列值冲突的情况，导致无法满足第三个原则。
散列函数作为散列表的核心部分，尺郑必然不能拖散列表的执行效率后腿，毕竟散列表的查询、插入和删除操作都需要经过基告散列函数，所以散列函数不能太复杂，执行效率不能太低。由于散列函数不可避免地都会出现散列冲突情况，散列函数要尽量降低散列冲突，使散列值能够均匀地分布在散列表中。
解决散列冲突主要有“ 开放寻址 ”（open addressing）和“ 链表法 ”（chaining）两类方法。
开放寻址法是指插入操作时，当生成的散列值对应槽位已经被其他数据占用，就探测空闲位置供插入使用，其中探测方法又分为“ 线性探测 ”（Linear Probing）、“ 二次探测 ”（Quadratic Probing）和“ 双重散列 ”（Double hashing）三种。
线性探测是其中较为简单的一种，这种探测方式是当遇到散列冲突的情况就顺序查找（查找到数组尾部时转向数组头部继续查找），直到查找到空槽将数据插入。当进行查找操作时，也是同样的操作，利用散列值从散列表中取出对应元素，与目标数据比对，如果不相等就继续顺序查找，直到查找到对应元素或遇到空槽为止，最坏情况下查找操作的时间复杂度可能会下降为 。
散列表除了支持插入和查找操作外，当然也支持删除操作，不过并不能将需删除的元素置为空。如果删除操作是将元素置为空的话，查找操作遇到空槽就会结束，存储在被删除元素之后的数据就可能无法正确查找到，这时的删除操作应该使用标记的方式，而不是使用将元素置空，当查找到被标识已删除的元素将继续查找，而不是就此停止。
线性探测是一次一个元素的探测，二次探测就是使用都是线性探测的二次方步长探测。例如线性探测是 ，那二次探测对应的就是 。
双重探测是当第一个散列函数冲突时使用第二个散列函数运算散列值，利用这种方式探测。例如，当 冲突时，就使用 计算散列值，如果再冲突就使用 计算散列值，依此类推。
关于散列表的空位多少使用“ 装载因子 ”（load factor）表示，装载因子满足数学关系 ，也就是说装载因子越大，散列表的空闲空间越小，散列冲突的可能性也就越大，一般我们会保持散列表有一定比例的空闲空间。
为了保持散列表一定比例的空闲空间，在装载因子到达一定阈值时需要对散列表数据进行搬移，但散列表搬移比较耗时。你可以试想下这样的步骤，在申请一个新的更大的散列表空间后，需要将旧散列表的数据重新通过散列函数生成散列值，再存储到新散列表中，想想都觉得麻烦。
散列表搬移的操作肯定会降低散列表的操作效率，那能不能对这一过程进行改进？其实可以将低效的扩容操作分摊至插入操作，当装载因子达到阈值时不一次性进行散列表搬移，而是在每次插入操作时将一个旧散列表数据搬移至新散列表，这样搬移操作的执行效率得到了提高，插入操作的时间复杂度也依然能保持 的高效。当新旧两个散列表同时存在时查询操作就要略作修改，需先在新散列表中查询，如果没有查找到目标数据再到旧散列表中查找。
当然，如果你对内存有更高效的利用要求，可以在装载因子降低至某一阈值时对散列表进行缩容处理。
除了开放寻址之外，还可以使用链表法解决散列冲突的问题。散列值对应的槽位并不直接存储数据，而是将数据存储在槽位对应的链表上，当进行查找操作时，根据散列函数计算的散列值找到对应槽位，再在槽位对应的链表上查找对应数据。
链表法操作的时间复杂度与散列表槽位和数据在槽位上的分布情况有关，假设有 n 个数据均匀分布在 m 个槽位的散列表上，那链表法的时间复杂度为 。链表法可以不用像开放寻址一样关心装载因子，但需要注意散列函数对散列值的计算，使链表结点能够尽可能均匀地分布在散列表槽位上，避免散列表退化为链表。有时黑客甚至会精心制造数据，利用散列函数制造散列冲突，使数据集中某些槽位上，造成散列表性能的极度退化。
面对这样的恶意行为散列表只能坐以待毙吗？其实不然，当槽位上的链表过长时，可以将其改造成之前学习过的跳表等，链表改造为跳表后查询的时间复杂度也只是退化为 ，依然是可以接受的范围。
链表法在存储利用上比开放寻址更加高效，不用提前申请存储空间，当有新数据时申请一个新的结点就行。而且链表法对装载因子也不那么敏感，装载因子的增高也只是意味着槽位对应的链表更长而已，链表增长也有将链表改造为跳表等结构的应对策略，所以链表法在装载因子超过 1 的情况下都可保持高效。
开放寻址不存在像链表法一样有链表过长而导致效率降低的烦恼，不过装载因子是开放寻址的晴雨表，装载因子过高会造成散列冲突机率的上升，开放寻址就需要不断探测空闲位置，算法的执行成本会不断被提高。而且在删除操作时只能将数据先标记为删除，对于频繁增删的数据效率会受到影响。
当然也可以在这种风险出现前进行散列表的动态扩容，不过这样就会出现大量空闲的存储空间，导致存储的利用效率过低，这种现象在数据量越大的情况下越明显。所以开放寻址比较适用于数据量较小的情况。
链表法对于散列冲突的处理更加灵活，同时对存储空间的利用效率也更高，但链表结点除了存储数据外还需要存储指针，如果存储数据较小指针占用的存储甚至会导致整体存储翻倍的情况，但存储数据较大时指针占用的存储也就可以忽略不计，所以链表法较适合存储数据对象较大，但频繁的增删操作不会对链表法造成明显的影响。因为这样的特点，链表法更加适合大数据量，或者数据对象较大的时候，如果数据操作频繁，那链表法更是不二之选。
散列表由数组扩展而来，使用散列函数将键计算为散列值，散列值对应数据存储的数组下标。虽然散列表的执行效率较高，但会有散列冲突的问题，可以通过开放寻址法和链表法解决此问题。
开放寻址存储利用效率较低，适用数据量较小并且增删不频繁的情况，如果数据量较大，增删频繁的情况更加适用链表法，相对之下链表法更加普适。
❺ 用哈希（散列）方法处理冲突（碰撞）可能出现堆积（聚集）现象，为什么“存储效率”会受堆积现象直接影响
因为可能数据会重复
简单的例子，网络网盘检查你上传的文件是否违规，就会将你的文件哈希值与违规文件的进行比对，假如你的文件或数据与违规库中的文件的哈希值冲突（碰撞），那么激动文件就会被误封。
❻ r为什么redis散列表内存小
Redis散列表内存小是因为Redis散列表是使用哈希表实现的，而哈希表是一种用空间换时间的数据结构。在哈希表中，元素的存储位置是通过将元素的键转换成哈希值，并对哈希值取模得到的索引位置进行匹配，因此哈希表可以实现O(1)时间复杂度的查找、插入和删除操作。在Redis中，通过对哈希表进行优化，可以更加高效地利用内存空间，从而实现散列表内存小的优势。
具体来说，Redis哈希表的优化包括：
1. 压缩列表：当散列表中的元素数量较少时，Redis会使用压缩列表（ziplist）来存储散列表埋笑橘节点，这样可以减少内存的使用。
2. 散列表节点：Redis使用指针数组来存储哈弯团希表节点，而不是使用指针结构体升咐来存储，这样可以节省一些内存空间。
3. 渐进式rehash：当散列表需要扩容时，Redis会采用渐进式rehash的方式进行，将哈希表的键值对从旧表复制到新表上，并逐渐释放旧表占用的内存，这样可以在不阻塞读写操作的情况下完成散列表的扩容。
综上所述，Redis散列表通过利用哈希表的优势和进行优化，可以实现较小的内存占用，从而达到高效的存储和操作数据的目的。
❼ 散列表和线性存储的区别，在线等！！急！！
（慎派猜1）顺序存储是把逻辑上相邻的节点存储在一羡高组连续的存储单元宽型之中，节点间的逻辑关系由存储单元地址关系隐含表示；
散列存储是根据节点的直确定节点的存储地址。
（2）顺序存储优点是节省存储空间，缺点是不便于修改；
散列存储的优点是查找速度快，但存储空间利用效率低。
（3）顺序存储处理简单，散列存储处理方法复杂。
❽ 数据结构 散列表
散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。设计合理的散列函数可以集成链表和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：
散列表的主要特点：1.将输入映射到数字2.不同的输入产生不同的输出3.相同的输入产生相同的输出4. 当填装因子超过阈值时，能自动扩展。填装因子 = 散列表包含的元素数 / 位置总数，当填装因子 =1，即散列表满的时候，就需要调整散列表的长度，自动扩展的方式是：申请一块旧存储容量 X 扩容系数的新内存地址，然后把原内存地址的值通过其中的 key 再次使用 hash 函数计算存储位置，拷贝到新申请的地址。5. 值呈均匀分布。这里的均匀指水平方向的，即数组维度的。如果多个值被映射到同一个位置，就产生了冲突，需要用链表来存储多个冲突的键值。极端情况是极限冲突，这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将变为最差的 O(n)，如果水平方向填充因子很小，但某些节点下的链表又很长，那值的均匀性就比较差。