HashMap HashTable HashSet区别剖析总结

深藏阁楼爱情的钟 2022-08-23 03:46 201阅读 0赞

HashMap、HashSet、HashTable之间的区别是Java程序员的一个常见面试题目，在此仅以此博客记录，并深入源代码进行分析：

在分析之前，先将其区别列于下面：

1.  1、HashSet底层采用的是HashMap进行实现的，但是没有key-value，只有HashMap的key set的视图，HashSet不容许重复的对象
2.  Hashtable是基于Dictionary类的，而HashMap是基于Map接口的一个实现
3.  Hashtable里默认的方法是同步的，而HashMap则是非同步的，因此Hashtable是多线程安全的
4.  HashMap可以将空值作为一个表的条目的key或者value,HashMap中由于键不能重复，因此只有一条记录的Key可以是空值，而value可以有多个为空，但HashTable不允许null值(键与值均不行)
5.  内存初始大小不同，HashTable初始大小是11，而HashMap初始大小是16
6.  内存扩容时采取的方式也不同，Hashtable采用的是2\*old+1,而HashMap是2\*old。
7.  哈希值的计算方法不同，Hashtable直接使用的是对象的hashCode,而HashMap则是在对象的hashCode的基础上还进行了一些变化

源代码分析：

**对于区别1，看下面的源码**

**\[java\]**  [view plain][] [copy][view plain]

