`

java hashSet与hashMap

阅读更多
题目:请说出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的大小而改变。
分享到:
评论
2 楼 abc08010051 2013-09-10  
请问楼主:既然hashmap是用数组存放Entry,为什么还在entry里放一个next属性,而且在查找的时候基本上都是通过next来找下一个entry,不是所有的entry都应该在数组里吗?
1 楼 tyut8518 2010-04-11  
探究的相当深啊 得循序渐进来了

相关推荐

    Java中HashSet和HashMap的区别_动力节点Java学院整理

    Java中HashSet和HashMap的区别 Java中HashSet和HashMap是两个常用的集合类,它们都属于Java集合框架(Java Collection Framework),但是它们有着不同的实现和应用场景。 什么是HashSet? HashSet实现了Set接口,...

    1.HashSet和HashMap遍历.md

    自己写的例子,关于HashSet遍历和HashMap遍历的. 感谢大家参考

    Java HashMap类详解

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,虽然它们实现的接口规范不同,但它们底层的 Hash 存储机制完全一样。甚至 HashSet 本身就采用 HashMap 来实现的。 2. Hash 存储机制 HashMap ...

    treemap treeset hashset hashmap 简要介绍

    在Java编程语言中,集合框架提供了多种数据结构来存储和操作数据,其中`TreeMap`、`TreeSet`、`HashSet`以及`HashMap`是最常用的数据结构之一。这些集合类各自有着独特的特性和应用场景,下面将对它们进行详细介绍。...

    HashSet和HashMap的区别_动力节点Java学院整理

    什么是HashSet? HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以...

    java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

    1. **HashMap与HashSet的比较**: - 两者的判断方式都是通过哈希值和equals()方法。哈希冲突时,使用equals()进行精确匹配。 - 由于HashMap允许键值对的键重复(但值不重复),而HashSet不允许元素重复,因此在...

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

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

    HashMap与HashTable和HashSet的区别

    ### HashMap与HashTable和HashSet的区别 #### 一、概述 在Java集合框架中,`HashMap`, `HashTable` 和 `HashSet` 是三个重要的数据结构,它们分别实现了`Map`接口和`Set`接口,提供了不同的功能来满足不同的编程...

    Java基础加强_ArrayList_HashSet的比较及Hashcode分析

    本篇将深入探讨ArrayList与HashSet的区别,并分析Hashcode在其中的作用。 ArrayList是基于动态数组实现的,它提供了按索引访问元素的能力,就像在数组中一样。由于内部维护了一个数组,ArrayList保证了元素的顺序性...

    HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别.docx

    HashMap与HashTable的主要区别在于线程安全性和对null值的支持。HashMap是非同步的,意味着在多线程环境中,如果不进行适当的同步控制,可能会导致数据不一致。而HashTable是同步的,因此它在多线程环境下的安全性更...

    java中HashMap,LinkedHashMap,TreeMap,HashTable的区别

    与`HashMap`类似,它也是基于哈希表实现的,但不允许使用`null`键或值。 - **特点**: - **线程安全**:由于它内部使用了`synchronized`关键字,所以可以直接在多线程环境中使用。 - **不支持null**:既不允许`...

    HashSet工作原理_动力节点Java学院整理

    对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:

    HashSet的实现原理

    HashSet基于HashMap实现,但与HashMap不同的是,HashSet并不存储键(key),而是存储值(value),并且HashMap中键对应的值统一使用一个静态的、不变的Object实例来替代。这个静态实例被定义为HashSet的一个私有静态常量...

    Java中HashMap详解(通俗易懂).doc

    Java中的HashMap是一个非常重要的...总结起来,HashMap和HashSet是Java集合框架的重要组成部分,它们利用哈希技术提供了高效的数据存储和检索。了解并熟练掌握HashMap的工作原理对于优化Java应用程序的性能至关重要。

    Java中的HashMap浅析

    在Java的集合框架中,HashSet,HashMap是用的比较多的一种,顺序结构的ArrayList、LinkedList这种也比较多,而像那几个线程同步的容器用的比较少,像Vector和HashTable,因为这两个线程同步的容器已经不被JDK推荐...

    java基础练习题 (目前到集合内含三个小综合案例)

    Java集合框架包括接口(如List、Set、Queue)和实现类(如ArrayList、LinkedList、HashSet、HashMap等)。理解各种集合的区别,以及它们的实现方式和应用场景,是提升编程效率的关键。例如,List接口中的ArrayList和...

    Java中HashSet的解读_.docx

    在Java编程语言中,HashSet是一种基于哈希表(HashMap)实现的无序、不重复的集合类。它的核心特点是高效查找、添加和删除元素。在深入解析HashSet之前,我们需要了解其内部使用的HashMap的工作原理。 HashMap是...

    (001)HashMap之链表转红黑树-treefyBin方法.docx

    在Java的集合框架中,HashMap是一种高效的键值对存储结构,它通过散列函数实现快速查找。当元素数量增加,导致某一个桶(bucket)内的链表过长时,为了保持查询性能,HashMap会将链表转换为红黑树。这个过程主要由`...

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

    HashSet是Java编程语言中的一种集合类,它是一个不包含重复元素的集合,其内部实现基于HashMap。HashSet不保证元素的顺序,允许存储null元素,并且是非同步的,这意味着在多线程环境下,如果需要保证线程安全,需要...

Global site tag (gtag.js) - Google Analytics