开发学院软件开发Java 集合类库(四):杂谈HashSet 阅读

集合类库(四):杂谈HashSet

 2009-09-18 00:00:00 来源:WEB开发网   
核心提示:(1) 为啥要用HahSet?假如我们现在想要在一大堆数据中查找X数据,LinkedList的数据结构就不说了,集合类库(四):杂谈HashSet,查找效率低的可怕,ArrayList哪,他并不是线性结构的集合,3、hashCode必须和equals必须兼容,如果我们不知道X的位置序号,还是一样要全部遍历一次直到查到结

(1) 为啥要用HahSet?

假如我们现在想要在一大堆数据中查找X数据。LinkedList的数据结构就不说了,查找效率低的可怕。ArrayList哪,如果我们不知道X的位置序号,还是一样要全部遍历一次直到查到结果,效率一样可怕。HashSet天生就是为了提高查找效率的。

(2) hashCode 散列码

散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。基本上,每一个对象都有一个默认的散列码,其值就是对象的内存地址。但也有一些对象的散列码不同,比如String对象,它的散列码是对内容的计算结果:

Java代码   

//String对象的散列码计算 
String str="hello"; 
int hash=0; 
for(int i=0;i<length();i++) 
  hash=31*hash+charAt(i);

那么下面散列码的结果不同也就好解释了。s和t都还是String对象,散列码由内容获得,结果一样。sb和tb是StringBuffer对象,自身没有hashCode方法,只能继承Object的默认方法,散列码是对象地址,当然不一样了。

Java代码   

String s=new String("OK");//散列码: 3030 
String t="Ok"; /散列码: 3030 
StringBuffer sb=new StringBuffer(s); //散列码:20526976 
StringBuffer tb=new StringBuffer(t); //散列码:20527144

(3)  HashSet 散列表的内部结构

HashSet是个链表数组。每一个数组元素就是一个列表,我们称为散列表元 。

集合类库(四):杂谈HashSet                    

(4) HashSet 如何add机制

假如我们有一个数据(散列码76268),而此时的HashSet有128个散列单元,那么这个数据将有可能插入到数组的第108个链表中 (76268%128=108)。但这只是有可能,如果在第108号链表中发现有一个老数据与新数据equals()=true的话,这个新数据将被视为已经加入,而不再重复丢入链表。

那么数据的散列码我知道,但HashSet的散列单元大小如何指定那?

Java默认的散列单元大小全部都是2的幂,初始值为16(2的4次幂)。假如16条链表中的75%链接有数据的时候,则认为加载因子达到默认的 0.75。HahSet开始重新散列,也就是将原来的散列结构全部抛弃,重新开辟一个散列单元大小为32(2的5次幂)的散列结果,并重新计算各个数据的存储位置。以此类推下去.....

(5) 为什么HashSet查找效率提高了。

知道了HashSet的add机制后,查找的道理一样。直接根据数据的散列码和散列表的数组大小计算除余后,就得到了所在数组的位置,然后再查找链表中是否有这个数据即可。

查找的代价也就是在链表中,但是真正一条链表中的数据很少,有的甚至没有。几乎没有什么迭代的代价可言了。所以散列表的查找效率建立在散列单元所指向的链表中的数据要少 。

(6) hashCode方法必须与equals方法必须兼容

如果我们自己定义了一个类,想对这个类的大量对象组织成散列表结构便于查找。有一点一定要注意:就是hashCode方法必须与equals方法向兼容。

Java代码   

//hashCode与equals方法的兼容 
public class Employee{ 
    public int id; 
    public String name=""; 
    //相同id对象具有相同散列码 
    public int hashCode(){ 
       return id; 
    } 
    //equals必须比较id 
    public boolean equals(Employee x){ 
       if(this.id==x.id) return true; 
       else return false; 
    } 
}

     为什么要这样,因为HashSet不允许相同元素(equals==ture)同时存在在结构中。假如employeeX(1111,“张三”)和 employee(1111,"李四"),而Employee.equals比较的是name。这样的话,employeeX和employeeY的 equals不相等。它们会根据相同的散列码1111加入到同一个散列单元所指向的列表中。这种情况多了,链表的数据将很庞大,散列冲突将非常严重,查找效率会大幅度的降低。

(6) 总结一下

1、HashSet不能重复存储equals相同的数据 。原因就是equals相同,数据的散列码也就相同(hashCode必须和equals兼容)。大量相同的数据将存放在同一个散列单元所指向的链表中,造成严重的散列冲突,对查找效率是灾难性的。

2、HashSet的存储是无序的 ,没有前后关系,他并不是线性结构的集合。

3、hashCode必须和equals必须兼容, 这也是为了第1点。

Tags:集合 杂谈 HashSet

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接