Hash求index的问题

Question

今天看了一篇关于Hash的文章有如下疑问
疑问1、
是一个问题
文章给出的也是hash
比如从“one  day i will success”中查找 will 
最简单的做法就是用split分割字符串 比较 如果用hash的话也得一个个单词遍历，求Index 这样效率会高吗？
问题2、我昨天发的一个帖子 一道面试题，希望各位能给我出最优解
http://bbs.csdn.net/topics/390277569
还有，我现在打算学hadoop 谁能给个学习路线。或者一个比较好的教程。能给我一个去公司实习的机会更好
    

Answer 1

我来讲讲我的想法，不一定对。【问题一】
假设字串的规模是n个字串，每个字串平均长度是m，那么hash和Trie树均为：预处理时间O(nm)，查找每个字串时间O(m)二者效率接近，但是Trie树不用考虑解决地址冲突，编程复杂度较小。【问题二】
这个问题最好的做法是并查集，时间复杂度是O(mα(n,m))，相当于O(m)。实现如下（屏幕输入输出）：class Element{

private Element father = this;

Element(){
}

Element getFather(){
if (father == this) return this; 
father = father.getFather();
return father;
}

void setFather(Element father_){
father = father_;
}

}public class UnionSet {

private Element[] elements;
private int parts;

public UnionSet(){
}

public UnionSet(int n){
parts = n;
elements = new Element[n];
for (int i = 0; i< n; i++)
elements[i] = new Element();
}

public boolean isInCommon(int index_1, int index_2){

return elements[index_1].getFather() == elements[index_2].getFather();

}

public void union(int index_1, int index_2){

if (!isInCommon(index_1, index_2)){
parts--;
elements[index_1].setFather(elements[index_2]);
}

}

public int getParts(){
return parts;
}

}
import java.util.Scanner;public class TestUnionSet {

public static void main(String[] args){

Scanner read = new Scanner(System.in);

int n = read.nextInt();
int m = read.nextInt();

UnionSet Friends = new UnionSet(n);

for (int i = 0; i < m; i++){
int x = read.nextInt();
int y = read.nextInt();
Friends.union(x-1, y-1);
}

System.out.println(Friends.getParts());

read.close();

}
}