hash演算法分表

Ⅰ 大數據量最近的存儲分表常見演算法

大數據量最近的存儲分表常見演算法
當一個應用的數據量大的時候，我們用單表和單庫來存儲會嚴重影響操作速度，如mysql的myisam存儲，我們經過測試，200w以下的時候，mysql的訪問速度都很快，但是如果超過200w以上的數據，他的訪問速度會急劇下降，影響到我們webapp的訪問速度，而且數據量太大的話，如果用單表存儲，就會使得系統相當的不穩定，mysql服務很容易掛掉。所以當數據量超過200w的時候，建議系統工程師還是考慮分表.
以下是幾種常見的分表演算法。
1.按自然時間來分表/分庫;
如一個應用的數據在一年後數據量會達到200w左右，那麼我們就可以考慮用一年的數據來做為一個表或者庫來存儲，例如，表名為app，那麼2010年的數據就是app_2010，app_2011;如果數據量在一個月就達到了200w左右，那麼我們就可以用月份來分，app_2010_01，app_2010_02.
2.按數字類型hash分表/分庫;
如果我們要存儲用戶的信息，我們應用的注冊量很大，我們用單表是不能滿足存儲需求的，那麼我們就可以用用戶的編號來進行hash，常見的是用取余操作，如果我們要分30張表來存儲用戶的信息，那麼用戶編號為1的用戶1%30=1，那麼我們就存在user_01表裡，如用戶的編號為500，那麼500%30=20，那麼我們就將此用戶的信息存儲在user_20的表裡.
3.按md5值來分表/分庫;
我們假設要存儲用戶上傳的文件，如果上傳量大的話，也會帶來系統的瓶頸問題，我們做過試驗，在一個文件夾下如果超過200個文件的話，文件的瀏覽效率會降低，當然，這個不屬於我們本文討論的范圍，這塊也要做散列操作.我們可以用文件的用戶名來md5或者用文件的md5校驗值來做，我們就可以用md5的前5位來做hash，這樣最多我們就可以得到5^5=3125個表，每次在存儲文件的時候，就可以用文件名的md5值的前5位來確定這個文件該存那張表.
4.實例:某微博的url加密演算法和存儲策略的猜想.
現在好多微博都用這樣的url來訪問，如果他們的域名為www.example.com，那麼如果你發微博的時候，你會發現你所發的url都變成了http://t.cn/Mx4ja1，這樣的形式，他們是怎麼進行這樣的轉換呢?我猜想就是用到了我們上面講的md5的存儲和查找規則，用你發的url來進行md5，得到md5值之後，如我們例子來說，就會用前6位來進行分表.
5.分表所帶來的問題.
分表也會帶來一系列的問題，如分頁的實現，統計的實現，如果我們要做一個所有數據的分頁，那麼我們得每張表都得遍歷一遍，這樣訪問效率會很低下.之前我嘗試過用mysql的代理來實現，最終用tcsql來實現了.
6.分表演算法的選擇.
首先，分表適合於沒有大的列表的應用來使用，要不然，會為這部分做好多額外的工作，如果你的應用數據量不是特別大的話，最好別用分表。7.針對每秒插入數據500+的設想為什麼要這個呢，因為很多資料庫在數據上千萬級別後，每秒插入數據的數度不是很快了，所以500/秒的速度夠嗆，解決方案設想：建立數據總表及兩個緩沖表，結構完全相同，將數據先插入其中一個緩沖表中，等到一定時間(插入效率降低之前)，轉向插入另一個緩沖表，同時啟動一個後台進程將第
一個緩沖表的的數據轉入總表，轉入總表後刪除第一個緩沖表中的數據; 再等到一定時間(還是插入效率降低之前)，轉向插入第一個緩沖表，這時啟動一個後台進程將第
二個緩沖表的的數據轉入總表，轉入總表後刪除第二個緩沖表中的數據; 如此循環往復...

如果後台進程處理的時間超過兩個緩沖表的循環周期的話，甚至可以考慮建立三個乃至四個緩沖表。

這僅僅是解決插入效率，查詢什麼的問題也大。

Ⅱ 哈希值計算方法耗電量

摘要 哈希演算法（Hash 演算法，Hash 算式，散列演算法，消息摘要演算法）將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨後的哈希都將產生不同的值。

