java该HashTable,HashMap和HashSet

时间：2022-03-08 15:59:50
同一时候我们也对HashSet和HashMap的核心方法hashcode进行了具体解释，见《探索equals()和hashCode()方法》。

万事俱备，那么以下我们就对基于hash算法的三个集合HashTable,HashSet和HashMap具体解释。

本文文件夹：

1. HashTable和HashMap的差别

2. HashSet和HashMap的差别

3. HashMap，HashSet工作原理

4. HashSet工作原理

5. 常见问题

1. HashTable和HashMap的差别

---------------------------------------------------------

相信这个是大家最easy混淆的。

HashMap和Hashtable都实现了Map接口，但决定用哪一个之前先要弄清楚它们之间的分别。基本的差别有：线程安全性。同步(synchronization)。以及速度。

  1. HashMap差点儿能够等价于Hashtable，除了HashMap是非synchronized的，并能够接受null(HashMap allows
    one null key and any number of null values.，而Hashtable则不行)。

    这就是说，HashMap中假设在表中没有发现搜索键，或者假设发现了搜索键。但它是一个空的值。那么get()将返回null。

    假设有必要，用containKey()方法来差别这两种情况。

  2. HashMap是非synchronized，而Hashtable是synchronized。这意味着Hashtable是线程安全的，多个线程能够共享一个Hashtable；而假设没有正确的同步的话，多个线程是不能共享HashMa的。 即是说，在多线程应用程序中，不用专门的操作就安全地能够使用Hashtable了。而对于HashMap。则须要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决：

                Map Collections.synchronizedMap(Map m)

    这种方法返回一个同步的Map，这个Map封装了底层的HashMap的全部方法，使得底层的HashMap即使是在多线程的环境中也是安全的。

    而并且Java 5提供了ConcurrentHashMap。它是HashTable的替代，比HashTable的扩展性更好。

    要具体了解ConcurrentHashMap见《构建一个更好的
HashMap---ConcurrentHashMap》
  1. 还有一个差别是HashMap的迭代器(Iterator)是fail-fast迭代器。而Hashtable的enumerator迭代器不是fail-fast的。所以当有其他线程改变了HashMap的结构（添加或者移除元素），将会抛出ConcurrentModificationException。但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并非一个一定发生的行为。要看JVM。这条相同也是Enumeration和Iterator的差别。
  2. 因为Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。假设你不须要同步，仅仅须要单一线程。那么使用HashMap性能要好过Hashtable。
  3. HashMap不能保证随着时间的推移Map中的元素次序是不变的。
  4. 哈希值的使用不同。HashTable直接使用对象的hashCode。代码是这种：

          int hash = key.hashCode();

          int index = (hash & 0x7FFFFFFF) % tab.length;

    而HashMap又一次计算hash值，并且用与取代求模：

    int hash = hash(k);

    int i = indexFor(hash, table.length);


要注意的一些重要术语：

1) sychronized意味着在一次仅有一个线程可以更改Hashtable。就是说不论什么线程要更新Hashtable时要首先获得同步锁，其他线程要等到同步锁被释放之后才干再次获得同步锁更新Hashtable。

2) Fail-safe和iterator迭代器相关。假设某个集合对象创建了Iterator或者ListIterator，然后其他的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。

但其他线程能够通过set()方法更改集合对象是同意的。由于这并没有从“结构上”更改集合。

可是假如已经从结构上进行了更改，再调用set()方法。将会抛出IllegalArgumentException异常。

3) 结构上的更改指的是删除或者插入一个元素，这样会影响到map的结构。

2. HashSet和HashMap的差别

---------------------------------------------------------

在分析他们的差别之前。我们首先分别来简介一下他们俩。（后面我会具体的结合源代码分析他俩）

什么是HashSet？

HashSet实现了Set接口，它不同意集合中有反复的值，当我们提到HashSet时。第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才干比較对象的值是否相等，以确保set中没有储存相等的对象。假设我们没有重写这两个方法，将会使用这种方法的默认实现。

详见《探索equals()和hashCode()方法》。

public boolean add(Object o)方法用来在Set中加入元素，当元素值反复时则会马上返回false。假设成功加入的话会返回true。

什么是HashMap？

