哈希算法的实现

浅浅的花香味﹌ 2022-07-12 05:26 170阅读 0赞

在我们开发的过程中，我们发现处处都会有hash。java中，Object有hash值，有hashtable，有hashmap。在我们的分布式集群中，一致性哈希一直也是个热门的词。那么，一致性hash到底是什么呢？

网上的博文很多，但是总觉得那么抽象。我想，我需要简化它的呈现形式。

首先，我们还是来复习以下hash算法吧。

我建一个类来模拟hash，其中采用%13的取法去取hash值。对于冲突，采用了简单的线性开放寻址法。

package yyf.Algorithm.hash;
    
    public class HashUtil {
    	private static int HASHSIZE = 20;
    
    	// 建立长度为100的散列表
    	private static String[] arr = new String[HASHSIZE];
    
    	public static void insert(String str) {
    		int sum = 0;
    		for (int i = 0; i < str.length(); i++) {
    			sum += str.charAt(i) + i;
    		}
    		int index = sum % 13;
    
    		// 发生冲突 线性寻址法
    		while (true) {
    			if (index >= HASHSIZE) {
    				System.err.println("插入失败：" + str);
    			}
    			if (arr[index] == null) {
    				arr[index] = str;
    				break;
    			} else {
    				index++;
    			}
    
    		}
    
    	}
    
    	public static int find(String str) {
    		int sum = 0;
    		for (int i = 0; i < str.length(); i++) {
    			sum += str.charAt(i) + i;
    		}
    		int index = sum % 13;
    		// 发生冲突 线性寻址法
    		while (true) {
    			if (index >= HASHSIZE) {
    				System.err.println("没有数据：" + str);
    				return 404;
    			}
    			if (str.equals(arr[index])) {
    				return index;
    			} else {
    				index++;
    			}
    
    		}
    
    	}
    }

我们来测试以下吧，

在其中用main来直接使用这个类，

public static void main(String[] args) {
    		insert("ab5");
    		insert("abc");
    		insert("qew");
    		insert("oiu");
    		insert("dad7");
    
    		for (int i = 0; i < arr.length; i++) {
    			System.out.println("[" + i + "]=" + arr[i]);
    		}
    
    		String sv = "ab5";
    		System.out.println(sv + "位置：" + find(sv));
    
    		sv = "oiu";
    		System.out.println(sv + "位置：" + find(sv));
    		
    		sv = "hah";
    		System.out.println(sv + "位置：" + find(sv));
    
    	}

存取5个字符串在hash表中，

[0]=null
    [1]=null
    [2]=null
    [3]=null
    [4]=ab5
    [5]=null
    [6]=null
    [7]=dad7
    [8]=null
    [9]=null
    [10]=null
    [11]=abc
    [12]=qew
    [13]=oiu
    [14]=null
    [15]=null
    [16]=null
    [17]=null
    [18]=null
    [19]=null

可以看到，5个字符串已经存入hash表，然后呢，查找测试：

ab5位置：4
    oiu位置：13
    hah位置：404
    没有数据：hah

按这中查找，从代码逻辑上来说速度是非常快的。

我想，如果大家都能明白以上代码的内容，对于hash的理解已经入门了。

然后呢，我们是不是该了解以下一致性hash了？

我看了网上很多大牛的博文，基本都如下：

[http://blog.csdn.net/sparkliang/article/details/5279393][http_blog.csdn.net_sparkliang_article_details_5279393]

[http://m.blog.csdn.net/article/details?id=50301123][http_m.blog.csdn.net_article_details_id_50301123]

[http_blog.csdn.net_sparkliang_article_details_5279393]: http://blog.csdn.net/sparkliang/article/details/5279393
[http_m.blog.csdn.net_article_details_id_50301123]: http://m.blog.csdn.net/article/details?id=50301123