Ⅲ mysql水平分表的幾種方法

1.按時間分表

這種分表方式有一定的局限性，當數據有較強的實效性，如微博發送記錄、微信消息記錄等，這種數據很少有用戶會查詢幾個月前的數據，如就可以按月分表。

2.按區間范圍分表

一般在有嚴格的自增id需求上，如按照user_id水平分表：
table_1 user_id從1~100w
table_2 user_id從101~200w
table_3 user_id從201~300w
...

3.hash分表

通過一個原始目標的ID或者名稱通過一定的hash演算法計算出數據存儲表的表名，然後訪問相應的表。
按如下分10張表：

• functionget_hash_table($table,$userid)

• {

• $str=crc32($userid);

• if($str<0){

• $hash="0".substr(abs($str),0,1);

• }else{

• $hash=substr($str,0,2);

• }

• return$table."_".$hash;

• }

• echo get_hash_table('message','user18991');//結果為message_10

• echo get_hash_table('message','user34523');//結果為message_13

Ⅳ 什麼是哈希演算法

就是空間映射函數，例如，全體的長整數的取值作為一個取值空間，映射到全部的位元組整數的取值的空間，這個映射函數就是HASH函數。通常這種映射函數是從一個非常大的取值空間映射到一個非常小的取值空間，由於不是一對一的映射，HASH函數轉換後不可逆，即不可能通過逆操作和HASH值還原出原始的值，受到計算能力限制（注意，不是邏輯上不可能，前面的不可能是邏輯上的）而且也無法還原出所有可能的全部原始值。HASH函數運用在字典表等需要快速查找的數據結構中，他的計算復雜度幾乎是O(1)，不會隨著數據量增加而增加。另外一種用途就是文件簽名，文件內容很多，將文件內容通過HASH函數處理後得到一個HASH值，驗證這個文件是否被修改過，只需要把文件內容用同樣的HASH函數處理後得到HASH值再比對和文件一起傳送的HASH值即可，如不公開HASH演算法，那麼信道是無法篡改文件內容的時候篡改文件HASH值，一般應用的時候，HASH演算法是公開的，這時候會用一個非對稱加密演算法加密一下這個HASH值，這樣即便能夠計算HASH值，但沒有加密密鑰依然無法篡改加密後HASH值。這種演算法用途很廣泛，用在電子簽名中。HASH演算法也可進行破解，這種破解不是傳統意義上的解密，而是按照已有的HASH值構造出能夠計算出相同HASH值的其他原文，從而妨礙原文的不可篡改性的驗證，俗稱找碰撞。這種碰撞對現有的電子簽名危害並不嚴重，主要是要能夠構造出有意義的原文才有價值，否則就是構造了一個完全不可識別的原文罷了，接收系統要麼無法處理報錯，要麼人工處理的時候發現完全不可讀。理論上我們終於找到了在可計算時間內發現碰撞的演算法，推算了HASH演算法的逆操作的時間復雜度大概的范圍。HASH演算法的另外一個很廣泛的用途，就是很多程序員都會使用的在資料庫中保存用戶密碼的演算法，通常不會直接保存用戶密碼（這樣DBA就能看到用戶密碼啦，好危險啊），而是保存密碼的HASH值，驗證的時候，用相同的HASH函數計算用戶輸入的密碼得到計算HASH值然後比對資料庫中存儲的HASH值是否一致，從而完成驗證。由於用戶的密碼的一樣的可能性是很高的，防止DBA猜測用戶密碼，我們還會用一種俗稱「撒鹽」的過程，就是計算密碼的HASH值之前，把密碼和另外一個會比較發散的數據拼接，通常我們會用用戶創建時間的毫秒部分。這樣計算的HASH值不大會都是一樣的，會很發散。最後，作為一個老程序員，我會把用戶的HASH值保存好，然後把我自己密碼的HASH值保存到資料庫裡面，然後用我自己的密碼和其他用戶的用戶名去登錄，然後再改回來解決我看不到用戶密碼而又要「偷窺」用戶的需要。最大的好處是，資料庫泄露後，得到用戶資料庫的黑客看著一大堆HASH值會翻白眼。

Ⅳ 大家mysql 分表的哈希演算法是怎樣的

