哈希算法检索字符串

先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？

有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止。

 

代码如下：

public class hash {

	public  static  boolean equals(String str1,String str2){
		int length1 = str1.length();
		int length2 = str2.length();
		if(length1 != length2){
			return false;
		}else{
			for(int i = 0;i < length1;i++){
				if(str1.charAt(i)!=str2.charAt(i)){
					return false;
				}
			}
		}
		 return true;
       }  
  
	public static void main(String[] args) {
		String[] data = {"hello","love","good","eat","eye"};

		//查找good
		String s = "good";
		for(String str:data){
			if(equals(s,str)){
				System.out.println("存在:"+s);
			}
		}
	}
}

 这个算法复杂程度为：词库单词个数 m*比较单词时间n。如果词库中有一半与要检索的词长度一样。那么比较单词的时间n就是要检索的的词长度*m/2

整个程序时间就是 (要检索的的词长度*m*m)/2

 

也可以利用哈希算法来检索

 

代码如下：

public class hash {
	//哈希函数  
    public static int Hash(int key){  
        return key%5;  
    }  
    
	public static int HashCode(char[] str,int len){
		int h = 0;
		for (int i = 0; i < len; i++) {  
			h = h* 33 + str[i];
        }  
        return h;  
       }  
  
	public static void main(String[] args) {
		String[] data = {"hello","love","good","eat","eye"};
		String[] hashtable = new String[5];
		int i = 0;
		for(String s:data){
			int code = HashCode(s.toCharArray(),s.length());
			hashtable[Hash(code)] = s;
		}
		//查找good
		String var = "good";
		int code = HashCode(var.toCharArray(),var.length());
		if(hashtable[Hash(code)]!=null){
			System.out.println("存在:"+var);
		}
	}
}

 这个算法复杂程度：词库单词个数m*词库单词平均长度n

 

当词库非常大时，相对于之前的算法，效率有很大的提高。