HashMap实现了Map接口，Map接口对键值对进行映射。

Map中不同意反复的键。

Map接口有两个主要的实现，HashMap和TreeMap。

TreeMap保存了对象的排列次序，而HashMap则不能。

HashMap同意键和值为null。HashMap是非synchronized的，但collection框架提供方法能保证HashMap synchronized。这样多个线程同一时候訪问HashMap时。能保证仅仅有一个线程更改Map。

public Object put(Object Key,Object value)方法用来将元素加入到map中。

HashSet和HashMap的差别

*HashMap* *HashSet*
HashMap实现了Map接口 HashSet实现了Set接口
HashMap储存键值对 HashSet只存储对象（且无反复对象）
使用put()方法将元素放入map中 使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值 HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能同样。所以equals()方法用来推断对象的相等性。假设两个对象不同的话，那么返回false
HashMap比較快。由于是使用唯一的键来获取对象 HashSet较HashMap来说比較慢

3. HashMap工作原理

---------------------------------------------------------



实际上，HashSet 和 HashMap 之间有非常多相似之处，对于 HashSet 而言。系统採用 Hash 算法决定集合元素的存储位置。这样能够保证能高速存、取集合元素；对于 HashMap 而言，系统 key-value 当成一个总体进行处理，系统总是依据 Hash 算法来计算 key-value 的存储位置，这样能够保证能高速存、取 Map 的 key-value 对。

在介绍集合存储之前须要指出一点：尽管集合号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入 Set 集合中，仅仅是在 Set 集合中保留这些对象的引用而言。也就是说：Java 集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的 Java 对象。

就像引用类型的数组一样，当我们把
Java 对象放入数组之时。并非真正的把 Java 对象放入数组中。仅仅是把对象的引用放入数组中，每一个数组元素都是一个引用变量。

HashMap存储的实现（put()方法）

当程序试图将多个key-value放入HashMap中是。以例如以下代码片段为例：

  1. HashMap<String , Double> map = new HashMap<String , Double>();
  2. map.put("语文" , 80.0);
  3. map.put("数学" , 89.0);
  4. map.put("英语" , 78.2);

HashMap採用了一种所谓的“Hash算法”来决定每一个元素的存储位置。

当程序运行map.put("语文",80.0)时。系统将调用"语文"（即Key）的hashCode()方法得到其hashCode值---每一个java对象都有hashCode()方法，都能够通过该方法获得它的hashCode值。

得到这个对象的hashCode值之后。系统依据hashCode值来决定 该元素的存储位置。

我们能够看HashMap类的put(K key,V value)方法的源码：

  1. public V put(K key, V value)
  2. {
  3. // 假设 key 为 null，调用 putForNullKey 方法进行处理
  4. if (key == null)
  5. return putForNullKey(value);
  6. // 依据 key 的 keyCode 计算 Hash 值
  7. int hash = hash(key.hashCode());
  8. // 搜索指定 hash 值在相应 table 中的索引
  9. int i = indexFor(hash, table.length);
  10. // 假设 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素
  11. for (Entry<K,V> e = table[i]; e != null; e = e.next)
  12. {
  13. Object k;
  14. // 找到指定 key 与须要放入的 key 相等（hash 值同样
  15. // 通过 equals 比較放回 true）
  16. if (e.hash == hash && ((k = e.key) == key
  17. || key.equals(k)))
  18. {
  19. V oldValue = e.value;
  20. e.value = value;
  21. e.recordAccess(this);
  22. return oldValue;
  23. }
  24. }
  25. // 假设 i 索引处的 Entry 为 null。表明此处还没有 Entry
  26. modCount++;
  27. // 将 key、value 加入到 i 索引处
  28. addEntry(hash, key, value, i);
  29. return null;
  30. }

上面程序中用到了一个重要的内部接口：Map.Entry，每一个 Map.Entry 事实上就是一个 key-value 对。

从上面程序中能够看出：当系统决定存储 HashMap 中的 key-value 对时，全然没有考虑 Entry 中的 value，只不过依据 key 来计算并决定每一个 Entry 的存储位置。这也说明了前面的结论：我们全然能够把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后。value 随之保存在那里就可以。