當一張的數據達到幾百萬時，你查詢一次所花的時間會變多，如果有聯合查詢的話，我想有可能會死在那兒了。分表的目的就在於此，減小資料庫的負擔，縮短查詢時間。
根據個人經驗，mysql執行一個sql的過程如下：
1,接收到sql;2,把sql放到排隊隊列中 ;3,執行sql;4,返回執行結果。在這個執行過程中最花時間在什麼地方呢？第一，是排隊等待的時間，第二，sql的執行時間。其實這二個是一回事，等待的同時，肯定有sql在執行。所以我們要縮短sql的執行時間。

Ⅵ Hash表及其應用

散列表，也叫做哈希表。

它基於數組的隨機訪問的特性，來拓展延伸，從而實現了散列表，為什麼這樣說呢，我們舉一個例子來看看。

假設學校舉行運動會，對100個進行編號，我們現在希望實現通過編號來快速找到某一個學生，該怎麼實現呢，我們可以維護一個數組，將每一個學生的編號放到同樣的數組下標內，比如1號放到數組下標為1的位置，接下來額以此類推，這樣就能夠實現快速隨機訪問，在O(1)的時間復雜度內就找到這個學生。

也許這樣你看不出用到了散列思想，但這確實就是使用了散列的思想，將數組下標和學生編號進行了映射，只不過映射規則非常簡單，就是f(n) = n。

但是現實時不會這么簡單的，現在要求編號要復雜一點，用 6 位數字來表示。比如 051167，其中，前兩位 05 表示年級，中間兩位 11 表示班級，最後兩位還是原來的編號 1 到 89。這個時候我們該如何存儲選手信息，才能夠支持通過編號來快速查找選手信息呢？

依然時通過散列的思想，我們可以截取編號的後兩位作為數組下標，存儲選手信息，當我們要查詢時，也截取後兩位作為數組下標，到數組內去查詢，這樣就能夠實現快速查詢。

其中，參賽選手的編號我們叫作鍵（key）或者關鍵字。我們用它來標識一個選手。我們把參賽編號轉化為數組下標的映射方法就叫作散列函數（或「Hash 函數」「哈希函數」），而散列函數計算得到的值就叫作散列值（或「Hash 值」「哈希值」）。拿上面那個來說，關鍵字是051167，我們通過hash函數，即截取後兩位，計算得到hash值67。

可以看到的是，hash函數是一個非常重要的東西，如何構造一個好的hash函數也是非常重要的，通過學習，我目前知道的是3點：

1：hash值是一個非負整數

2：如果key1==key2 hash(key1) == hash(key2)

3：如果key1!=key2 hash(key1) != hash(key2)

第一點很好理解，因為我們要維護成數組的下標，那麼負數和非整數都是不行的；第二點也好理解，如果兩個key相同，那麼經過同一個hash函數計算，他們得到的值也必須要一樣。第三點要好好理解一下，不同的key得到的hash值不一樣，也就是這一點，引出了hash沖突這樣一個概念。

因為即使最好的hash演算法，也無法保證兩個不一樣的key得到的hash值一定不一樣。

計既然無法解決，那麼就要找其他的方法了。

經典的方法有鏈表法和開放定址法。

開放定址法：

這個比較好理解，就是如果計算得到的hash值在數組內已經有數據了，那我們就在緊接下一個尋找，如果沒有數據，就插入到這個位置，這種方法不是非常好。

為了保證散列表的性能，我們會維護一個 裝載因子 的概念。

裝載因子： 填入表中的元素個數 / 散列表的長度

裝載因子越小，發生散列沖突的概率就越小，性能就越好，如果裝載因子越大，那麼性能就會迅速下降，不過裝載因子越小，那麼需要消耗的內存就越大，如果不考慮性能，裝載因子可以超越1.

鏈表法：

鏈表法比較常用

介紹了散列表的基本概念和一些散列沖突的解決方法，拿我們來看看究竟怎麼樣，才能設計一個優秀的企業級的散列表呢？

設計散列表，最關鍵的就是散列函數的設計，一個好的散列函數，既能夠快速計算，也能夠讓散列沖突的概率較為小。既然要計算快速，那麼這個散列函數就必然不能夠太復雜，不然計算時間就較為耗時，其次也要保證計算出來的hash值要平均分布，否則一個槽出現的概率非常大，那麼散列沖突的概率就大大提升。

