① 桶排序與哈希桶排序
桶排序 (箱排序)的原理是將待排序序列分到有限數量的桶裡面,然後對每個桶再分別排序(帆禪咐可以使用其它的排序演算法或者是遞歸使用桶排序演算法),最後將各個桶中的數據有序的合並起來成為一個整體有序的序列。
排序過程:
1.假設待排序的一組數統一的分布在一個范圍中,並將這一范圍劃分成幾個子范圍,也就是桶
2.將待排序的一組數,分檔規入這些子桶,並將桶中的數據進行排序
3.將各個桶中的數據有序的合並起來
設有數組 array = [29, 25, 3, 49, 9, 37, 21, 43],那麼數組中最大數為 49,先設置 5 個桶,那麼每個桶可存放數的范圍為:09、1019、2029、3039、40~49,然後分別將這些數放人自己所屬的桶,如下圖:
1.時間復雜度:O(m+n)
2.空間復雜度:O(m+n)
適用於序列比較均勻的情況,否則會很耗空間。
或者特殊的場景,例如需要對一個公司的員工的年齡進行排序,年齡的范圍為1-120,此時就可以開辟120個桶進行統計排序。
另,桶排序的瓶頸主要是桶數量的選擇。
另此演算法為穩定的排序演算法。
排序演算法主要是用分治法,用哈希函數對序列進行劃分,最後使用其它的排序演算法或者遞歸使用哈希排序進行排序從而得到一個整體有序的序列。下面先介紹幾個自定義的概念:
1.哈希桶排序:因為本演算法是使用了哈希函數把序列劃分到對應的桶裡面,所以本排序演算法取名為哈希桶排序。
2.哈希桶因子(hashFactor):hashFactor = (max - min) / length
計算公式如上式,當結果小於等於0的時候再做特殊處理,據此因子進行桶的劃分。
設有數組 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1],那麼數組中最大值max = 10011,最小值min = 1,哈希桶因子hashFactor = (10011 - 1) / 10 = 1001。對數組進行劃分,10011 / 1001 = 10,所以10011放在keywei10的桶裡面;10001 / 1001 = 9, 所以10001放在key為9的桶裡面,以此類推,最後得到的桶態純的情況為:{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分別對每個桶進行排序即可。
1.時間復雜度:O(m+n)
2.空間復雜度:O(m+n)
此演算法與桶排序對比,主要是通過哈希建桶的方式減少了空間的消耗,對序列進行了一個歸約襲伍,時間上跟桶排序相當。
使用與序列的最小最大值相差比較大同時又出現在某一個取值區間的集聚的情況。
另此演算法為穩定的排序演算法。
② 大數據最常用的演算法有哪些
奧地利符號計算研究所(Research Institute for Symbolic Computation,簡稱RISC)的Christoph Koutschan博士在自己的頁面上發布了一篇文章,提到他做了一個調查,參與者大多數是計算機科學家,他請這些科學家投票選出最重要的演算法,以下是這次調查的結果,按照英文名稱字母順序排序。
大數據等最核心的關鍵技術:32個演算法
1、A* 搜索演算法——圖形搜索演算法,從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算,為每個節點估算通過該節點的最佳路徑,並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此,A*搜索演算法是最佳優先搜索的範例。
2、集束搜索(又名定向搜索,Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過,集束搜索只能在每個深度中發現最前面的m個最符合條件的節點,m是固定數字——集束的寬度。
3、二分查找(Binary Search)——在線性數組中找特定值的演算法,每個步驟去掉一半不符合要求的數據。
4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法,特別是針對離散、組合的最優化。
5、Buchberger演算法——一種數學演算法,可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。
6、數據壓縮——採取特定編碼方案,使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程,又叫來源編碼。
7、Diffie-Hellman密鑰交換演算法——一種加密協議,允許雙方在事先不了解對方的情況下,在不安全的通信信道中,共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起,加密後續通訊。
8、Dijkstra演算法——針對沒有負值權重邊的有向圖,計算其中的單一起點最短演算法。
9、離散微分演算法(Discrete differentiation)。
10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法
11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的最大公約數。最古老的演算法之一,出現在公元前300前歐幾里得的《幾何原本》。
12、期望-最大演算法(Expectation-maximization algorithm,又名EM-Training)——在統計計算中,期望-最大演算法在概率模型中尋找可能性最大的參數估算值,其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算,第一步是計算期望,利用對隱藏變數的現有估計值,計算其最大可能估計值;第二步是最大化,最大化在第一步上求得的最大可能值來計算參數的值。
13、快速傅里葉變換(Fast Fourier transform,FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣,從數字信號處理到解決偏微分方程,到快速計算大整數乘積。
14、梯度下降(Gradient descent)——一種數學上的最優化演算法。
15、哈希演算法(Hashing)。
16、堆排序(Heaps)。
17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用,比如計算機代數系統和大數程序庫,如果使用長乘法,速度太慢。該演算法發現於1962年。
18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入,輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用:背包加密系統(knapsack)、有特定設置的RSA加密等等。
19、最大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關,這就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的最大流。
20、合並排序(Merge Sort)。
21、牛頓法(Newton』s method)——求非線性方程(組)零點的一種重要的迭代法。
22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法,函數採取在給定狀態的給定動作,並計算出期望的效用價值,在此後遵循固定的策略。Q-leanring的優勢是,在不需要環境模型的情況下,可以對比可採納行動的期望效用。
23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法,在實踐中,是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數,它仍是最快的,而且都認為它比數域篩法更簡單。
24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據,數據中包含異常值,估算一個數學模型的參數值。其基本假設是:數據包含非異化值,也就是能夠通過某些模型參數解釋的值,異化值就是那些不符合模型的數據點。
25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用,大家也相信它有足夠安全長度的公鑰。
26、Sch?nhage-Strassen演算法——在數學中,Sch?nhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為:O(N log(N) log(log(N))),該演算法使用了傅里葉變換。
27、單純型演算法(Simplex Algorithm)——在數學的優化理論中,單純型演算法是常用的技術,用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組,以及一個等待最大化(或最小化)的固定線性函數。
28、奇異值分解(Singular value decomposition,簡稱SVD)——在線性代數中,SVD是重要的實數或復數矩陣的分解方法,在信號處理和統計中有多種應用,比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。
29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題,它們有很多應用,比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組,可以使用高斯—約當消去法(Gauss-Jordan elimination),或是柯列斯基分解( Cholesky decomposition)。
30、Strukturtensor演算法——應用於模式識別領域,為所有像素找出一種計算方法,看看該像素是否處於同質區域( homogenous region),看看它是否屬於邊緣,還是是一個頂點。
31、合並查找演算法(Union-find)——給定一組元素,該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作:
查找:判斷某特定元素屬於哪個組。
合並:聯合或合並兩個組為一個組。
32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法,這種序列被稱為維特比路徑,其結果是一系列可以觀察到的事件,特別是在隱藏的Markov模型中。
以上就是Christoph博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?
③ 哈希加密演算法
MD5即Message-Digest Algorithm 5(信息摘要演算法5),是計算機廣泛使用的散列演算法之一。經MD2、MD3和MD4發展而來,誕生於20世紀90年代初。用於確保信息傳輸完整一致。雖然已被破解,但仍然具有較好的安全性,加之可以免費使用,所以仍廣泛運用於數字簽名、文件完整性驗證以及口令加密等領域。
演算法原理:
散列演算法得到的結果位數是有限的,比如MD5演算法計算出的結果字長為128位,意味著只要我們窮舉2^128次,就肯定能得到一組碰撞,下面讓我們來看看一個真實的碰撞案例。我們之所以說MD5過時,是因為它在某些時候已經很難表現出散列演算法的某些優勢——比如在應對文件的微小修改時,散列演算法得到的指紋結果應當有顯著的不同,而下面的程序說明了MD5並不能實現這一點。
而諸如此類的碰撞案例還有很多,上面只是原始文件相對較小的一個例子。事實上現在我們用智能手機只要數秒就能找到MD5的一個碰撞案例,因此,MD5在數年前就已經不被推薦作為應用中的散列演算法方案,取代它的是SHA家族演算法,也就是安全散列演算法(Secure Hash Algorithm,縮寫為SHA)。
SHA實際包括有一系列演算法,分別是SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。而我們所說的SHA2實際是對後面4中的統稱。各種SHA演算法的數據比較如下表,其中的長度單位均為位:
MD5和SHA1,它們都有4個邏輯函數,而在SHA2的一系列演算法中都採用了6個邏輯函數。
以SHA-1為例,演算法包括有如下的處理過程:
和MD5處理輸入方式相同
經過添加位數處理的明文,其長度正好為512位的整數倍,然後按512位的長度進行分組,可以得到一定數量的明文分組,我們用Y 0 ,Y 1 ,……Y N-1 表示這些明文分組。對於每一個明文分組,都要重復反復的處理,這些與MD5都是相同的。
而對於每個512位的明文分組,SHA1將其再分成16份更小的明文分組,稱為子明文分組,每個子明文分組為32位,我們且使用M[t](t= 0, 1,……15)來表示這16個子明文分組。然後需要將這16個子明文分組擴充到80個子明文分組,我們將其記為W[t](t= 0, 1,……79),擴充的具體方法是:當0≤t≤15時,Wt = Mt;當16≤t≤79時,Wt = ( W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16 ) <<< 1,從而得到80個子明文分組。
所謂初始化緩存就是為鏈接變數賦初值。前面我們實現MD5演算法時,說過由於摘要是128位,以32位為計算單位,所以需要4個鏈接變數。同樣SHA-1採用160位的信息摘要,也以32位為計算長度,就需要5個鏈接變數。我們記為A、B、C、D、E。其初始賦值分別為:A = 0x67452301、B = 0xEFCDAB89、C = 0x98BADCFE、D = 0x10325476、E = 0xC3D2E1F0。
如果我們對比前面說過的MD5演算法就會發現,前4個鏈接變數的初始值是一樣的,因為它們本來就是同源的。
經過前面的准備,接下來就是計算信息摘要了。SHA1有4輪運算,每一輪包括20個步驟,一共80步,最終產生160位的信息摘要,這160位的摘要存放在5個32位的鏈接變數中。
在SHA1的4論運算中,雖然進行的就具體操作函數不同,但邏輯過程卻是一致的。首先,定義5個變數,假設為H0、H1、H2、H3、H4,對其分別進行如下操作:
(A)、將A左移5為與 函數的結果求和,再與對應的子明文分組、E以及計算常數求和後的結果賦予H0。
(B)、將A的值賦予H1。
(C)、將B左移30位,並賦予H2。
(D)、將C的值賦予H3。
(E)、將D的值賦予H4。
(F)、最後將H0、H1、H2、H3、H4的值分別賦予A、B、C、D
這一過程表示如下:
而在4輪80步的計算中使用到的函數和固定常數如下表所示:
經過4輪80步計算後得到的結果,再與各鏈接變數的初始值求和,就得到了我們最終的信息摘要。而對於有多個明文分組的,則將前面所得到的結果作為初始值進行下一明文分組的計算,最終計算全部的明文分組就得到了最終的結果。
④ 一致性hash演算法,採用哪種演算法實現比較好,比如MD5,CRC32,或者其它
環割法(一致性 hash)環割法的原理如下:
1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字元串,例如 SHARD-1-NODE-1,並計算所有 X×N 個字元串的所有 hash 值。
2. 將所有計算出來的 hash 值放到一個排序的 Map 中,並將其中的所有元素進行排序。
3. 輸入字元串的時候計算輸入字元串的 hash 值,查看 hash 值介於哪兩個元素之間,取小於 hash 值的那個元素對應的分片為數據的分片。
數據比較
下面將通過測試對環割法和跳躍法的性能及均衡性進行對比,說明 DBLE 為何使用跳躍法代替了環割法。
數據源:現場數據 350595 條
測試經過:
1. 通過各自的測試方法執行對於測試數據的分片任務。
2. 測試方法:記錄分片結果的方差;記錄從開始分片至分片結束的時間;記錄分片結果與平均數的最大差值。
3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數,所以測試過程只能使用 2 的指數形式進行測試,並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷,取全量長度進行測試。
⑤ 常見的哈希演算法有哪些
1.linear hash 線性
2.quadratic hash 每次以1,4,9,16這樣的幅度向下找
3.double hash 用兩個函數一起決定HASH的index
⑥ 哈希表與哈希(Hash)演算法
根據設定的 哈希函數H(key) 和 處理沖突的方法 將一組關鍵字影像到一個有限的連續的地址集(區間)上,並以關鍵字在地址集中的「像」作為記錄在表中的存儲位置,這種表便成為 哈希表 ,這一映像過程稱為哈希造表或 散列 ,所得存儲位置稱 哈希地址 或 散列地址 。
上面所提到的 哈希函數 是指:有一個對應關系 f ,使得每個關鍵字和結構中一個唯一的存儲位置相對應,這樣在查找時,我們不需要像傳統的爛碼查找演算法那樣進行比較,而是根據這個對應關系 f 找到給定值K的像 f(K) 。
哈希函數也可叫哈希演算法,它可以用於檢驗信息是否相同( 文件校驗 ),或兆歷褲者檢驗信息的擁有者是否真實( 數字簽名 )。
下面分別就哈希函數和族簡處理沖突的方法進行討論;
構造哈希函數的方法有很多。在介紹各種方法前,首先需要明確什麼是「好」 的哈希演算法。若對於關鍵字集合中的任一個關鍵字,經哈希函數映像到地址集合中任何一個地址的概率是相等的,則稱此類哈希函數是 均勻的 (Uniform)哈希函數。換句話說,就是使關鍵字經過哈希函數得到一個「隨機的地址」,以便使一組關鍵字的哈希地址均勻分布在整個地址區間中,從而減少沖突。
常用的構造哈希函數的方法有:
理論研究表明, 除留余數法的模 p 取不大於表長且最接近表長 m 的素數效果最好,且 p 最好取1.1 n ~ 1.7 n 之間的一個素數(n為存在的數據元素個數) 。
以上便是常用的6種構造哈希函數的方法,實際工作中需視不同的情況採用採用不同的哈希函數,通常考慮的因素有:
前面有提到過 均勻的哈希函數可以減少沖突,但不能避免 ,因此,如何處理沖突是哈希造表不可缺少的另一方面。
通常用的處理沖突的方法有下列幾種:
在哈希表上進行查找的過程和哈希建表的過程基本一致。 給定K值,根據建表時設定的哈希函數求得哈希地址,若表中此位置上沒有記錄,則查找不成功;否則比較關鍵字,若和給定值相等,則查找成功;否則根據造表時設定的處理沖突的方案找「下一地址」 ,直到找到為止。