上面方法提供了一个依据 hashCode() 返回值来计算 Hash 码的方法：hash()，这种方法是一个纯粹的数学计算，其方法例如以下：

static int hash(int h)

{

    h ^= (h >>> 20) ^ (h >>> 12);

    return h ^ (h >>> 7) ^ (h >>> 4);

}

对于随意给定的对象，仅仅要它的 hashCode() 返回值同样，那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是同样的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。

indexFor(int h, int length) 方法的代码例如以下：

static int indexFor(int h, int length)

{

    return h & (length-1);

}

这种方法很巧妙。它总是通过 h &(table.length -1) 来得到该对象的保存位置——而 HashMap 底层数组的长度总是 2 的 n 次方。这一点可參看后面关于 HashMap 构造器的介绍。

当 length 总是 2 的倍数时。h & (length-1)将是一个很巧妙的设计：如果
h=5,length=16, 那么 h & length - 1 将得到 5；假设 h=6,length=16, 那么 h & length - 1 将得到 6 ……假设 h=15,length=16, 那么 h & length - 1 将得到 15；可是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了。当 h=17 时 , length=16 时。那么 h & length - 1 将得到 1 了……这样保证计算得到的索引值总是位于 table 数组的索引之内。

依据上面 put 方法的源码能够看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先依据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：假设两个 Entry 的 key 的 hashCode() 返回值同样，那它们的存储位置同样。假设这两个 Entry 的 key 通过 equals 比較返回 true。新加入 Entry 的 value 将覆盖集合中原有 Entry 的 value。但 key 不会覆盖。

假设这两个 Entry 的 key 通过 equals
比較返回 false，新加入的 Entry 将与集合中原有 Entry 形成 Entry 链，并且新加入的 Entry 位于 Entry 链的头部——详细说明继续看 addEntry() 方法的说明。

当向 HashMap 中加入 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（就是 Entry 对象）的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值同样时。将由 key 通过 eqauls() 比較值决定是採用覆盖行为（返回 true），还是产生 Entry 链（返回 false）。

上面程序中还调用了 addEntry(hash, key, value, i); 代码。当中 addEntry 是 HashMap 提供的一个包訪问权限的方法，该方法仅用于加入一个 key-value 对。

以下是该方法的代码：

<span style="font-weight: normal;">void addEntry(int hash, K key, V value, int bucketIndex)

{

    // 获取指定 bucketIndex 索引处的 Entry

    Entry<K,V> e = table[bucketIndex]; 	 // ①

    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry

    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

    // 假设 Map 中的 key-value 对的数量超过了极限

    if (size++ >= threshold)

        // 把 table 对象的长度扩充到 2 倍。

        resize(2 * table.length); 	 // ②

}</span>

上面方法的代码非常easy。但当中包括了一个非常优雅的设计：系统总是将新加入的 Entry 对象放入 table 数组的 bucketIndex 索引处——假设 bucketIndex 索引处已经有了一个 Entry 对象，那新加入的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），假设 bucketIndex 索引处没有 Entry 对象。也就是上面程序①号代码的 e 变量是 null，也就是新放入的 Entry 对象指向
null。也就是没有产生 Entry 链。

什么是Map.Entry？

  1. <span style="font-weight: normal;"><span style="font-size:14px;">Map是java中的接口，Map.Entry是Map的一个内部接口。
  2. Map提供了一些经常用法，如keySet()、entrySet()等方法，keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry。
  3. Map.Entry是Map声明的一个内部接口。此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue方法。
  4. 由以上能够得出。遍历Map的经常用法：
  5. 1.  Map map = new HashMap();
  6. Irerator iterator = map.entrySet().iterator();
  7. while(iterator.hasNext()) {
  8. Map.Entry entry = iterator.next();
  9. Object key = entry.getKey();
  10. //
  11. }
  12. 2.Map map = new HashMap();
  13. Set  keySet= map.keySet();
  14. Irerator iterator = keySet.iterator;
  15. while(iterator.hasNext()) {
  16. Object key = iterator.next();
  17. Object value = map.get(key);
  18. //
  19. }
  20. 另外。另一种遍历方法是，单纯的遍历value值，Map有一个values方法。返回的是value的Collection集合。

    通过遍历collection也能够遍历value,如

  21. Map map = new HashMap();
  22. Collection c = map.values();
  23. Iterator iterator = c.iterator();
  24. while(iterator.hasNext()) {
  25. Object value = iterator.next();
  26. }</span></span>