我們之前說過，hash函數是有一個裝載因子的概念的，對於動態的散列表，我們不斷進行插入操作，它的裝載因子勢必會擴大，當裝載因子過大時，hash表的性能就會下降，這個時候，就需要對hash表進行擴容，這樣裝載因子就會下降，對於數組的擴容，我們都可以很好的實現，不過對於散列表的擴容，就不是簡單的移動數據這么簡單了。

可以看到，當我們新建了一個數組後，原來hash表中的內容就要重新計算hash值，然後存放到新的哈市、表中，並不是簡單的移動就能解決的。

不過，這樣擴容，如果數據量很大，那麼效率就必然很低下，怎麼解決呢，我們可以不立刻拷貝數據到新的hash表裡面，可以每新插入一個數據就將老的表裡面的數據拿一個到新的表裡面，這樣就可以不一次性拷貝數據，效率就會得到提升。

接下啦看如何選擇合適的hash沖突解決法：

當數據量比較小、裝載因子小的時候，適合採用開放定址法。這也是 Java 中的ThreadLocalMap使用開放定址法解決散列沖突的原因。

基於鏈表的散列沖突處理方法比較適合存儲大對象、大數據量的散列表，而且，比起開放定址法，它更加靈活，支持更多的優化策略，比如用紅黑樹代替鏈表。

    this.hash = var1;

  }

  return var1;

}

Ⅶ PHP mysql 實現hash分區的問題

當分片索引不是純整型的字元串時，只接受整型的內置 hash 演算法是無法使用的。為此，stringhash 按照用戶定義的起點和終點去截取分片索引欄位中的部分字元，根據當中每個字元的二進制 unicode 值換算出一個長整型數值，然後就直接調用內置 hash 演算法求解分片路由：先求模得到邏輯分片號，再根據邏輯分片號直接映射到物理分片。

• 用戶需要在 rule.xml 中定義 partitionLength[] 和 partitionCount[] 兩個數組和 hashSlice 二元組。

• 在 DBLE 的啟動階段，點乘兩個數組得到模數，也是邏輯分片的數量

• 並且根據兩個數組的叉乘，得到各個邏輯分片到物理分片的映射表（物理分片數量由 partitionCount[] 數組的元素值之和）

• 此外根據 hashSlice 二元組，約定把分片索引值中的第 4 字元到第 5 字元（字元串以 0 開始編號，編號 3 到編號 4 等於第 4 字元到第 5 字元）字元串用於 「字元串->整型」的轉換

• 在 DBLE 的運行過程中，用戶訪問使用這個演算法的表時，WHERE 子句中的分片索引值會被提取出來，取當中的第 4 個字元到第 5 字元，送入下一步

• 設置一個初始值為 0 的累計值，逐個取字元，把累計值乘以 31，再把這個字元的 unicode 值當成長整型加入到累計值中，如此類推直至處理完截取出來的所有字元，此時的累計值就能夠代表用戶的分片索引值，完成了 「字元串->整型」 的轉換

• 對上一步的累計值進行求模，得到邏輯分片號

• 再根據邏輯分片號，查映射表，直接得到物理分片號

與MyCat的類似分片演算法對比

兩種演算法在string轉化為int之後，和 hash 分區演算法相同，區別也繼承了 hash 演算法的區別。

開發注意點

【分片索引】1. 必須是字元串

【分片索引】2. 最大物理分片配置方法是，讓 partitionCount[] 數組和等於 2880

例如：

• <property name="partitionLength">1</property><property name="partitionCount">2880</property>



或

• <property name="partitionLength">1,1</property><property name="partitionCount">1440,1440</property>



【分片索引】3. 最小物理分片配置方法是，讓 partitionCount[] 數組和等於 1

例如

• <property name="partitionLength">2880</property><property name="partitionCount">1</property>



【分片索引】4. partitionLength 和 partitionCount 被當做兩個逗號分隔的一維數組，它們之間的點乘必須在 [1, 2880] 范圍內

【分片索引】5. partitionLength 和 partitionCount 的配置對順序敏感

• <property name="partitionLength">512,256</property><property name="partitionCount">1,2</property>



和

• <property name="partitionLength">256,512</property><property name="partitionCount">2,1</property>



是不同的分片結果

