Go语言视频零基础入门到精通

javalearner

(1) 为啥要用HahSet?
     假如我们现在想要在一大堆数据中查找X数据。LinkedList的数据结构就不说了，查找效率低的可怕。ArrayList哪，如果我们不知道X的位置序号，还是一样要全部遍历一次直到查到结果，效率一样可怕。HashSet天生就是为了提高查找效率的。 (2) hashCode 散列码
     散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。基本上，每一个对象都有一个默认的散列码，其值就是对象的内存地址。但也有一些对象的散列码不同，比如String对象，它的散列码是对内容的计算结果：

//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的默认方法，散列码是对象地址，当然不一样了。

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







(3) 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方法向兼容。

1. //hashCode与equals方法的兼容   
   
2. public class Employee{   
   
3.        public int id;   
   
4.        public String name="";   
   
5.        //相同id对象具有相同散列码   
   
6.        public int hashCode(){   
   
7.               return id;   
   
8.        }   
   
9.        //equals必须比较id   
   
10.         public boolean equals(Employee x){   
    
11.               if(this.id==x.id) return true;   
    
12.               else return false;   
    
13.        }   
    
14. }  
    

复制代码

     为什么要这样，因为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点。 附：

1. import java.util.HashSet;   
   
2. import java.util.Iterator;   
   
3.   
   
4. public class IteratorTest {   
   
5.     public static void main(String[] args) {   
   
6.         HashSet set = new HashSet();   
   
7.         set.add("a");   
   
8.         set.add("b");   
   
9.         set.add("c");   
   
10.         set.add("d");   
    
11.         set.add("e");   
    
12.         Iterator iter = set.iterator();   
    
13.         while(iter.hasNext()){   
    
14.             String value = (String)iter.next();   
    
15.             System.out.println(value);   
    
16.         }   
    
17.     }   
    
18. }  
    
19. 
    
20. 也可使用for循环迭代
    
21. Java代码  
    
22. for(Iterator iter = set.iterator();iter.hasNext();){   
    
23.             String value = (String)iter.next();   
    
24.             System.out.println(value);   
    
25.         }  
    
26.                
    
27. 下例中的TreeSet必须要有一个comparator类，才能往里添加Student对象，否则会抛出ClassCastException
    
28. Java代码  
    
29.   
    
30. import java.util.Comparator;   
    
31. import java.util.TreeSet;   
    
32.   
    
33. public class TreeSetTest {   
    
34.     public static void main(String[] args) {   
    
35.         TreeSet set = new TreeSet(new StudentComparator());   
    
36.         set.add(new Student(80));   
    
37.         set.add(new Student(90));   
    
38.         set.add(new Student(60));   
    
39.         set.add(new Student(70));   
    
40.            
    
41.         System.out.println(set);   
    
42.     }   
    
43. }   
    
44.   
    
45. class Student{   
    
46.     int score;   
    
47.   
    
48.     public Student(int score) {   
    
49.         this.score = score;   
    
50.     }   
    
51.       
    
52.     public String toString() {   
    
53.         return String.valueOf(score);   
    
54.     }   
    
55. }   
    
56.   
    
57. class StudentComparator implements Comparator{   
    
58.   
    
59.     //按学生成绩升序   
    
60.     public int compare(Object o1, Object o2) {   
    
61.         Student s1 =(Student)o1;   
    
62.         Student s2 =(Student)o2;   
    
63.         return s1.score - s2.score;   
    
64.     }   
    
65.       
    
66. }  
    
67.                
    
68.                
    

复制代码

  
  
   
   

     
   

     
   
  

复制代码