Map.Entry是Map内部定义的一个接口，专门用来保存key→value的内容。

Map.Entry的定义例如以下：

  1. public static interface Map.Entry<K,V>

Map.Entry是使用statickeyword声明的内部接口。此接口能够由外部通过"外部类.内部类"的形式直接调用。在本接口中提供了如表13-12所看到的的方法。

表13-12  Map.Entry接口的经常用法

序号

方    法

类型

描    述

1

public boolean equals(Object o)

普通

对象比較

2

public K getKey()

普通

取得key

3

public V getValue()

普通

取得value

4

public int hashCode()

普通

返回哈希码

5

public V setValue(V value)

普通

设置value的值

从之前的内容能够知道。在Map的操作中。全部的内容都是通过key→value的形式保存数据的，那么对于集合来讲，实际上是将key→value的数据保存在了Map.Entry的实例之后，再在Map集合中插入的是一个Map.Entry的实例化对象，如图13-4所看到的。

java该HashTable,HashMap和HashSet 
（点击查看大图）图13-4  Map与Map.Entry

U提示：Map.Entry在集合输出时会使用到。

在一般的Map操作中（比如，添加或取出数据等操作）不用去管Map.Entry接口，可是在将Map中的数据所有输出时就必须使用Map.Entry接口


Hash 算法的性能选项

依据上面代码能够看出，在同一个 bucket 存储 Entry 链的情况下。新放入的 Entry 总是位于 bucket 中。而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端。

上面程序中还有这样两个变量：

  • size：该变量保存了该 HashMap 中所包括的 key-value 对的数量。
  • threshold：该变量包括了 HashMap 能容纳的 key-value 对的极限。它的值等于 HashMap 的容量乘以负载因子（load factor）。

从上面程序中②号代码能够看出。当 size++ >= threshold 时，HashMap 会自己主动调用 resize 方法扩充 HashMap 的容量。

每扩充一次，HashMap 的容量就增大一倍。

上面程序中使用的 table 事实上就是一个普通数组。每一个数组都有一个固定的长度。这个数组的长度就是 HashMap 的容量。HashMap 包括例如以下几个构造器：

  • HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

当创建一个 HashMap 时，系统会自己主动创建一个 table 数组来保存 HashMap 中的 Entry，以下是 HashMap 中一个构造器的代码：

 // 以指定初始化容量、负载因子创建 HashMap

 public HashMap(int initialCapacity, float loadFactor)

 {

	 // 初始容量不能为负数

	 if (initialCapacity < 0)

		 throw new IllegalArgumentException(

		"Illegal initial capacity: " +

			 initialCapacity);

	 // 假设初始容量大于最大容量，让出示容量

	 if (initialCapacity > MAXIMUM_CAPACITY)

		 initialCapacity = MAXIMUM_CAPACITY;

	 // 负载因子必须大于 0 的数值

	 if (loadFactor <= 0 || Float.isNaN(loadFactor))

		 throw new IllegalArgumentException(

		 loadFactor);

	 // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。

	 int capacity = 1;

	 while (capacity < initialCapacity)

		 capacity <<= 1;

	 this.loadFactor = loadFactor;

	 // 设置容量极限等于容量 * 负载因子

	 threshold = (int)(capacity * loadFactor);

	 // 初始化 table 数组

	 table = new Entry[capacity]; 			 // ①

	 init();

 }

上面代码中粗体字代码包括了一个简洁的代码实现：找出大于 initialCapacity 的、最小的 2 的 n 次方值，并将其作为 HashMap 的实际容量（由 capacity 变量保存）。比如给定 initialCapacity 为 10，那么该 HashMap 的实际容量就是 16。

initialCapacity 与 HashTable 的容量

创建 HashMap 时指定的 initialCapacity 并不等于 HashMap 的实际容量。通常来说。HashMap 的实际容量总比 initialCapacity 大一些，除非我们指定的 initialCapacity 參数值恰好是 2 的 n 次方。当然，掌握了 HashMap 容量分配的知识之后，应该在创建 HashMap 时将 initialCapacity 參数值指定为 2 的 n 次方。这样能够降低系统的计算开销。