【分片索引】6. 分片索引欄位長度小於用戶指定的截取長度時，截取長度會安全減少到符合分片索引欄位長度

【數據分布】1. 分片索引欄位截取越長則越有利於數據均勻分布

【數據分布】2. 分片索引欄位的內容重復率越低則越有利於數據均勻分布

運維注意點

【擴容】1. 預先過量分片，並且不改變 partitionCount 和 partitionLength 點乘結果，也不改變截取設置 hashSlice 時，可以避免數據再平衡，只需進行涉及數據的遷移

【擴容】2. 若需要改變 partitionCount 和 partitionLength 點乘結果或改變截取設置 hashSlice 時，需要數據再平衡

【縮容】1. 預先過量分片，並且不改變 partitionCount 和 partitionLength 點乘結果，也不改變截取設置 hashSlice 時，可以避免數據再平衡，只需進行涉及數據的遷移

【縮容】2. 若需要改變 partitionCount 和 partitionLength 點乘結果或改變截取設置 hashSlice 時，需要數據再平衡

配置注意點

【配置項】1. 在 rule.xml 中，可配置項為<property name="partitionLength"> 、<property name="partitionCount"> 和 <property name="hashSlice">

【配置項】2.在 rule.xml 中配置 <property name="partitionLength">標簽

內容形式為：<物理分片持有的虛擬分片數>[,<物理分片持有的虛擬分片數>,...<物理分片持有的虛擬分片數>]

物理分片持有的虛擬分片數必須是整型，物理分片持有的虛擬分片數從左到右與同順序的物理分片數對應，partitionLength 和partitionCount 的點乘結果必須在 [1, 2880] 范圍內

【配置項】3. 在 rule.xml 中配置 <property name="partitionCount">標簽
內容形式為：<物理分片數>[,<物理分片數>,...<物理分片數>]

其中物理分片數必須是整型，物理分片數按從左到右的順序與同順序的物理分片持有的虛擬分片數對應，物理分片的編號從左到右連續遞進，partitionLength 和 partitionCount 的點乘結果必須在 [1, 2880] 范圍內

【配置項】4. partitionLength 和 partitionCount 的語義是：持有partitionLength[i] 個虛擬分片的物理分片有 partitionCount[i] 個

例如

• <property name="partitionLength">512,256</property><property name="partitionCount">1,2</property>



語義是持有 512 個邏輯分片的物理分片有 1 個，緊隨其後，持有 256 個邏輯分片的物理分片有 2 個

【配置項】5.partitionLength 和 partitionCount 都對書寫順序敏感，

例如

• <property name="partitionLength">512,256</property><property name="partitionCount">1,2</property>



分片結果是第一個物理分片持有頭512個邏輯分片，第二個物理分片持有緊接著的256個邏輯分片，第三個物理分片持有最後256個邏輯分片，相對的

• <property name="partitionLength">256,512</property><property name="partitionCount">2,1</property>



分片結果則是第一個物理分片持有頭 256 個邏輯分片，第二個物理分片持有緊接著的 256 個邏輯分片，第三個物理分片持有最後 512 個邏輯分片

【配置項】6.partitionLength[] 的元素全部為 1 時，這時候partitionCount 數組和等於 partitionLength 和 partitionCount 的點乘，物理分片和邏輯分片就會一一對應，該分片演算法等效於直接取余

【配置項】7.在 rule.xml 中配置標簽，從分片索引欄位的第幾個字元開始截取到第幾個字元：

• 若希望從首字元開始截取 k 個字元（ k 為正整數），配置的內容形式可以為「 0 : k 」、「 k 」或「 : k 」；

• 若希望從末字元開始截取 k 個字元（ k 為正整數），則配置的內容形式可以為「 -k : 0 」、「 -k 」或「 -k : 」；

• 若希望從頭第 m 個字元起算截取 n 個字元（ m 和 n 都是正整數），則先計算出 i = m - 1 和 j = i + n - 1，配置的內容形式為「 i : j 」；

• 若希望從尾第 m 個字元起算截取從尾算起的 n 個字元（ m 和 n 都是正整數），則先計算出 i = -m + n - 1，配置的內容形式可以為「 -m : i 」；

• 若希望不截取，則配置的內容形式可以為「 0 : 0 」、「 0 : 」、「 : 0 」或 「 : 」