A. Redis 利用 Hash 存储节约内存
刚开始用 String 结构来做一个 key-value 存储
但这样单个简单的 key 存储的 value 很大
优化方案是使用 Hash 结构，由于 Hash 结构会在单个 Hash 元素在不足一定数量时进行压缩存储，所以可以大量节约内存。这一点 String 结构里是不存在的
省内存的原因是新建一个 hash 对象时开始是用 ziplist（又称为 small hash）来存储的。这个 ziplist 其实并不是 hash table，但是 ziplist 相比正常的 hash 实现可以节省不少 hash 本身需要的一些元数据存储开销。 尽管 ziplist 的添加，删除，查找都是 O(n)，但是由于一般对象的 field 数量都不太多。 所以使用 ziplist 也是很快的销搜轿，也就是说添加删除平均还是 O(1) 。如果 field 或者 value 的大小超出一定限制后，redis 会在内部自动将 ziplist 替换成正常的 hash 实现，这个限制可以在配置文件中指定 hash-zipmap-max-entries 参数来控制。将 hash-zipmap-max-entries 设置为 1000 时，性能比较好，超过 1000 后 HSET 命令就会导致 CPU 消耗变得非常大
原存储方式：
将数据分段，每一段使用一个 Hash 结构存储，保证了每个 Hash 内部只包含 3 位的 key，也就是 1000 个。如：
这样公共的前缀只存了一次，也节约了一部分漏茄内存亏肆
总的 2 个优化：
B. 哈希表 当拉链长度超过阀值时，会有什么优化
HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）,时，将链表转换为红黑树，这样大大减少了查找时间。
一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。
这样子的HashMap性能上就抱有一定疑问，如果弊颂历说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一樱返直是O(logn),这样会提高租搜HashMap的效率。
https://blog.csdn.net/hefenglian/article/details/79763634
C. 哈希表—哈希函数的设计
上一篇文章中，我们举了 身份证号为关键字 的例子。这里，我们假设真的有一个无限大的空间，那么，可以直接将身份证号作为索引吗？
显然不合适。因为，并不是所有的身份证号都是18位的，对于那些位数在17位以下的，就太浪费这个大空间了。
设计哈希函数的原则是，将我们所关心的键通过哈希函数求出索引， “键”通过哈希函数得到的“索引”分布越均匀越好 (实际上，实现起来非常困难)
那么，对于像身份证号这样的大整数为关键字时，该怎么计算对应的索引呢？
或者像复合类、字符串、浮点数这样类型的关键字，该如何计算它们对应的索引呢？
对于哈希函数来说，我们只能将整型数据作为关键字来求解索引。所以，不管什么类型的关键字，我们应该先将其转化为整型类型的数据。
按照这个思路，以下介绍几种最简单、最基础、最一般、最通用的哈希函数
小范围正整数直接使用
例如，上一篇讲的ASCII值作为关键字
再例如，一个班有30个学生，1—30表示每位学生对应的学号，并作为关键字
像这样的小范围正整数，可以直接将关键字作为索引，存储到数组中去
小范围负整数进行偏移
例如，-100～100的数作为关键字，这时可以每个数都加上100，变为0～200的正整数
这样，就可以将关键字直接作为索引存储到数组中去
大整数取模
例如，身份证号作为关键字，412637199707096354
取后四位(6354)。也就是，mod 10000
假如，取后六位(096354)。即，mod 100 0000 这样，会 分布不均匀
对于身份证号来说，后六位的前两位(09)代表着日期数，也就是1～31的数字。那么，这个六位数不会达到32 0000这么大，中国这么多人口，显然这个数字是不够的，这也就造成了索引分布不均匀
这也就体现了哈希函数的复杂性，也说明了具体问题要具体分析。
上面的取模方式还有一个问题，没有 有效利用所有信息。 我们这样取模，只是利用了关键字的一部分，也就是不管这个人是哪个地区哪个年份出生的，都有可能存储到一个地址中去，这样会增加哈希冲突的概率。那么，该如何解决这个问题呢？
一个简单的解决办法： 模一个素数
为什么要模一个素数呢？简单举个例子
显然，模一个素数，结果会分布的更均匀，哈希冲突的概率也会变小。我们该如何选择这个素数呢？相关的领域专家已经为我们研究出了答案。
假如，需要存储的数在2^5～2^6之间，模上53就可以了。
注：这个表并不是唯一的，一个区间内可以有多个素数
将浮点型解析成大整型，之后再相应取模(如上)
先看一个例子
把一个整数用科学计数法来表示，同样，字符串也可以类似表示。将这个字符串看成26进制，是因为有26个小写字母，如果字符串中有大写字母或者标点符号，那么看成26进制显然祥唯渗是不够的，可以看成是100进制或者256进制等。显然，这个进制是用户可以自己选择的，我们用 B 来表示这个进制
每一个小写字母对应一个数字，这样我们把字符串也转化成了大整型，之后就可以利用上面取模的方式计算哈希值了。
这样就可以计算出字符串的谨脊哈希值了。当B是一个比较大的数或者字符串比较长时，求B的k次方是比较浪费时间的，所以我们可以优化这个表达式
这样就省去了求次方运算。但是，还有可能会出现整型溢出的情况，当B是一个很大的数字或者字符串很长的时候，我们可以再次优化这个表达式
这样，每退出一个小括号，数字都会变成比M先得数字，就不会出现溢出情况了
假如我们自己定义一个类，日期类
Date：year，month，day
为这个Date类设计哈希函数，可以像字符串那样，将类的属性值看着是一个字符
这山哪样，就求出了复合类的哈希值。
一致性： 当关键字相同时，经过哈希函数求出的哈希值也是相同的。
反过来是不成立的，即当哈希值相同时关键字不一定相同。哈希值相同，取模后得到的索引也相同，即不同的关键字对应的存储位置相同，这也就是所谓的哈希冲突。
高效性： 我们设计哈希函数就是为了高效存储数据，如果哈希函数的设计就消耗过多性能，那么就得不偿失了
均匀性： 通过哈希函数求出的索引必须是分布均匀的。
以上，就是转化为整型求哈希函数。但是， 这并不是求哈希函数唯一的方法 。
D. redis 用hashmap省内存的误解
看过许多redis优化的案例，裤橘通过引入hashmap的方式将key散列到多个hashmap，
具体可以见：
Redis 利用Hash存储节约内存 - 刘本龙的专栏 - CSDN博客
我们得到如下公式：
原来是:
key1,key2,key3,key4,key5
变成
hash1:
key1:value1
key2:value2
key3:value2
hash2:
key4:value4
key5:value5
虽然名义上5个key变成了2个hashmap，但是每个filed还是会保存原始的key，所以从key减少的层面是行不通的，这个时候就要从底层储存结构去看。
redis对hashmap有一个优化，当filed数量比较少胡滚团的时候(因为ziplist是用顺序遍历的方式查找元素，所以数备源量多了复杂度是o(N)肯定不合适。
)，会用一个叫ziplist的结构保存，而不是传统的hash结构，ziplist有几个特点：
ziplist介绍
https://blog.csdn.net/weixin_30783913/article/details/98141347
所以hashmap能省内存是依赖ziplist的结构，而不是key的减少。
使用ziplist可以用以下参数控制
必须满足以上两个条件，那么该key会被压缩。否则就是按照正常的hash结构来存储hash类型的key。
E. 哈希函数详解（一）
Hash（哈希），又称“散列”。
散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。
在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照[散列函数]的分类进行排列。
在介绍一些集合时，我们总强调需要重写某个类的 equals() 方法和 hash Code() 方法，确保唯一性。这里的 hash Code() 表示的是对当前对象的唯一标示。计算 hash Code 的过程就称作 哈希。
我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在 查找某个元素 是否存在的过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大 减少比较次数 。
举个栗子：
现在有 4 个数 {2,5,9,13}，需要查找 13 是否存在。
这样需要遍历 4 次才能找到，时间复杂度为 O(n)。
四个数 {2,5,9,13} 对应的哈希值为：
然后把它们存储到对应的位置。
当要查找 13 时，只要先使用哈希函数计算它的位置，然后去那个位置查看是否存在就好了，本例中只需查找一次，时间复杂度为 O(1)。
因此可以发现，哈希 其实是随机存储的一种优化，先进行分类，然后查找时按照这个对象的分类去找。
哈希通过一次计算大幅度缩小查找范围，自然比从全部数据里查找速度要快。
比如你和我一样是个剁手族买书狂，家里书一大堆，如果书存放时不分类直接摆到书架上（数组存储），找某本书时可能需要脑袋从左往右从上往下转好几圈才能发现；如果存放时按照类别分开放，技术书、小说、文学等等分开（按照某种哈希函数计算），找书时只要从它对应的分类里找，自然省事多了。
哈希的过程中需要使用哈希函数进行计算。
哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。
表示为：
address = H [key]
哈希的过程中需要使用哈坦谈希函数进行计算。
哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。
表示为：
address = H [key]
取关键字或关键字的某个线性函数值为散列地址。
即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。
取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
即 H(key) = key % p, p < m。
当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
随机分布的关键字，得到的散列地址也是随机分布的。
将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。
选择一个随机函数，把关键字的随机函数值作为它的哈希值。
通常当关键字的长度不等时用这种方法。
构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是 尽可能少的让隐碰产携如生冲突 。
通常考虑的因素有 关键字的长度 和 分布情况 、 哈希值的范围 等。
如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。
F. Redis的内存优化
一. redisObject对象
二. 缩减键值对象
三. 共享对象池
四. 字符串优化
五. 编码优化
六. 控制key的数量
Redis存储的所有值对象在内部定义为redisObject结构体，内部结构如下图所示。
表示当前对象使用的数据类型，Redis主要支持5种数据类型:string,hash,list,set,zset。可以使用type {key}命令查看对象所属类型，type命令返回的是值对象类型，键都是string类型。
表示Redis内部编码类型，encoding在Redis内部使用，代表当前对象内部采用哪种数据结构实现。理解Redis内部编码方式对于优化内存非常重要 ，同一个对象采用不同的编码实现内存占用存在明显差异，具体细节见之后编码优化部分。
记录对象最后一次被访问的时间，当配置了 maxmemory和maxmemory-policy=volatile-lru | allkeys-lru 时， 用于辅助LRU算法删除键数据。可以使用object idletime {key}命令在不更新lru字段情况下查看当前键的空闲时间。
记录当前对象被引用的次数，用于通过引用次数回收内存，当refcount=0时，可以安全回收当前对象空间。使用object refcount {key}获取当前对象引用。当对象为整数且范围在[0-9999]时，Redis可以使用共享对象的方式来节省内存。具体细节见之后共享对象池部分。
与对象的数据内容相关，如果是整数直接存储数据，否则表示指向数据的指针。Redis在3.0之后对值对象是字符串且长度<=39字节的数据，内部编码为embstr类型，字符串sds和redisObject一起分配，从而只要一次内存操作。
降低Redis内存使用最直接的方式就是缩减键（key）和值（value）的长度。
其中java-built-in-serializer表示JAVA内置序列化方式，更多数据见jvm-serializers项目: https://github.com/eishay/jvm-serializers/wiki，其它语言也有各自对应的高效序列化工具。
值对象除了存储二进制数据之外，通常还会使用通用格式存储数据比如:json，xml等作为字符串存储在Redis中。这种方式优点是方便调试和跨语言，但是同样的数据相比字节数组所需的空间更大，在内存紧张的情况下，可以使用通用压缩算法压缩json,xml后再存入Redis，从而降低内存占用，例如使用GZIP压缩后的json可降低约60%的空间。
对象共享池指Redis内部维护[0-9999]的整数对象池。创建大量的整数类型redisObject存在内存开销，每个redisObject内部结构至少占16字节，甚至超过了整数自身空间消耗。所以Redis内存维护一个[0-9999]的整数对象池，用于节约内存。 除了整数值对象，其他类型如list,hash,set,zset内部元素也可以使用整数对象池。因此开发中在满足需求的前提下，尽量使用整数对象以节省内存。
整数对象池在Redis中通过变量REDIS_SHARED_INTEGERS定义，不能通过配置修改。可以通过object refcount 命令查看对象引用数验证是否启用整数对象池技术，如下:
设置键foo等于100时，直接使用共享池内整数对象，因此引用数是2，再设置键bar等于100时，引用数又变为3，如下图所示。
使用整数对象池究竟能降低多少内存？让我们通过测试来对比对象池的内存优化效果，如下表所示。
使用共享对象池后，相同的数据内存使用降低30%以上。可见当数据大量使用[0-9999]的整数时，共享对象池可以节约大量内存。需要注意的是对象池并不是只要存储[0-9999]的整数就可以工作。当设置maxmemory并启用LRU相关淘汰策略如:volatile-lru，allkeys-lru时，Redis禁止使用共享对象池，测试命令如下：
LRU算法需要获取对象最后被访问时间，以便淘汰最长未访问数据，每个对象最后访问时间存储在redisObject对象的lru字段。对象共享意味着多个引用共享同一个redisObject，这时lru字段也会被共享，导致无法获取每个对象的最后访问时间。如果没有设置maxmemory，直到内存被用尽Redis也不会触发内存回收，所以共享对象池可以正常工作。
综上所述，共享对象池与maxmemory+LRU策略冲突，使用时需要注意。 对于ziplist编码的值对象，即使内部数据为整数也无法使用共享对象池，因为ziplist使用压缩且内存连续的结构，对象共享判断成本过高，ziplist编码细节后面内容详细说明。
首先整数对象池复用的几率最大，其次对象共享的一个关键操作就是判断相等性，Redis之所以只有整数对象池，是因为整数比较算法时间复杂度为O(1)，只保留一万个整数为了防止对象池浪费。如果是字符串判断相等性，时间复杂度变为O(n)，特别是长字符串更消耗性能(浮点数在Redis内部使用字符串存储)。对于更复杂的数据结构如hash,list等，相等性判断需要O(n2)。对于单线程的Redis来说，这样的开销显然不合理，因此Redis只保留整数共享对象池。
字符串对象是Redis内部最常用的数据类型。所有的键都是字符串类型， 值对象数据除了整数之外都使用字符串存储。比如执行命令:lpush cache:type “redis” “memcache” “tair” “levelDB” ，Redis首先创建”cache:type”键字符串，然后创建链表对象，链表对象内再包含四个字符串对象，排除Redis内部用到的字符串对象之外至少创建5个字符串对象。可见字符串对象在Redis内部使用非常广泛，因此深刻理解Redis字符串对于内存优化非常有帮助:
Redis没有采用原生C语言的字符串类型而是自己实现了字符串结构，内部简单动态字符串(simple dynamic string)，简称SDS。结构下图所示。
Redis自身实现的字符串结构有如下特点:
因为字符串(SDS)存在预分配机制，日常开发中要小心预分配带来的内存浪费，例如下表的测试用例。
从测试数据可以看出，同样的数据追加后内存消耗非常严重，下面我们结合图来分析这一现象。阶段1每个字符串对象空间占用如下图所示。
阶段1插入新的字符串后，free字段保留空间为0，总占用空间=实际占用空间+1字节，最后1字节保存‘\0’标示结尾，这里忽略int类型len和free字段消耗的8字节。在阶段1原有字符串上追加60字节数据空间占用如下图所示。
追加操作后字符串对象预分配了一倍容量作为预留空间，而且大量追加操作需要内存重新分配，造成内存碎片率(mem_fragmentation_ratio)上升。直接插入与阶段2相同数据的空间占用，如下图所示。
阶段3直接插入同等数据后，相比阶段2节省了每个字符串对象预分配的空间，同时降低了碎片率。
字符串之所以采用预分配的方式是防止修改操作需要不断重分配内存和字节数据拷贝。但同样也会造成内存的浪费。字符串预分配每次并不都是翻倍扩容，空间预分配规则如下:
字符串重构:指不一定把每份数据作为字符串整体存储，像json这样的数据可以使用hash结构，使用二级结构存储也能帮我们节省内存。同时可以使用hmget,hmset命令支持字段的部分读取修改，而不用每次整体存取。例如下面的json数据：
分别使用字符串和hash结构测试内存表现，如下表所示。
根据测试结构，第一次默认配置下使用hash类型，内存消耗不但没有降低反而比字符串存储多出2倍，而调整hash-max-ziplist-value=66之后内存降低为535.60M。因为json的videoAlbumPic属性长度是65，而hash-max-ziplist-value默认值是64，Redis采用hashtable编码方式，反而消耗了大量内存。调整配置后hash类型内部编码方式变为ziplist，相比字符串更省内存且支持属性的部分操作。下一节将具体介绍ziplist编码优化细节。
Redis对外提供了string,list,hash,set,zet等类型，但是Redis内部针对不同类型存在编码的概念，所谓编码就是具体使用哪种底层数据结构来实现。编码不同将直接影响数据的内存占用和读写效率。使用object encoding {key}命令获取编码类型。如下:
Redis针对每种数据类型(type)可以采用至少两种编码方式来实现，下表表示type和encoding的对应关系。
了解编码和类型对应关系之后，我们不禁疑惑Redis为什么需要对一种数据结构实现多种编码方式？
主要原因是Redis作者想通过不同编码实现效率和空间的平衡。比如当我们的存储只有10个元素的列表，当使用双向链表数据结构时，必然需要维护大量的内部字段如每个元素需要:前置指针，后置指针，数据指针等，造成空间浪费，如果采用连续内存结构的压缩列表(ziplist)，将会节省大量内存，而由于数据长度较小，存取操作时间复杂度即使为O(n2)性能也可满足需求。
Redis内存优化
编码类型转换在Redis写入数据时自动完成，这个转换过程是不可逆的，转换规则只能从小内存编码向大内存编码转换。例如：
以上命令体现了list类型编码的转换过程，其中Redis之所以不支持编码回退，主要是数据增删频繁时，数据向压缩编码转换非常消耗CPU，得不偿失。以上示例用到了list-max-ziplist-entries参数，这个参数用来决定列表长度在多少范围内使用ziplist编码。当然还有其它参数控制各种数据类型的编码，如下表所示：
掌握编码转换机制，对我们通过编码来优化内存使用非常有帮助。下面以hash类型为例，介绍编码转换的运行流程，如下图所示。
理解编码转换流程和相关配置之后，可以使用config set命令设置编码相关参数来满足使用压缩编码的条件。对于已经采用非压缩编码类型的数据如hashtable,linkedlist等，设置参数后即使数据满足压缩编码条件，Redis也不会做转换，需要重启Redis重新加载数据才能完成转换。
ziplist编码主要目的是为了节约内存，因此所有数据都是采用线性连续的内存结构。ziplist编码是应用范围最广的一种，可以分别作为hash、list、zset类型的底层数据结构实现。首先从ziplist编码结构开始分析，它的内部结构类似这样:<….>。一个ziplist可以包含多个entry(元素)，每个entry保存具体的数据(整数或者字节数组)，内部结构如下图所示。
ziplist结构字段含义：
根据以上对ziplist字段说明，可以分析出该数据结构特点如下:
下面通过测试展示ziplist编码在不同类型中内存和速度的表现，如下表所示。
测试数据采用100W个36字节数据，划分为1000个键，每个类型长度统一为1000。从测试结果可以看出：
intset编码是集合(set)类型编码的一种，内部表现为存储有序，不重复的整数集。当集合只包含整数且长度不超过set-max-intset-entries配置时被启用。执行以下命令查看intset表现：
以上命令可以看出intset对写入整数进行排序，通过O(log(n))时间复杂度实现查找和去重操作，intset编码结构如下图所示。
intset的字段结构含义：
根据以上测试结果发现intset表现非常好，同样的数据内存占用只有不到hashtable编码的十分之一。intset数据结构插入命令复杂度为O(n)，查询命令为O(log(n))，由于整数占用空间非常小，所以在集合长度可控的基础上，写入命令执行速度也会非常快，因此当使用整数集合时尽量使用intset编码。上表测试第三行把ziplist-hash类型也放入其中，主要因为intset编码必须存储整数，当集合内保存非整数数据时，无法使用intset实现内存优化。这时可以使用ziplist-hash类型对象模拟集合类型，hash的field当作集合中的元素，value设置为1字节占位符即可。使用ziplist编码的hash类型依然比使用hashtable编码的集合节省大量内存。
当使用Redis存储大量数据时，通常会存在大量键，过多的键同样会消耗大量内存。Redis本质是一个数据结构服务器，它为我们提供多种数据结构，如hash，list，set，zset 等结构。使用Redis时不要进入一个误区，大量使用get/set这样的API，把Redis当成Memcached使用。对于存储相同的数据内容利用Redis的数据结构降低外层键的数量，也可以节省大量内存。如下图所示，通过在客户端预估键规模，把大量键分组映射到多个hash结构中降低键的数量。
hash结构降低键数量分析：
通过这个测试数据，可以说明：
关于hash键和field键的设计：
使用hash结构控制键的规模虽然可以大幅降低内存，但同样会带来问题，需要提前做好规避处理。如下:
本文主要讲解Redis内存优化技巧，Redis的数据特性是”ALL IN MEMORY”，优化内存将变得非常重要。对于内存优化建议读者先要掌握Redis内存存储的特性比如字符串，压缩编码，整数集合等，再根据数据规模和所用命令需求去调整，从而达到空间和效率的最佳平衡。建议使用Redis存储大量数据时，把内存优化环节加入到前期设计阶段，否则数据大幅增长后，开发人员需要面对重新优化内存所带来开发和数据迁移的双重成本。当Redis内存不足时，首先考虑的问题不是加机器做水平扩展，应该先尝试做内存优化。当遇到瓶颈时，再去考虑水平扩展。即使对于集群化方案，垂直层面优化也同样重要，避免不必要的资源浪费和集群化后的管理成本。
G. hashjoinrightsemi如何优化
MySQL一直被人诟病没有实现HashJoin，最新发布的8.0.18已经带上了这个功能，令人欣喜。有时候在想，MySQL为什么一直不支持HashJoin呢？我想可能是因为MySQL多用于简单的OLTP场景，并且在互联网应用居多，需求没那么紧急。另一方面可能是因为以前完全靠社区，这种演进速度毕竟有限，Oracle收购MySQL后，MySQL的发版演进速度明显加快了很多。
HashJoin本身算法实现并不复杂，要说复杂，可能是优化器配套选择执行计划时，是否选择HashJoin，选择外表，内表可能更复杂一点。不管怎样现在已经有了HashJoin，优化器在选择Join算法时又多了一个选择。MySQL本着实用主义，相信这个功能增强也回应了一些质疑，有些功能不是没有能力做好，而是有它的优先级。
在8.0.18之前，MySQL只支持NestLoopJoin算法，最简单的就是Simple NestLoop Join，MySQL针对这个算法做了若干优化，实现了Block NestLoop Join，Index NestLoop Join和Batched Key Access等，有了这些优化，在一定程度上能缓解对HashJoin的迫切程度。下文会单独拿一个章节讲MySQL的这些Join优化，下面先讲HashJoin。
Hash Join算法
NestLoopJoin算法简单来说，就是双重循环，遍历外表(驱动表)，对于外表的每一行记录，然后遍历内表，然后判断join条件是否符合，进而确定是否将记录吐出给上一个执行节点。从算法角度来说，这是一个M*N的复杂度。HashJoin是针对equal-join场景的优化，基本思想是，将外表数据load到内存，并建立hash表，这样只需要遍历一遍内表，就可以完成join操作，输出匹配的记录。如果数据能全部load到内存当然好，逻辑也简单，一般称这种join为CHJ(Classic Hash Join)，之前MariaDB就已经实现了这种HashJoin算法。如果数据不能全部load到内存，就需要分批load进内存，然后分批join，下面具体介绍这几种join算法的实现。
In-Memory Join(CHJ)
HashJoin一般包括两个过程，创建hash表的build过程和探测hash表的probe过程。
1).build phase
遍历外表，以join条件为key，查询需要的列作为value创建hash表。这里涉及到一个选择外表的依据，主要是评估参与join的两个表(结果集)的大小来判断，谁小就选择谁，这样有限的内存更容易放下hash表。
2).probe phase
hash表build完成后，然后逐行遍历内表，对于内表的每个记录，对join条件计算hash值，并在hash表中查找，如果匹配，则输出，否则跳过。所有内表记录遍历完，则整个过程就结束了。过程参照下图，来源于MySQL官方博客
左侧是build过程，右侧是probe过程，country_id是equal_join条件，countries表是外表，persons表是内表。
On-Disk Hash Join
CHJ的限制条件在于，要求内存能装下整个外表。在MySQL中，Join可以使用的内存通过参数join_buffer_size控制。如果join需要的内存超出了join_buffer_size，那么CHJ将无能为力，只能对外表分成若干段，每个分段逐一进行build过程，然后遍历内表对每个分段再进行一次probe过程。假设外表分成了N片，那么将扫描内表N次。这种方式当然是比较弱的。在MySQL8.0中，如果join需要内存超过了join_buffer_size，build阶段会首先利用hash算将外表进行分区，并产生临时分片写到磁盘上；然后在probe阶段，对于内表使用同样的hash算法进行分区。由于使用分片hash函数相同，那么key相同(join条件相同)必然在同一个分片编号中。接下来，再对外表和内表中相同分片编号的数据进行CHJ的过程，所有分片的CHJ做完，整个join过程就结束了。这种算法的代价是，对外表和内表分别进行了两次读IO，一次写IO。相对于之之前需要N次扫描内表IO，现在的处理方式更好。
第一张图是外表的分片过程，第二张图是内表的分片过程，第三张图是对分片进行build+probe过程。
Grace Hash Join
主流的数据库Oracle，SQLServer，PostgreSQL早就支持了HashJoin。Join算法都类似，这里介绍下Oracle使用的Grace Hash Join算法。其实整个过程与MySQL的HashJoin类似，主要有一点区别。当出现join_buffer_size不足时，MySQL会对外表进行分片，然后再进行CHJ过程。但是，极端情况下，如果数据分布不均匀，导致大量的数据hash后都分布在一个分桶中，导致分片后，join_buffer_size仍然不够，MySQL的处理方式是一次读分片读若干记录构建hash表，然后probe对应的外表分片。处理完一批后，清理hash表，重复上述过程，直到这个分片的所有数据处理完为止。这个过程与CHJ在join_buffer_size不足时，处理逻辑相同。
GraceHash在遇到这种情况时，会继续分片进行二次Hash，直到内存足够放下一个hash表为止。但是，这里仍然有极端情况，如果输入join条件都相同，那么无论进行多少次Hash，都没法分开，那么这个时候GraceHashJoin也退化成和MySQL的处理方式一样。
hybrid hash join
与GraceHashJoin的区别在于，如果缓存能缓存足够多的分片数据，会尽量缓存，那么就不必像GraceHash那样，严格地将所有分片都先读进内存，然后写到外存，然后再读进内存去走build过程。这个是在内存相对于分片比较充裕的情况下的一种优化，目的是为了减少磁盘的读写IO。目前Oceanbase的HashJoin采用的是这种join方式。
MySQL-Join算法优化
在MySQL8.0.18之前，也就是在很长一段时间内，MySQL数据库并没有HashJoin，主要的Join算法是NestLoopJoin。SimpleNestLoopJoin显然是很低效的，对内表需要进行N次全表扫描，实际复杂度是N*M，N是外表的记录数目，M是记录数，代表一次扫描内表的代价。为此，MySQL针对SimpleNestLoopJoin做了若干优化，下面贴的图片均来自网络。
BlockNestLoopJoin(BNLJ)
MySQL采用了批量技术，即一次利用join_buffer_size缓存足够多的记录，每次遍历内表时，每条内表记录与这一批数据进行条件判断，这样就减少了扫描内表的次数，如果内表比较大，间接就缓解了IO的读压力。
IndexNestLoopJoin(INLJ)
如果我们能对内表的join条件建立索引，那么对于外表的每条记录，无需再进行全表扫描内表，只需要一次Btree-Lookup即可，整体时间复杂度降低为N*O(logM)。对比HashJoin，对于外表每条记录，HashJoin是一次HashTable的search，当然HashTable也有build时间，还需要处理内存不足的情况，不一定比INLJ好。
Batched Key Access
IndexNestLoopJoin利用join条件的索引，通过Btree-Lookup去匹配减少了遍历内表的代价。如果join条件是非主键列，那么意味着大量的回表和随机IO。BKA优化的做法是，将满足条件的一批数据按主键排序，这样回表时，从主键的角度来说就相对有序，缓解随机IO的代价。BKA实际上是利用了MRR特性(MultiRangeRead)，访问数据之前，先将主键排序，然后再访问。主键排序的缓存大小通过参数read_rnd_buffer_size控制。
总结
MySQL8.0以后，Server层代码做了大量的重构，虽然优化器相对于Oracle还有很大差距，但一直在进步。HashJoin的支持使得MySQL优化器有更多选择，SQL的执行路径也能做到更优，尤其是对于等值join的场景。虽然MySQL之前对于Join做过若干优化，比如NBLJ，INLJ以及BKA等，但这些代替不了HashJoin的作用。一个好用的数据库就应该具备丰富的基础能力，利用优化器分析出合适场景，然后拿出对应的基础能力以最高效的方式响应请求。
H. 小白如何秒懂区块链中的哈希计算
小白如何秒懂区块链中的哈希计算
当我在区块链的学习过程中，发现有一个词像幽灵一样反复出现，“哈希”，英文写作“HASH”。
那位说“拉稀”同学你给我出去！！
这个“哈希”据说是来源于密码学的一个函数，尝试搜一搜，论文出来一堆一堆的，不是横式就是竖式，不是表格就是图片，还有一堆看不懂得xyzabc。大哥，我就是想了解一下区块链的基础知识，给我弄那么难干啥呀？！我最长的密码就是123456，复杂一点的就是654321，最复杂的时候在最后加个a，你给我写的那么复杂明显感觉脑力被榨干，仅有的脑细胞成批成批的死亡！为了让和我一样的小白同学了解这点，我就勉为其难，努力用傻瓜式的语言讲解一下哈希计算，不求最准确但求最简单最易懂。下面我们开始：
# 一、什么是哈希算法
## 1、定义：哈希算法是将任意长度的字符串变换为固定长度的字符串。
从这里可以看出，可以理解为给**“哈希运算”输入一串数字，它会输出一串数字**。
如果我们自己定义 “增一算法”，那么输入1，就输出2；输入100就输出101。
如果我我们自己定义“变大写算法”，那么输入“abc”输出“ABC”。
呵呵，先别打我啊！这确实就只是一个函数的概念。
## 2、特点：
这个哈希算法和我的“增一算法”和“变大写算裤御法”相比有什么特点呢？
1）**确定性，算得快**：咋算结果都一样，算起来效率高。
2）**不可逆**：就是知道输出推不出输入的值。
3）**结果不可测**：就是输入变一点，结果天翻地覆毫无规律。
总之，这个哈希运算就是个黑箱，是加密的好帮手！你说“11111”，它给你加密成“”，你说“11112”它给你弄成“”。反正输入和输出一个天上一个地下，即使输入相关但两个输出毫不相关。
# 二、哈希运算在区块链中的使用
## 1、数据加密
**交易数据是通过哈希运算进行加密，并把相应的哈希值写入区块头**。如下图所示，一个区块头包含了上一个区块的hash值，还包含下一个区块的hash值。
1）、**识别区块数据是否被篡改**：区块链的哈希值能够唯一而精准地标识一个区块，区块链中任意节点通过简单的哈希计算都可以获得这个区块的哈希值，计算出的哈希值没有变化也就意味着区块链中的信息没有被篡改。
2）、**把各个区块串联成区块链**：每个区块都包含上一个区块的哈希值和下一个区块的值，就相当于通过上一个区块的哈希值挂钩到上陪前一个区块尾，通过下一个区块的哈希值挂钩到下一个区块链的头，就自然而然形成一个链式结构的区块链。
## 2、加密交易地址及哈希
在上图的区块头中，有一个Merkle root（默克尔根）的哈希值，它是用来做什么的呢？
首先了解啥叫Merkle root？ 它就是个二叉树结构的根。啥叫二叉树？啥叫根？看看下面的图就知道了。一分二，二分四，四分八可以一直分下去就叫二叉树。根就是最上面的节点就叫 根。
这个根的数据是怎么来的呢？是把一个区块中的每笔交易的哈希值得出后，再两两哈希值再哈希，再哈希，再哈希，直到最顶层的数值。
这么哈希了半天，搞什么事情？有啥作用呢？
1）、**快速定位每笔交易**：由于交易在存储上是线性存储，定位到某笔交易会需要遍历，效率低时间慢，通过这样的二叉树可以快速定位到想要找的交易。
举个不恰当的例子：怎么找到0-100之间的一个任意整数？（假设答案是88）那比较好的一个方法就是问：1、比50大还是小？2、胡乱岩比75大还是小？3、比88大还是小？ 仅仅通过几个问题就可以快速定位到答案。
2）、**核实交易数据是否被篡改**：从交易到每个二叉树的哈希值，有任何一个数字有变化都会导致Merkle root值的变化。同时，如果有错误发生的情况，也可以快速定位错误的地方。
## 3、挖矿
在我们的区块头中有个参数叫**随机数Nonce，寻找这个随机数的过程就叫做“挖矿”**！网络上任何一台机器只要找到一个合适的数字填到自己的这个区块的Nonce位置，使得区块头这6个字段（80个字节）的数据的哈希值的哈希值以18个以上的0开头，谁就找到了“挖到了那个金子”！既然我们没有办法事先写好一个满足18个0的数字然后反推Nounce，唯一的做法就是从0开始一个一个的尝试，看结果是不是满足要求，不满足就再试下一个，直到找到。
找这个数字是弄啥呢？做这个有什么作用呢？
1）、**公平的找到计算能力最强的计算机**：这个有点像我这里有个沙子，再告诉你它也那一个沙滩的中的一粒相同，你把相同的那粒找出来一样。那可行的办法就是把每一粒都拿起来都比较一下！那么比较速度最快的那个人是最有可能先早到那个沙子。这就是所谓的“工作量证明pow”，你先找到这个沙子，我就认为你比较的次数最多，干的工作最多。
2）、**动态调整难度**：比特币为了保证10分钟出一个区块，就会每2016个块（2周）的时间计算一下找到这个nonce数字的难度，如果这2016个块平均时间低于10分钟则调高难度，如高于十分钟则调低难度。这样，不管全网的挖矿算力是怎么变化，都可以保证10分钟的算出这个随机数nonce。
# 三、哈希运算有哪些？
说了这么多哈希运算，好像哈希运算就是一种似的，其实不是！作为密码学中的哈希运算在不断的发展中衍生出很多流派。我看了”满头包”还是觉得内在机理也太复杂了，暂时罗列如下，小白们有印象知道是怎么回事就好。
从下表中也可以看得出，哈希运算也在不断的发展中，有着各种各样的算法，各种不同的应用也在灵活应用着单个或者多个算法。比特币系统中，哈希运算基本都是使用的SHA256算法，而莱特币是使用SCRYPT算法，夸克币（Quark）达世币（DASH）是把很多算法一层层串联上使用，Heavycoin（HAV）却又是把一下算法并联起来，各取部分混起来使用。以太坊的POW阶段使用ETHASH算法，ZCASH使用EQUIHASH。
需要说明的是，哈希运算的各种算法都是在不断升级完善中，而各种币种使用的算法也并非一成不变，也在不断地优化中。
**总结**：哈希运算在区块链的各个项目中都有着广泛的应用，我们以比特币为例就能看到在**数据加密、交易数据定位、挖矿等等各个方面都有着极其重要的作用**。而哈希运算作为加密学的一门方向不断的发展和延伸，身为普通小白的我们，想理解区块链的一些基础概念，了解到这个层面也已经足够。
I. hashmap的最大容量是多少，在多少的时候会导致查询响应过慢
原则上，hashmap的插入和搜索，复杂度都是1，是非常快速的跟你的容量大小通常是没有直接关系的但是这是理想的情况。
这里说的理想，是在你所存储的对象的hashcode这个方法写的非常有效的情况下。根据hash的原理，存放一个对象是根据他的hashcode来计算的，如果没有哈希冲突，那么他的存储效率是最高，最完美的。
为什么哈希冲突会使得效率下降呢？
具体来分析，假设一个对象O1，他的hashcode算出来是1，另一个对象是O2，hashcode算起来也是1. 先放入O1对象，这时候速度很快，根据hashcode计算出来这个对象应该在哪个位置存放，然后直接放进去。但是到了放O2的时候，根据hashcode计算的地址存放，发现之前已经有O1了，那么显然是不能放的，因此就要采取些措施，比如，再计算一次，然后分配存放的地址（如果冲突，将继续，知道解决），一种最恶劣的情况下，很多很多的对象都存在hash冲突，那么重要就变得存储越来越慢。但是这个不是hashmap的责任，而是你的对象的hashcode方法没有定义好，使得冲突频繁
另外，哈希表为了避免这种冲突，会有一点优化。简单的说，原本可以放100个数据的空间，当放到80个的时候，根据经验，接下去冲突的可能性会更加高，就好比一个靶子上80%都是箭的时候你再射一箭出去，射中箭的可能性很大。因此就自动增加空间来减小冲突可能性。
80/100 = 0.8 这个0.8就是负载因子。
java中的hashmap的负载因子是0.75说了写理论。说这个的原因是想解释一下你的疑问“10000条的时候在搜索的时候很快，那么在多少条的时候可能导致效率下降呢”。这个答案是肯定的，就是存储的量跟存储效率没有直接的关系。
这页是hash表这个数据结构的优势所在
如果你觉得效率出现问题的时候，应该去关注一下你的存储对象的hashcode方法写的是否有问题
如果想更完美的解决效率问题，还可以手动指定hashmap的负载因子（用HashMap（int factor）这个构造方法），负载因子越低，冲突可能越小。但是牺牲的空间会相应增加
如果还是不能很好理解，可以先参看hash这个数据结构的特点，和JDK中HashMap的源代码，以及注释
学好java，数据结构是很重要的，理解原理的使用，跟生搬硬套的使用，不可同年而语
所以，去面试淘宝，腾讯，化为这种公司不会问你struts怎么用，只会问你struts怎么写。如同不会问你hashmap怎么用，而会问你hashmap的设计理念，和实现原理
希望对你有所帮助