程序①号代码处能够看到：table 的实质就是一个数组，一个长度为 capacity 的数组。

对于 HashMap 及其子类而言，它们採用 Hash 算法来决定集合中元素的存储位置。当系统開始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里能够存储元素的位置被称为“桶（bucket）”，每一个 bucket 都有其指定索引，系统能够依据其索引高速訪问该 bucket 里存储的元素。

不管何时，HashMap 的每一个“桶”仅仅存储一个元素（也就是一个 Entry）。因为 Entry 对象能够包括一个引用变量（就是 Entry 构造器的的最后一个參数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中仅仅有一个 Entry，但这个 Entry 指向还有一个 Entry ——这就形成了一个 Entry 链。如图 1 所看到的：

图 1. HashMap 的存储示意

java该HashTable,HashMap和HashSet

key同样的则产生链。

HashMap 的读取实现（）

当 HashMap 的每一个 bucket 里存储的 Entry 仅仅是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出相应 value 时，系统仅仅要先计算出该 key 的 hashCode() 返回值，在依据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 相应的 value 就可以。看 HashMap
类的 get(K key) 方法代码：

 public V get(Object key)

 {

	 // 假设 key 是 null，调用 getForNullKey 取出相应的 value

	 if (key == null)

		 return getForNullKey();

	 // 依据该 key 的 hashCode 值计算它的 hash 码

	 int hash = hash(key.hashCode());

	 // 直接取出 table 数组中指定索引处的值，

	 for (Entry<K,V> e = table[indexFor(hash, table.length)];

		 e != null;

		 // 搜索该 Entry 链的下一个 Entr

		 e = e.next) 		 // ①

	 {

		 Object k;

		 // 假设该 Entry 的 key 与被搜索 key 同样

		 if (e.hash == hash && ((k = e.key) == key

			 || key.equals(k)))

			 return e.value;

	 }

	 return null;

 }

从上面代码中能够看出，假设 HashMap 的每一个 bucket 里仅仅有一个 Entry 时。HashMap 能够依据索引、高速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统仅仅能必须按顺序遍历每一个 Entry，直到找到想搜索的 Entry 为止——假设恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket
中），那系统必须循环到最后才干找到该元素。

归纳起来简单地说。HashMap 在底层将 key-value 当成一个总体进行处理，这个总体就是一个 Entry 对象。HashMap 底层採用一个 Entry[] 数组来保存全部的 key-value 对，当须要存储一个 Entry 对象时，会依据 Hash 算法来决定其存储位置；当须要取出一个 Entry 时，也会依据 Hash 算法找到其存储位置，直接取出该 Entry。

由此可见：HashMap 之所以能高速存、取它所包括的 Entry，全然类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，须要时才干高速找到它。

当创建 HashMap 时。有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子能够降低 Hash 表（就是那个 Entry 数组）所占用的内存空间。但会添加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会添加 Hash 表所占用的内存空间。

掌握了上面知识之后，我们能够在创建 HashMap 时依据实际须要适当地调整 load factor 的值。假设程序比較关心空间开销、内存比較紧张，能够适当地添加负载因子；假设程序比較关心时间开销。内存比較宽裕则能够适当的降低负载因子。通常情况下，程序猿无需改变负载因子的值。

假设開始就知道 HashMap 会保存多个 key-value 对。能够在创建时就使用较大的初始化容量，假设 HashMap 中 Entry 的数量一直不会超过极限容量（capacity * load factor），HashMap 就无需调用 resize() 方法又一次分配 table 数组。从而保证较好的性能。当然，開始就将初始容量设置太高可能会浪费空间（系统须要创建一个长度为 capacity 的 Entry 数组）。因此创建 HashMap 时初始化容量设置也须要小心对待。

4. HashSet工作原理

----------------------------------------------------

