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的設計理念，和實現原理
希望對你有所幫助