黑马程序员技术交流社区

标题: HashSet的实现方式(建议大家多去看源码) [打印本页]

作者: 杨志    时间: 2012-7-27 20:54
标题: HashSet的实现方式(建议大家多去看源码)
本帖最后由 杨志 于 2012-7-27 21:05 编辑

刚解决一个同学的问题。关于hashSet中的add方法和remove方法。
希望大家认真去看!如果这点时间都不肯花的话!我想更不要说让你自己去看源代码了!
个人查了一下jdk的源码。感觉这些可能对大家有点好处。就发个帖子。
建议多看源码,会有些意外的收获。
好的那么咱们就来看看JDK 的源码是怎么样实现hashSet的。
其实是这样的!先看下代码!
  1. /**
  2.      * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
  3.      * default initial capacity (16) and load factor (0.75).
  4.      */
  5.    public HashSet() {
  6. map = new HashMap<E,Object>();
  7.     }
复制代码
这是JDK中的HashSet的构造方法。
这里看到这里的HashSet其实是采用了HashMap去存储的。
那么这里hashSet的add 方法又是怎么样呢!如下:
  1. public boolean add(E e) {
  2. return map.put(e, PRESENT)==null;
  3.     }
复制代码
也是用了hashMap的put方法。这里的PRESENT只是一个Object对象。一个final变量。
那么好的!我们就去看看HashMap中的put方法是怎么样做的!
  1.     public V put(K key, V value) {
  2.         if (key == null)
  3.             return putForNullKey(value);
  4.         int hash = hash(key.hashCode());
  5.         int i = indexFor(hash, table.length);
  6.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  7.             Object k;
  8.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  9.                 V oldValue = e.value;
  10.                 e.value = value;
  11.                 e.recordAccess(this);
  12.                 return oldValue;
  13.             }
  14.         }
  15.         modCount++;
  16.         addEntry(hash, key, value, i);
  17.         return null;
  18.     }
复制代码
可以到这里
  1. int hash = hash(key.hashCode());
复制代码
这句表明其实,将传入的Key先转换成hashCOde.然后再进行移位运算。
而这里你并没有对该对象的hashCode方法进行重载。那么就是说两个hashCode值不同。
  1. public class Test{

  2. public static void main(String[] args){

  3. Person p1 = new Person("tt");
  4. Person p2 = new Person("tt");

  5. System.out.println(p1.hashCode());
  6. System.out.println(p2.hashCode());

  7. }
  8. }
  9. class Person{
  10. private String name;
  11. public Person(String name){
  12. this.name = name;
  13. }
  14. }
复制代码
所以可以看出其实存入了两个对象的。
我想现在你应该知道hashCode方法存在的意义了。
当你去重写hashCode方法,根据值去生成hashCode.那么在底层发现两次的值是一样的。
这样就不会去保存。也就额可以避免重复。我想现在  equals()方法你也知道是为什么了吧!
也是为了避免重复添加。
现在在去看看 remove方法是怎么完成的。
  1. public boolean remove(Object o) {
  2. return map.remove(o)==PRESENT;
  3. }
复制代码
一样也是调用了map的方法。而map的方法是怎么样的呢?
  1. public V remove(Object key) {
  2. Entry<K,V> e = removeEntryForKey(key);
  3. return (e == null ? null : e.value);
  4. }
复制代码
一样的也是根据key值去删除的。在看看你的代码:
  1. c.remove(new Person("Jack", 20))
复制代码
你是新建了一个对象。那么请问这个对象以前有么?肯定是没有的。注意判断的根据是根据hashCode值 哦!
所有remove一个hashSet中根本就没有的值肯定是不可以的。
我不知道为什么你会说hashSet中的remove方法要new一个对象。看下面代码:
  1. import java.util.*;
  2. public class Test{

  3. public static void main(String[] args){
  4. Set set=new HashSet();

  5. Person p1 = new Person("tt");
  6. Person p2 = new Person("tt");
  7. set.add(p1);
  8. set.add(p2);
  9. System.out.println(set.size());
  10. set.remove(p2);
  11. System.out.println(set.size());
  12. System.out.println(p1.hashCode());
  13. System.out.println(p2.hashCode());
  14. }
  15. }
  16. class Person{
  17. private String name;
  18. public Person(String name){
  19. this.name = name;
  20. }
  21. }
复制代码
这样就可以删除了撒!因为p2存在的,而不是new 的一个对象。
好了说了这么多!建议碰到不会的去看看JDK 。真的很有帮助。希望你能有点帮助。
个人还是推荐多看JDK源码。那才真的是一座宝库!

作者: 牛杨    时间: 2012-8-4 11:39
呵呵呵 同意同意,有些问题听老师怎么讲都不明白,稍微看看原码自己思考 思考就都明白了
作者: 杨志    时间: 2012-8-4 12:06
牛杨 发表于 2012-8-4 11:39
呵呵呵 同意同意,有些问题听老师怎么讲都不明白,稍微看看原码自己思考 思考就都明白了 ...

嘿嘿!多多加油哦!
本来准备给你弄点分!
发现12期我不是版主不能加分!嘿嘿!
作者: 牛杨    时间: 2012-8-4 12:09
杨志 发表于 2012-8-4 12:06
嘿嘿!多多加油哦!
本来准备给你弄点分!
发现12期我不是版主不能加分!嘿嘿! ...

没事 怎么加技术分的规则我还不太明白呢 ,正在努力中。
作者: 叶久瑞    时间: 2012-8-5 19:57
版主写的太棒了!刚刚看到,很好,查看源码也是一种很好的学习方法,好多东西的原理懂了,就知道怎么用了,顶一下!
作者: 杨志    时间: 2012-8-5 20:22
叶久瑞 发表于 2012-8-5 19:57
版主写的太棒了!刚刚看到,很好,查看源码也是一种很好的学习方法,好多东西的原理懂了,就知道怎么用了, ...

嘿嘿!加油呢!
作者: 沙漠里的小鱼    时间: 2012-9-23 03:01
请问源码应该怎么看呢
作者: 杨志    时间: 2012-9-23 14:47
沙漠里的小鱼 发表于 2012-9-23 03:01
请问源码应该怎么看呢

JDK中自带了源码包的!
作者: Changer_s    时间: 2013-5-27 23:47
挺喜欢楼主这种做事风格的,但有时候地方不太会用,也用到挺少的,在api找答案不太会
而百度或者论坛提问来得快些,但是忘记得也快一些
呜呜呜~~~
作者: liyi8110301    时间: 2014-1-13 21:49
感谢楼主的分享,谢谢。




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2