对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层採用 HashMap 来保存全部元素。因此 HashSet 的实现比較简单，查看 HashSet 的源码，能够看到例如以下代码：

 public class HashSet<E>

	 extends AbstractSet<E>

	 implements Set<E>, Cloneable, java.io.Serializable

 {

	 // 使用 HashMap 的 key 保存 HashSet 中全部元素

	 private transient HashMap<E,Object> map;

	 // 定义一个虚拟的 Object 对象作为 HashMap 的 value

	 private static final Object PRESENT = new Object();

	 ...

	 // 初始化 HashSet，底层会初始化一个 HashMap

	 public HashSet()

	 {

		 map = new HashMap<E,Object>();

	 }

	 // 以指定的 initialCapacity、loadFactor 创建 HashSet

	 // 事实上就是以相应的參数创建 HashMap

	 public HashSet(int initialCapacity, float loadFactor)

	 {

		 map = new HashMap<E,Object>(initialCapacity, loadFactor);

	 }

	 public HashSet(int initialCapacity)

	 {

		 map = new HashMap<E,Object>(initialCapacity);

	 }

	 HashSet(int initialCapacity, float loadFactor, boolean dummy)

	 {

		 map = new LinkedHashMap<E,Object>(initialCapacity

			 , loadFactor);

	 }

	 // 调用 map 的 keySet 来返回全部的 key

	 public Iterator<E> iterator()

	 {

		 return map.keySet().iterator();

	 }

	 // 调用 HashMap 的 size() 方法返回 Entry 的数量，就得到该 Set 里元素的个数

	 public int size()

	 {

		 return map.size();

	 }

	 // 调用 HashMap 的 isEmpty() 推断该 HashSet 是否为空，

	 // 当 HashMap 为空时，相应的 HashSet 也为空

	 public boolean isEmpty()

	 {

		 return map.isEmpty();

	 }

	 // 调用 HashMap 的 containsKey 推断是否包括指定 key

	 //HashSet 的全部元素就是通过 HashMap 的 key 来保存的

	 public boolean contains(Object o)

	 {

		 return map.containsKey(o);

	 }

	 // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap

	 public boolean add(E e)

	 {

		 return map.put(e, PRESENT) == null;

	 }

	 // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中相应的元素

	 public boolean remove(Object o)

	 {

		 return map.remove(o)==PRESENT;

	 }

	 // 调用 Map 的 clear 方法清空全部 Entry。也就清空了 HashSet 中全部元素

	 public void clear()

	 {

		 map.clear();

	 }

	 ...

 }

由上面源程序能够看出。HashSet 的实现事实上很easy。它仅仅是封装了一个 HashMap 对象来存储全部的集合元素，全部放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT。它是一个静态的 Object 对象。

HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的。因此 HashSet 和 HashMap 两个集合在实现本质上是同样的。

HashMap 的 put 与 HashSet 的 add

因为 HashSet 的 add() 方法加入集合元素时实际上转变为调用 HashMap 的 put() 方法来加入 key-value 对，当新放入 HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 同样（hashCode() 返回值相等。通过 equals 比較也返回 true），新加入的 Entry 的 value 将覆盖原来 Entry 的 value，但 key 不会有不论什么改变，因此假设向 HashSet 中加入一个已经存在的元素。新加入的集合元素（底层由
HashMap 的 key 保存）不会覆盖已有的集合元素。

掌握上面理论知识之后，接下来看一个演示样例程序，測试一下自己是否真正掌握了 HashMap 和 HashSet 集合的功能。

以下这个程序事实上，我在上篇博客《探索equals()和hashCode()方法》中已经讲得非常清楚了，可是因为比較重要。我就再把他写一遍。

主要说明的就是重写equals()方法时。就必须重写hashCode()方法。

 class Name

{

    private String first;

    private String last; 

    public Name(String first, String last)

    {

        this.first = first;

        this.last = last;

    } 

    public boolean equals(Object o)

    {

        if (this == o)

        {

            return true;

        } 

	if (o.getClass() == Name.class)

        {

            Name n = (Name)o;

            return n.first.equals(first)

                && n.last.equals(last);

        }

        return false;

    }

}

public class HashSetTest

{

    public static void main(String[] args)

    {

        Set<Name> s = new HashSet<Name>();

        s.add(new Name("abc", "123"));

        System.out.println(

            s.contains(new Name("abc", "123")));

    }

}

