`
L.G.Alexander
  • 浏览: 158420 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

(十七):HashSet与HashMap关系之源码分析

阅读更多
题目:请说出hashCode方法,equals方法,HashSet,HasMap之间的关系?
解答:策略,分析jdk的源代码:
  public HashSet() {
	map = new HashMap<E,Object>();
    }


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方法源码如下:
   
public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
首先,如果key == null,这个key是往HashSet里面add的那个对象,它返回一个putForNullKey(value),它是一个方法,源码如下:
  
 private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
这里面有一个Entry,我们看看它的源码:
   
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
	    V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }
static class Entry表示它是一个静态的内部类,注意,外部类是不能用static的,对类来说,只有内部类能用static来修饰。这个Entry它实现了一个Map.Entry<K,V>接口,我看看Map.Entry<K,V>的源码:
   
interface Entry<K,V> {
	K getKey();
	V getValue();
	V setValue(V value);
	boolean equals(Object o);
	int hashCode();
    }
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的底层是怎样维护的呢?我们看一下源码:
 
  /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;
它是一个Entry类型的数组,table数组里面放Entry类型的,Entry的源码有:
  
     final K key;
        V value;

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

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

我们看HashMap的put方法,如果key == null,返回putForNullKey(value),看putForNullKey方法:
private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
首先做一个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方法源码:
   
static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
这个hash方法异常复杂。并且jdk5.0和jdk6.0对这个方法的实现方式也是不一样的。hash方法就是我们在数据结构中讲的散列函数。它是经过放进HashSet里面的对象作为key得到hashCode码,在进行散列得到的一个整数。
接着执行put方法里面的int i = indexFor(hash, table.length);语句,我们看看indexFor方法的源码:
 
 * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

indexFor方法也返回一个整型值,将上面通过hash方法得到的int值和数组的长度进行与运算,然后返回。他是往HashSet里面放置对象位置的索引值,它的值永远在0到数组长度减1之间,它是不会超过数组长度的。它是有hash方法和indexFor方法来保证不会超过的。
所以对于put方法,如果indexFor返回2,那么就在数组的第2个位置,然后执行for循环,如果第2个位置没有元素,则跳出for循环,调用addEntry方法将这个元素添加到数组中第2个位置,addEntry(hash, key, value, i);这是比较简单的情况。比较复杂的情况,数组的第2个位置已经有元素了,不为null,那么它是怎么做的呢?我们看一下:
         
  Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
它用这种方式方式进行比较,(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的大小而改变。
































分享到:
评论
2 楼 明天的昨天 2009-09-20  
文章写的很好 对我很有帮助
1 楼 blackstreet 2009-05-17  
我二年java工作经验的人,看的头晕

相关推荐

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

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

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

    HashMap的get方法源码分析: get方法是HashMap中最常用的方法之一,其源码如上所示。该方法首先判断key是否为空,如果为空则调用getForNullKey()方法。否则,获取key的hash值,并在“该hash值对应的链表”上查找...

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

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

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

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

    对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的容量...

    assemble:这是JDK中集合源码分析

    "assemble:这是JDK中集合源码分析" 提到的是对Java Development Kit (JDK) 中集合类的深入源码分析。集合框架主要包括List、Set、Map等接口,以及ArrayList、LinkedList、HashSet、HashMap等实现类。通过对这些源码...

    集合框架源码分析

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

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

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

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

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

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

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

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

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

    Java基础学习25.pdf

    ### HashSet源码分析 1. **构造器**:HashSet提供了多个构造器,可以创建默认容量的HashSet,指定容量和负载因子的HashSet,或者带有一个初始集合的HashSet。 2. **add(E e)**:向HashSet添加元素时,实际上是将...

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

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

    《JAVA 核心技术 卷I:基础知识》源码

    - 数组:源码中会展示如何声明、初始化和操作数组,以及数组与对象的关系。 - 集合框架:List,Set,Map等接口及其实现类的使用,如ArrayList,HashSet,HashMap等。 4. **异常处理**: - 异常分类:源码中会有...

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

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

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

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

    常见的java集合源码分析,以及面试题

    Vector与ArrayList类似,但在多线程环境下提供了同步控制,但通常不推荐使用,因为它的性能较差。 Set接口中的HashSet基于哈希表实现,存储元素时会计算其哈希值,因此插入和查找速度快。LinkedHashSet保持了元素的...

    Java 编程 源码 处理

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

    JAVA2核心技术第2卷:高级特性(源码)

    3. **集合框架**:Java的集合框架包括List、Set、Map等接口及其实现类,如ArrayList、LinkedList、HashSet、HashMap等。源码中会有如何操作这些数据结构的实例,如遍历、增删改查、并发访问等。 4. **IO流与NIO**:...

Global site tag (gtag.js) - Google Analytics