`
YOUNG918
  • 浏览: 188777 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

HashSet与HashMap关系之源码分析

    博客分类:
  • java
阅读更多

http://lukuijun.iteye.com/blog/340756

 

题目:请说出hashCode方法,equals方法,HashSet,HasMap之间的关系?
解答:策略,分析jdk的源代码:

Java代码
  1. public  HashSet() {  
  2. ap = new  HashMap<E,Object>();  
  3.   }  



1、HashSet底层是采用HashMap实现的。

private transient HashMap<E,Object> map;是HashSet类里面定义的一个私有的成员变量。并且是transient类型的,在序列化的时候是不会序列化到文件里面去的,信息会丢失。 HashMap<E,Object>里面的key为E,是HashSet<E>里面放置的对象E(对象的引用,为了简单方便起见 我说成是对象,一定要搞清楚,在集合里面放置的永远都是对象的引用,而不是对象,对象是在堆里面的,这个一定要注 意),HashMap<E,Object>的value是Object类型的。

2、这个HashMap的key就是放进HashSet中对象,value是Object类型的。当我去使用一个默认的构造方法的时候,执行 public HashSet() {map = new HashMap<E,Object>();},会将HashMap实例化,将集合能容纳的内型作为key,Object作为它的value。 当我们去往HashSet里面放值的时候,这个HashMap<E,Object>里面的Object类型的value到底取什么值呢?这个 时候我们就需要看HashSet的add方法,因为add方法可以往里面增加对象,通过往里面增加对象,会导致底层的HashMap增加一个key和 value。这个时候我们看一下add方法:  public boolean add(E e) {return map.put(e, PRESENT)==null;},add方法接受一个E类型的参数,这个E类型就是我们在HashSet里面能容纳的类型,当我们往HashSet里面 add对象的时候,HashMap是往里面put(E,PRESET),增加E为key,PRESET为value,PRESET是这样定义 的:private static final Object PRESENT = new Object();从这里我们知道PRESET是private static final Object的常量并且已经实例化好了。HashMap<E,Object>()中的key为HashSet中add的对象,不能重 复,value为PRESET,这是jdk为了方便将value设为常量PRESET,因为value是可以重复的。

3、当调用HashSet的add方法时,实际上是向HashMap中增加了一行(key-value对),该行的key就是向HashSet增加的那个对象,该行的value就是一个Object类型的常量。

接着,我们看看HashMap的源码,流程讲到map.put(e, PRESENT)==null,我们往HashSet里面add一个对象,那么HashMap就往里面put(key,value)。HashMap的put方法源码如下:

   
Java代码
  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.   
  16.         modCount++;  
  17.         addEntry(hash, key, value, i);  
  18.         return   null ;  
  19.     }  

首先,如果key == null,这个key是往HashSet里面add的那个对象,它返回一个putForNullKey(value),它是一个方法,源码如下:

  
Java代码
  1. private  V putForNullKey(V value) {  
  2.        for  (Entry<K,V> e = table[ 0 ]; e !=  null ; e = e.next) {  
  3.            if  (e.key ==  null ) {  
  4.                V oldValue = e.value;  
  5.                e.value = value;  
  6.                e.recordAccess(this );  
  7.                return  oldValue;  
  8.            }  
  9.        }  
  10.        modCount++;  
  11.        addEntry(0 null , value,  0 );  
  12.        return   null ;  
  13.    }  

这里面有一个Entry,我们看看它的源码:

   
Java代码
  1. static   class  Entry<K,V>  implements  Map.Entry<K,V> {  
  2.         final  K key;  
  3.         V value;  
  4.         Entry<K,V> next;  
  5.         final   int  hash;  
  6.   
  7.         /**  
  8.          * Creates new entry.  
  9.          */   
  10.         Entry(int  h, K k, V v, Entry<K,V> n) {  
  11.             value = v;  
  12.             next = n;  
  13.             key = k;  
  14.             hash = h;  
  15.         }  
  16.   
  17.         public   final  K getKey() {  
  18.             return  key;  
  19.         }  
  20.   
  21.         public   final  V getValue() {  
  22.             return  value;  
  23.         }  
  24.   
  25.         public   final  V setValue(V newValue) {  
  26.         V oldValue = value;  
  27.             value = newValue;  
  28.             return  oldValue;  
  29.         }  
  30.   
  31.         public   final   boolean  equals(Object o) {  
  32.             if  (!(o  instanceof  Map.Entry))  
  33.                 return   false ;  
  34.             Map.Entry e = (Map.Entry)o;  
  35.             Object k1 = getKey();  
  36.             Object k2 = e.getKey();  
  37.             if  (k1 == k2 || (k1 !=  null  && k1.equals(k2))) {  
  38.                 Object v1 = getValue();  
  39.                 Object v2 = e.getValue();  
  40.                 if  (v1 == v2 || (v1 !=  null  && v1.equals(v2)))  
  41.                     return   true ;  
  42.             }  
  43.             return   false ;  
  44.         }  
  45.   
  46.         public   final   int  hashCode() {  
  47.             return  (key== null    ?  0  : key.hashCode()) ^  
  48.                    (value==null  ?  0  : value.hashCode());  
  49.         }  
  50.   
  51.         public   final  String toString() {  
  52.             return  getKey() +  "="  + getValue();  
  53.         }  
  54.   
  55.         /**  
  56.          * This method is invoked whenever the value in an entry is  
  57.          * overwritten by an invocation of put(k,v) for a key k that's already  
  58.          * in the HashMap.  
  59.          */   
  60.         void  recordAccess(HashMap<K,V> m) {  
  61.         }  
  62.   
  63.         /**  
  64.          * This method is invoked whenever the entry is  
  65.          * removed from the table.  
  66.          */   
  67.         void  recordRemoval(HashMap<K,V> m) {  
  68.         }  
  69.     }  

static class Entry表示它是一个静态的内部类,注意,外部类是不能用static的,对类来说,只有内部类能用static来修饰。这个Entry它实现了一个 Map.Entry<K,V>接口,我看看Map.Entry<K,V>的源码:

   
Java代码
  1. interface  Entry<K,V> {  
  2.     K getKey();  
  3.     V getValue();  
  4.     V setValue(V value);  
  5.     boolean  equals(Object o);  
  6.     int  hashCode();  
  7.     }  

Map.Entry<K,V> 它是一个接口,里面定义了几个方法,Map.Entry<K,V>它实际上是一个内部的接口(inner interface),Map.Entry干什么用的呢?我看看Map接口有一个 Set<Map.Entry<K, V>> entrySet();方法,它返回一个Set集合,它里面是Map.Entry<K, V>类型的,这个方法用得非常多。表示你在调用一个Map的entrySet()方法,它会返回一个Set集合,这个集合里面放置的就是你的Map 的key和value这两个对象所共同组成的Map.Entry类型的那样的对象,Map.Entry类型对象里面放置的就是你的HashMap里面的 key和value,所以说当你去调用一个Map(不管是HashMap还是Treemap)的entrySet()方法,会返回一个Set集合,个集合 里面放置的就是你的Map的key和value这两个对象所共同组成的Map.Entry类型的那样的对象。
HashMap的底层是怎样维护的呢?我们看一下源码:

 
Java代码
  1. /**  
  2.    * The table, resized as necessary. Length MUST Always be a power of two.  
  3.    */   
  4.   transient  Entry[] table;  

它是一个Entry类型的数组,table数组里面放Entry类型的,Entry的源码有:

  
Java代码
  1. final  K key;  
  2.    V value;  


这里的K表示HashMap的key,V表示HashMap的value,所以我们可以大胆的断定,HashMap的底层是用数组来维护的。理解这一点非常重要,因为java的集合,底层大部分都是用数组来维护的,顶层之所以有那么高级,是因为底层对其进行了封装。

4、HashMap底层采用数组来维护。数组里面的每一个元素都是Entry,而这个Entry里面是Key和value组成的内容。

我们看HashMap的put方法,如果key == null,返回putForNullKey(value),看putForNullKey方法:

Java代码
  1. private  V putForNullKey(V value) {  
  2.         for  (Entry<K,V> e = table[ 0 ]; e !=  null ; e = e.next) {  
  3.             if  (e.key ==  null ) {  
  4.                 V oldValue = e.value;  
  5.                 e.value = value;  
  6.                 e.recordAccess(this );  
  7.                 return  oldValue;  
  8.             }  
  9.         }  
  10.         modCount++;  
  11.         addEntry(0 null , value,  0 );  
  12.         return   null ;  
  13.     }  

首 先做一个for循环,从Entry数组的第一个元素开始,e.next是static class Entry<K,V> implements Map.Entry<K,V>的一个成员属性 Entry<K,V> next;next也是Entry<K,V>类型的,next也可以指向Entry类型的对象,当我知道一个Entry类型的对象,就可以通 过它的next属性知道这个Entry类型的对象的后面一个Entry类型的对象,通过这个next变量来寻找下一个。next指向的Entry类型的对 象不在数组中。
接着判断e.key == null,如果e.key 为null,说明HashMap里面没有这个对象,这个时就会将我们add到Set里面的对象真真正正的放置到Entry数组里面去。
我们在看HashMap的put方法里面:int hash = hash(key.hashCode());如果key不为null,这个key就是我们往HashSet里面放置的那个对象。它就会调用 key.hashCode()方法,这是流程转到hashCode方法里面去了,调用hashCode()方法返回hash码,接着调用hash方法,我 们看看hash方法源码:

   
Java代码
  1. static   int  hash( int  h) {  
  2.         // This function ensures that hashCodes that differ only by   
  3.         // constant multiples at each bit position have a bounded   
  4.         // number of collisions (approximately 8 at default load factor).   
  5.         h ^= (h >>> 20 ) ^ (h >>>  12 );  
  6.         return  h ^ (h >>>  7 ) ^ (h >>>  4 );  
  7.     }  

这个hash方法异常复杂。并且jdk5.0和jdk6.0对这个方法的实现方式也是不一样的。hash方法就是我们在数据结构中讲的散列函数。它是经过放进HashSet里面的对象作为key得到hashCode码,在进行散列得到的一个整数。
接着执行put方法里面的int i = indexFor(hash, table.length);语句,我们看看indexFor方法的源码:

 
Java代码
  1. * Returns index  for  hash code h.  
  2.     */  
  3.    static   int  indexFor( int  h,  int  length) {  
  4.        return  h & (length- 1 );  
  5.    }  


indexFor方法也返回一个整型值,将上面通过hash方法得到的int值和数组的长度进行与运算,然后返回。他是往HashSet里面放置 对象位置的索引值,它的值永远在0到数组长度减1之间,它是不会超过数组长度的。它是有hash方法和indexFor方法来保证不会超过的。
所以对于put方法,如果indexFor返回2,那么就在数组的第2个位置,然后执行for循环,如果第2个位置没有元素,则跳出for循 环,调用addEntry方法将这个元素添加到数组中第2个位置,addEntry(hash, key, value, i);这是比较简单的情况。比较复杂的情况,数组的第2个位置已经有元素了,不为null,那么它是怎么做的呢?我们看一下:

         
Java代码
  1. Object k;  
  2.           if  (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  3.               V oldValue = e.value;  
  4.               e.value = value;  
  5.               e.recordAccess(this );  
  6.               return  oldValue;  
  7.           }  

它 用这种方式方式进行比较,(e.hash == hash && ((k = e.key) == key || key.equals(k))它会医用k的equals方法来个第2个位置上的元素进行比较,如果这个equals方法返回true,表示这个对象确实是 一个对象,这个时候还没有完,如果e.hash == hash并且key.equals(k)表示真的是相同的,这个时候就会用新的相同的对象的值替换就的那个值,同时它把旧的那个被替换的值给返回。如果不 相同呢,它会根据next指向的对象再去比较,如果又不成功又会根据它的next链去寻找比较,一直到最后一个,当为null的时候下一个就不存在了。这 就是put方法的for过程。我们往HashMap里面放值的时候,两种情况,要么放进去了增加(key-value)要么替换掉(将旧的值替换掉了,其 实是一样的)了。如果都不成功,表示在链上不存在,这个时候就直接添加到数组,同时将添加的这个Entry的next执行往外替换的那个Entry,这样 做的好处就是减少索引时间。不管你链接有多长,每次查找时间固定(用hash方法)。  

5、调用增加的那个对象的hashCode方法,来得到一个hashCode值,然后根据该值来计算出一个数组的下表索引(计算出数组中的一个位置)

6、将准备增加到map中的对象与该位置上的对象进行比较(equals方法),如果相同,那么就将该位置上的那个对象(Entry类型)的 value值替换掉,否则沿着该Entry的链接继承重复上述过程,如果到链的最后仍然没有找到与此对象相同的对象,那么这个时候就会将该对象增加到数组 中,将数组中该位置上的那个Entry对象链到该对象的后面。

7、对于HashSet,HashMap来说,这样做就是为了提高查找的效率,使得查找时间不随着Set或者Map的大小而改变。

分享到:
评论

相关推荐

    Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结

    Java集合专题总结:HashMap和HashTable源码...本文总结了HashMap和HashTable的源码学习和面试总结,涵盖了它们的存储结构、构造方法、get和put方法的源码分析、Hash表的特点和缺点、HashTable和HashMap的区别等内容。

    Java集合框架源码剖析:HashSet 和 HashMap

     之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。  HashMap实现了Map...

    JavaHashSet和HashMap源码剖析编程开发技术

    在源码分析中,我们可以关注以下几个关键点: 1. **哈希函数**:HashMap使用`hash()`方法计算键的哈希值,这个过程决定了元素在内部数组中的分布。 2. **数组与链表**:当哈希冲突发生时,HashMap会将冲突的键值对...

    对java基础集合部分(List、HashMap、HashSet、ArrayList等)底层源码的分析与总结

    本文主要探讨了几个关键的集合接口和实现类的底层源码,包括List、HashMap、HashSet等,以及它们的基本操作。 首先,Collection接口是所有单值集合的父接口,提供了增加、删除、遍历元素的基本方法。例如,`add()`...

    java集合类源码分析之Set详解.docx

    以下是对HashSet关键方法的源码分析: 1. 构造器: - `HashSet()`:创建一个空的HashSet,其内部的HashMap默认容量为16。 - `HashSet(Collection&lt;? extends E&gt; c)`:根据传入的集合c初始化HashSet,HashMap的容量...

    Android+上百实例源码分析以及开源分析+集合打包3

    总之,"Android+上百实例源码分析以及开源分析+集合打包3"是一个全面的Android学习资源,它将帮助开发者从基础实例操作到源码深入理解,再到开源库的应用与分析,全面提升Android开发水平。通过系统学习和实践,...

    集合的概念及应用和HashSet保证数据不重复的原理

    同时,源码分析也能帮助我们理解HashMap的扩容机制,以及为什么即使两个对象的hashCode相同,它们仍然可以在HashSet中区分(因为equals()方法的正确实现)。 工具在学习和使用集合框架时也扮演着重要角色。例如,...

    【死磕Java集合】-集合源码分析.pdf

    四、HashMap源码分析 HashMap是一种基于散列表实现的Map,提供了快速的键值对存储和检索能力。HashMap的继承体系中,它继承了AbstractMap,实现了Map接口。 HashMap的主要属性包括键值对数组table、键值对个数size...

    Java面试题 从源码角度分析HashSet实现原理

    通过源码分析, HashSet的实现原理可以分为以下几个方面: 1. HashSet的构造函数:HashSet的构造函数中,会创建一个HashMap对象,用于存储集合元素。`public HashSet() { map = new HashMap();}` 2. HashSet的add...

    集合框架源码分析

    4. **源码分析:HashMap** `HashMap`是`Map`接口的主要实现,它使用哈希表(数组+链表/红黑树)来存储键值对。哈希函数用于快速定位元素,链表处理哈希冲突。当链表长度超过一定阈值时,会转换为红黑树,以提高查找...

    Java中的HashSet详解和使用示例_动力节点Java学院整理

    在HashSet的源码分析中,可以看到HashSet是通过map(HashMap对象)保存内容的。HashSet中的map变量是transient的,也就是说,HashSet对象在序列化时,不会将map对象序列化。HashSet中还定义了一个静态final变量PRESENT...

    深入解读大厂java面试必考点之HashMap全套学习资料

    - HashMap与HashSet的关系? - 如何解决哈希冲突? - 如何自定义键的哈希码生成方式? - 如何避免和处理HashMap中的循环链表? 通过深入学习和理解这些知识点,你将能够在面试中自信地应对关于HashMap的问题,提升...

    java集合类源码分析之Set详解

    Java集合类源码分析之Set详解 Java集合类中的Set Interface是用于存储无序、不可重复元素的集合接口。Set Interface继承自Collection Interface,提供了基本的集合操作,如add、remove、contains等。Set Interface...

    Java源码分析:集合-容器.pdf

    HashSet是基于HashMap实现的,其元素存储在HashMap的key上,而value使用一个静态的默认对象。为了保证元素的唯一性,存储在HashSet中的对象必须正确地覆写hashCode和equals方法。TreeSet利用二叉树的原理对元素进行...

    Java 编程 源码 处理

    4. **集合框架**:Java集合框架包括List、Set、Map等接口及其实现类,如ArrayList、HashSet、HashMap等。源码分析能帮助理解它们的工作机制和性能特点,选择合适的数据结构存储和操作数据。 5. **多线程编程**:...

    corejava7源码

    源码中展示了这些接口的实现机制,如ArrayList、LinkedList、HashSet、HashMap的工作原理,这对于理解和优化代码性能至关重要。 3. 异常处理:Java的异常处理机制(try-catch-finally,throws,throw)是其强健性的...

    java课程设计源码

    Java课程设计源码是针对Java编程语言的一系列实践项目,旨在帮助学习者加深对Java语言的理解,...在研究源码时,建议逐步分析每个类和方法的作用,理解它们之间的关系,并尝试修改和扩展代码,以增强自己的编程能力。

    疯狂java讲义源码和疯狂Java实战源码

    源码分析: 1. **类和对象**:Java是一种面向对象的语言,书中源码会展示如何定义类、封装数据、创建对象以及如何使用面向对象的特性如继承、多态和抽象。通过阅读这些源码,你可以看到类的构造函数、成员变量和...

    Android_上百实例源码分析以及开源分析_集合打包1

    3. **集合框架深入理解**:由于文件名包含“集合”,所以这部分内容可能着重于Android中对Java集合框架的运用,如ArrayList、LinkedList、HashMap、HashSet等。开发者将学习如何高效地管理数据结构,理解并发环境下...

    Java 集合学习指南 - v1.1.pdf

    最后,针对集合的学习指南还涉及了对集合类之间的对比分析,如HashSet与HashMap的比较。它们在实现上有着类似的机制,但HashSet专注于存储不重复的元素,而HashMap专注于存储键值对映射。 本学习指南适合已经具备...

Global site tag (gtag.js) - Google Analytics