上面程序中向 HashSet 里加入了一个 new Name("abc", "123") 对象之后。马上通过程序推断该 HashSet 是否包括一个 new Name("abc", "123") 对象。

粗看上去，非常easy以为该程序会输出 true。

实际执行上面程序将看到程序输出 false，这是由于 HashSet 推断两个对象相等的标准除了要求通过 equals() 方法比較返回 true 之外，还要求两个对象的 hashCode() 返回值相等。

而上面程序没有重写 Name 类的 hashCode() 方法，两个 Name 对象的 hashCode() 返回值并不同样，因此 HashSet 会把它们当成 2 个对象处理。因此程序返回 false。

由此可见。当我们试图把某个类的对象当成 HashMap 的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的 equals(Object obj) 方法和 hashCode() 方法非常重要，并且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值同样时，它们通过 equals() 方法比較也应该返回 true。通常来说，全部參与计算 hashCode() 返回值的关键属性。都应该用于作为 equals()
比較的标准。

hashCode() 和 equals()

例如以下程序就正确重写了 Name 类的 hashCode() 和 equals() 方法，程序例如以下：

class Name

{

    private String first;

    private String last;

    public Name(String first, String last)

    {

        this.first = first;

        this.last = last;

    }

    // 依据 first 推断两个 Name 是否相等

    public boolean equals(Object o)

    {

        if (this == o)

        {

            return true;

        }

        if (o.getClass() == Name.class)

        {

            Name n = (Name)o;

            return n.first.equals(first);

        }

        return false;

    } 

    // 依据 first 计算 Name 对象的 hashCode() 返回值

    public int hashCode()

    {

        return first.hashCode();

    }

    public String toString()

    {

        return "Name[first=" + first + ", last=" + last + "]";

    }

 } 

 public class HashSetTest2

 {

    public static void main(String[] args)

    {

        HashSet<Name> set = new HashSet<Name>();

        set.add(new Name("abc" , "123"));

        set.add(new Name("abc" , "456"));

        System.out.println(set);

    }

}

上面程序中提供了一个 Name 类。该 Name 类重写了 equals() 和 toString() 两个方法，这两个方法都是依据 Name 类的 first 实例变量来推断的，当两个 Name 对象的 first 实例变量相等时。这两个 Name 对象的 hashCode() 返回值也同样。通过 equals() 比較也会返回 true。

程序主方法先将第一个 Name 对象加入到 HashSet 中，该 Name 对象的 first 实例变量值为"abc"，接着程序再次试图将一个 first 为"abc"的 Name 对象加入到 HashSet 中，非常明显。此时没法将新的 Name 对象加入到该 HashSet 中，由于此处试图加入的 Name 对象的 first 也是" abc"，HashSet 会推断此处新增的 Name 对象与原有的 Name 对象同样，因此无法加入进入。程序在①号代码处输出
set 集合时将看到该集合里仅仅包括一个 Name 对象，就是第一个、last 为"123"的 Name 对象。

5. 常见问题

--------------------------------------------

“你知道HashMap的工作原理吗？” “你知道HashMap的get()方法的工作原理吗？”

答：“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。

”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象。作为Map.Entry。这一点有助于理解获取对象的逻辑。

假设你没有意识到这一点，或者错误的觉得只只在bucket中存储值的话，你将不会回答怎样从HashMap中获取对象的逻辑。

这个答案相当的正确。也显示出面试者确实知道hashing以及HashMap的工作原理。