1.  //HashSet类的部份源代码  
2.  **public** **class** HashSet<E>  
3.      **extends** AbstractSet<E>  
4.      **implements** Set<E>, Cloneable, java.io.Serializable  
5.  \{   //用于类的序列化，可以不用管它  
6.      **static** **final** **long** serialVersionUID = -5024744406713321676L;  
7.      //从这里可以看出HashSet类里面真的是采用HashMap来实现的  
8.      **private** **transient** HashMap<E,Object> map;  
9.    
10.     // Dummy value to associate with an Object in the backing Map  
11.     //这里是生成一个对象，生成这个对象的作用是将每一个键的值均关联于此对象，以满足HashMap的键值对  
12.     **private** **static** **final** Object PRESENT = **new** Object();  
13.   
14.     /\*\* 
15.      \* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has 
16.      \* default initial capacity (16) and load factor (0.75). 
17.      \*/  
18.     //这里是一个构造函数，开构生成一个HashMap对象，用来存放数据  
19.     **public** HashSet() \{  
20.     map = **new** HashMap<E,Object>();  
21.     \}

从上面的代码中得出的结论是HashSet的确是采用HashMap来实现的，而且每一个键都关键同一个Object类的对象，因此键所关联的值没有意义，真正有意义的是键。而HashMap里的键是不允许重复的，因此1也就很容易明白了。

**对于区别2，继续看源代码如下**

**\[java\]**  [view plain][] [copy][view plain]

1.  //从这里可以看得出Hashtable是继承于Dictionary,实现了Map接口  
2.  **public** **class** Hashtable<K,V>  
3.      **extends** Dictionary<K,V>  
4.      **implements** Map<K,V>, Cloneable, java.io.Serializable \{

**\[java\]**  [view plain][] [copy][view plain]

1.  //这里可以看出的是HashMap是继承于AbstractMap类，实现了Map接口  
2.  //因此与Hashtable继承的父类不同  
3.  **public** **class** HashMap<K,V>  
4.      **extends** AbstractMap<K,V>  
5.      **implements** Map<K,V>, Cloneable, Serializable

**区别3，找一个具有针对性的方法看看，这个方法就是put**

**\[java\]**  [view plain][] [copy][view plain]

1.  //Hashtable里的向集体增加键值对的方法，从这里可以明显看到的是  
2.  //采用了synchronized关键字，这个关键字的作用就是用于线程的同步操作  
3.  //因此下面这个方法对于多线程来说是安全的，但这会影响效率     
4.  **public** **synchronized** V put(K key, V value) \{  
5.      // Make sure the value is not null  
6.      //如果值为空的，则会抛出异常  
7.      **if** (value == **null**) \{  
8.          **throw** **new** NullPointerException();  
9.      \}  
10.   
11.     // Makes sure the key is not already in the hashtable.  
12.     Entry tab\[\] = table;  
13.     //获得键值的hashCode,从这里也可以看得出key!=null,否则的话会抛出异常的呦  
14.     **int** hash = key.hashCode();  
15.     //获取键据所在的哈希表的位置  
16.     **int** index = (hash & 0x7FFFFFFF) % tab.length;  
17.     //从下面这个循环中可以看出的是，内部实现采用了链表，即桶状结构  
18.     **for** (Entry<K,V> e = tab\[index\] ; e != **null** ; e = e.next) \{  
19.         //如果向Hashtable中增加同一个元素时，则会重新更新元素的值   
20.         **if** ((e.hash == hash) && e.key.equals(key)) \{  
21.                 V old = e.value;  
22.                 e.value = value;  
23.                 **return** old;  
24.         \}  
25.     \}  
26.     //后面的暂时不用管它，大概的意思就是内存的个数少于某个阀值时，进行重新分配内存  
27.     modCount++;  
28.     **if** (count >= threshold) \{  
29.         // Rehash the table if the threshold is exceeded  
30.         rehash();  
31.   
32.             tab = table;  
33.             index = (hash & 0x7FFFFFFF) % tab.length;  
34.     \}

**\[java\]**  [view plain][] [copy][view plain]

1.  //HashMap中的实现则相对来说要简单的很多了，如下代码  
2.  //这里的代码中没有synchronize关键字，即可以看出，这个关键函数不是线程安全的  
3.      **public** V put(K key, V value) \{  
4.      //对于键是空时，将向Map中放值一个null-value构成的键值对  
5.      //对值却没有进行判空处理，意味着可以有多个具有键，键所对应的值却为空的元素。  
6.          **if** (key == **null**)  
7.              **return** putForNullKey(value);  
8.      //算出键所在的哈希表的位置  
9.          **int** hash = hash(key.hashCode());  
10.         **int** i = indexFor(hash, table.length);  
11.     //同样从这里可以看得出来的是采用的是链表结构，采用的是桶状  
12.         **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{  
13.             Object k;  
14.             //对于向集体中增加具有相同键的情况时，这里可以看出，并不增加进去，而是进行更新操作  
15.             **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{  
16.                 V oldValue = e.value;  
17.                 e.value = value;  
18.                 e.recordAccess(**this**);  
19.                 **return** oldValue;  
20.             \}  
21.         \}  
22.         //开始增加元素  
23.         modCount++;  
24.         addEntry(hash, key, value, i);  
25.         **return** **null**;  
26.     \}

**区别4在上面的代码中，已经分析了，可以再细看一下**

**区别5内存初化大小不同，看看两者的源代码：**

**\[java\]**  [view plain][] [copy][view plain]

1.   **public** Hashtable() \{  
2.     //从这里可以看出，默认的初始化大小11，这里的11并不是11个字节，而是11个Entry,这个Entry是  
3.     //实现链表的关键结构  
4.     //这里的0.75代表的是装载因子  
5.  **this**(11, 0.75f);  
6.   \}

**\[java\]**  [view plain][] [copy][view plain]

1.  //这里均是一些定义  
2.   **public** HashMap() \{  
3.   //这个默认的装载因子也是0.75  
4.       **this**.loadFactor = DEFAULT\_LOAD\_FACTOR;  
5.   //默认的痤为0.75\*16  
6.       threshold = (**int**)(DEFAULT\_INITIAL\_CAPACITY \* DEFAULT\_LOAD\_FACTOR);  
7.   //这里开始是默认的初始化大小，这里大小是16  
8.       table = **new** Entry\[DEFAULT\_INITIAL\_CAPACITY\];  
9.       init();  
10.  \}

从上面的代码中，可以看出的是两者的默认大小是不同的，一个是11，一个是16

**区别6内存的扩容方式，**看一看源代码也是很清楚的，其实区别是不大的，一个是2\*oldCapacity+1, 一个是2\*oldCapacity,你说大吗:）

**\[java\]**  [view plain][] [copy][view plain]

1.  //Hashtable中调整内存的函数，这个函数没有synchronize关键字，但是protected呦  
2.  **protected** **void** rehash() \{  
3.      //获取原来的表大小  
4.      **int** oldCapacity = table.length;  
5.      Entry\[\] oldMap = table;  
6.    //设置新的大小为2\*oldCapacity+1  
7.      **int** newCapacity = oldCapacity \* 2 + 1;  
8.      //开设空间  
9.      Entry\[\] newMap = **new** Entry\[newCapacity\];  
10.   //以下就不用管了。。。  
11.     modCount++;  
12.     threshold = (**int**)(newCapacity \* loadFactor);  
13.     table = newMap;  
14.   
15.     **for** (**int** i = oldCapacity ; i-- > 0 ;) \{  
16.         **for** (Entry<K,V> old = oldMap\[i\] ; old != **null** ; ) \{  
17.         Entry<K,V> e = old;  
18.         old = old.next;  
19.   
20.         **int** index = (e.hash & 0x7FFFFFFF) % newCapacity;  
21.         e.next = newMap\[index\];  
22.         newMap\[index\] = e;  
23.         \}  
24.     \}  
25.     \}

**\[java\]**  [view plain][] [copy][view plain]

1.  //HashMap中要简单的多了，看看就知道了  
2.  **void** addEntry(**int** hash, K key, V value, **int** bucketIndex) \{  
3.  Entry<K,V> e = table\[bucketIndex\];  
4.         table\[bucketIndex\] = **new** Entry<K,V>(hash, key, value, e);  
5.         //如果超过了阀值  
6.         **if** (size++ >= threshold)  
7.         //就将大小设置为原来的2倍  
8.             resize(2 \* table.length);  
9.     \}

**对于区别7的哈希值计算方法的不同：**

**\[java\]**  [view plain][] [copy][view plain]

1.  //Hashtable中可以看出的是直接采用关键字的hashcode作为哈希值  
2.  **int** hash = key.hashCode();  
3.  //然后进行模运算，求出所在哗然表的位置   
4.  **int** index = (hash & 0x7FFFFFFF) % tab.length;

**\[java\]**  [view plain][] [copy][view plain]

1.  //HashMap中的实现  
2.  //这两行代码的意思是先计算hashcode,然后再求其在哈希表的相应位置        
3.  **int** hash = hash(key.hashCode());  
4.  **int** i = indexFor(hash, table.length);

上面的HashMap中可以看出关键在两个函数hash与indexFor

源码如下:

**\[java\]**  [view plain][] [copy][view plain]

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.      //这个我就不多说了，>>>这个是无符号右移运算符，可以理解为无符号整型  
6.      h ^= (h >>> 20) ^ (h >>> 12);  
7.      **return** h ^ (h >>> 7) ^ (h >>> 4);  
8.  \}

**\[java\]**  [view plain][] [copy][view plain]

1.  //求位于哈希表中的位置  
2.   **static** **int** indexFor(**int** h, **int** length) \{  
3.       **return** h & (length-1);

[view plain]: http://blog.csdn.net/zwjlpeng/article/details/9746425#

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap底层实现原理？HashMap与HashTable区别？HashMap与HashSet区别？

①HashMap的工作原理： HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的

╰半橙微兮°/ 2022年12月20日 12:35/ 0 赞/ 192 阅读

相关 Map HashMap HashTable Set HashSet

一.HashMap和HashTable都实现了Map接口，保存的是Key-value。HashSet实现了Set接口。二.HashMap和HashTable继承的父类不同，

冷不防/ 2022年08月26日 15:17/ 0 赞/ 198 阅读

相关 HashMap HashTable HashSet区别剖析总结

HashMap、HashSet、HashTable之间的区别是Java程序员的一个常见面试题目，在此仅以此博客记录，并深入源代码进行分析：在分析之前，先将其区别列于

深藏阁楼爱情的钟/ 2022年08月23日 03:46/ 0 赞/ 202 阅读

相关 HashMap、TreeMap、Hashtable、HashSet和ConcurrentHashMap区别

一、HashMap和TreeMap区别 1、HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。 TreeMap基于红黑树（一种自平衡二叉查找树）实现的

深碍√TFBOYSˉ_/ 2022年08月04日 05:06/ 0 赞/ 248 阅读

相关 HashMap底层实现原理/HashMap与HashTable区别/HashMap与HashSet区别

①HashMap的工作原理 HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的h

旧城等待，/ 2022年06月08日 03:43/ 0 赞/ 306 阅读

相关 HashMap和Hashtable的区别总结

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，在只有一

青旅半醒/ 2022年06月06日 09:19/ 0 赞/ 214 阅读

相关 HashMap、TreeMap、Hashtable、HashSet和ConcurrentHashMap区别

一、HashMap和TreeMap区别 1、HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。 TreeMap基于红黑树（一种自平衡二叉查找树）实现的

浅浅的花香味﹌/ 2022年06月01日 12:19/ 0 赞/ 293 阅读

相关 hashmap ，hashtable， hashset 的containskey比较

一直以为这三个结构的containskey算法是一样的都是通过计算散列值计算存不存在，今天没事查了下源代码详细看下。 hashmap： public boolean

痛定思痛。/ 2022年05月19日 09:34/ 0 赞/ 236 阅读

相关 HashMap、HashTable、HashSet

关于HashMap 首先要清楚HashMap的存储结构，如下图所示： ![70][] 图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点

布满荆棘的人生/ 2022年05月13日 04:30/ 0 赞/ 204 阅读

相关 HashMap、Hashtable、HashSet的对比

转载自[https://www.cnblogs.com/lzrabbit/p/3721067.html\h1][https_www.cnblogs.com_lzrabbit_p

迷南。/ 2021年12月04日 02:34/ 0 赞/ 246 阅读