“当两个对象的hashcode同样会发生什么？” 从这里開始。真正的困惑開始了。一些面试者会回答由于hashcode同样，所以两个对象是相等的，HashMap将会抛出异常，或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法。并告诉他们两个对象就算hashcode同样，可是它们可能并不相等。一些面试者可能就此放弃。而另外一些还能继续挺进，他们回答“由于hashcode同样，所以它们的bucket位置同样，‘碰撞’会发生。由于HashMap使用链表存储对象，这个Entry(包括有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理，尽管有非常多种处理碰撞的方法，这样的方法是最简单的，也正是HashMap的处理方法。

但故事还没有完结。面试官会继续问：

“假设两个键的hashcode同样，你怎样获取值对象？” 面试者会回答：当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。面试官提醒他假设有两个值对象储存在同一个bucket，他给出答案:将会遍历链表直到找到值对象。

面试官会问由于你并没有值对象去比較。你是怎样确定确定找到值对象的？除非面试者直到HashMap在链表中存储的是键值对。否则他们不可能回答出这一题。

当中一些记得这个重要知识点的面试者会说，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，终于找到要找的值对象。完美的答案！

很多情况下。面试者会在这个环节中出错。由于他们混淆了hashCode()和equals()方法。由于在此之前hashCode()屡屡出现。而equals()方法只在获取值对象的时候才出现。一些优秀的开发人员会指出使用不可变的、声明作final的对象，而且採用合适的equals()和hashCode()方法的话，将会降低碰撞的发生，提高效率。不可变性使得可以缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这种wrapper类作为键是很好的选择。

假设你觉得到这里已经完结了，那么听到以下这个问题的时候。你会大吃一惊。

“假设HashMap的大小超过了负载因子(load factor)定义的容量。怎么办？”除非你真正知道HashMap的工作原理。否则你将回答不出这道题。

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其他集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来又一次调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing。由于它调用hash方法找到新的bucket位置。假设你可以回答这道问题，以下的问题来了：

“你了解又一次调整HashMap大小存在什么问题吗？”你可能回答不上来。这时面试官会提醒你当多线程的情况下，可能产生条件竞争(race condition)。

当又一次调整HashMap大小的时候，确实存在条件竞争。由于假设两个线程都发现HashMap须要又一次调整大小了，它们会同一时候试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，由于移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部。而是放在头部，这是为了避免尾部遍历(tail traversing)。假设条件竞争发生了。那么就死循环了。这个时候，你能够质问面试官。为什么这么奇怪。要在多线程的环境下使用HashMap呢？：）

”为什么String, Interger这种wrapper类适合作为键？“ String,
Interger这种wrapper类作为HashMap的键是再适合只是了。并且String最为经常使用。

由于String是不可变的，也是final的，并且已经重写了equals()和hashCode()方法了。其它的wrapper类也有这个特点。

不可变性是必要的，由于为了要计算hashCode()，就要防止键值改变，假设键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其它的长处如线程安全。假设你能够只通过将某个field声明成final就能保证hashCode是不变的。那么请这么做吧。由于获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是很重要的。假设两个不相等的对象返回不同的hashcode的话。那么碰撞的几率就会小些，这样就能提高HashMap的性能。

“我们能够使用自己定义的对象作为键吗？ ”这是前一个问题的延伸。

当然你可能使用不论什么对象作为键，仅仅要它遵守了equals()和hashCode()方法的定义规则，而且当对象插入到Map中之后将不会再改变了。假设这个自己定义对象时不可变的，那么它已经满足了作为键的条件，由于当它创建之后就已经不能改变了。

“我们能够使用CocurrentHashMap来取代Hashtable吗？”这是另外一个非常热门的面试题。由于ConcurrentHashMap越来越多人用了。

我们知道Hashtable是synchronized的，可是ConcurrentHashMap同步性能更好，由于它只依据同步级别对map的一部分进行上锁。

ConcurrentHashMap当然能够取代HashTable，可是HashTable提供更强的线程安全性。

看看查看《HashMap
Vs ConcurrentHashMap》Hashtable和ConcurrentHashMap的差别。

这些问题设计哪些知识点：

  • hashing的概念
  • HashMap中解决碰撞的方法
  • equals()和hashCode()的应用，以及它们在HashMap中的重要性
  • 不可变对象的优点
  • HashMap多线程的条件竞争
  • 又一次调整HashMap的大小

好吧今天的HashSet和HashMap就告一段落了。明天讲TreeSet和TreeMap。顺便介绍介绍一篇博客给大家《20道最常见的java问题(电子商务方向)》。改天我也研究研究。

Reference：

http://www.ibm.com/developerworks/cn/java/j-jtp05273/

http://javarevisited.blogspot.com/2011/09/difference-hashmap-vs-hashset-java.html

http://www.ibm.com/developerworks/cn/java/j-lo-hash/index.html



上篇博客中我们具体的分析了java集合《java中Map,List与Set的差别》。


版权声明：本文博客原创文章，博客，未经同意，不得转载。

相关文章