六.HashMap HashTable HashSet区别剖析总结

摘要:
HashMap中的键不能重复,因此1很容易理解。

 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,看下面的源码

 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,继续看源代码如下

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

 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     }  
 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内存初化大小不同,看看两者的源代码:

1  public Hashtable() {  
2    //从这里可以看出,默认的初始化大小11,这里的11并不是11个字节,而是11个Entry,这个Entry是  
3    //实现链表的关键结构  
4    //这里的0.75代表的是装载因子  
5 this(11, 0.75f);  
6  }  
 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,你说大吗:)

 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     }  
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的哈希值计算方法的不同:

1 //Hashtable中可以看出的是直接采用关键字的hashcode作为哈希值  
2 int hash = key.hashCode();  
3 //然后进行模运算,求出所在哗然表的位置   
4 int index = (hash & 0x7FFFFFFF) % tab.length;  
1 //HashMap中的实现  
2 //这两行代码的意思是先计算hashcode,然后再求其在哈希表的相应位置        
3 int hash = hash(key.hashCode());  
4 int i = indexFor(hash, table.length);  

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

源码如下:

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 }  
1 //求位于哈希表中的位置  
2  static int indexFor(int h, int length) {  
3      return h & (length-1);  

转载链接:http://blog.csdn.net/jianyuerensheng/article/details/51593118

Java数据机构系列:简约人生的博客

免责声明:文章转载自《六.HashMap HashTable HashSet区别剖析总结》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Sql Server 锁【四】将vue项目打包至阿里云服务器,并进行配置nginx下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

浏览器默认样式

浏览器默认样式(user agent stylesheet)+cssreset 每种浏览器都有一套默认的样式表,即user agent stylesheet,在写网页时,没有指定的样式,按浏览器内置的样式表来渲染。这是合理的,像word中也有一些预留样式,可以让我们的排版更美观整齐。不同浏览器甚至同一浏览器不同版本的默认样式是不同的。这才带来了很多的坑,让...

ios storyboard全解析 (二)

Add Player 最终的设计看上去像下面这样:#接第一部分:原帖地址简书地址 如果你想了解storyboards,那么你来对地方了.在第一篇文章第一篇文章中,你已经学到了Interface Builder的基本用法来创建和连线多个控制器,以及使用在storyboard中可以通过直接创建自定义的tableViewCell.此次storyboard系列教...

Cocos2d-x Lua 阅读Csv文件,使用数据更方便

在我的书或出售之前,我的源代码,有Csvshadow文件。 也许这是偏见。我与工作将是最长的轮廓Csv,所以,我会帮助不大喜欢它的游戏。 Csv文件,非常格式easy,也就是说,一个数据线,字段之间用逗号分隔,策划也能够方便地使用Excel进行编辑。 Csv格式的文件。解析起来也非常easy,所以自己动手写写非常快~(小若:我就喜欢拿来主义,你怎么着)...

磁力链接 结构解析

https://blog.csdn.net/cony_14/article/details/50888073 磁力链接由一组参数组成,参数间的顺序没有讲究,其格式与在HTTP链接末尾的查询字符串相同。最常见的参数是"xt",是"exact topic"的缩写,通常是一个特定文件的内容散列函数值形成的URN,例如:  magnet:?xt=urn:sha1...

RedisTemplate访问Redis数据结构(三)——Hash

HashOperations提供一系列方法操作hash。首先初始化spring工厂获得redisTemplate和opsForHash private RedisTemplate<String,Object> redisTemplate; private HashOperations<String,String,Objec...

查询速度慢的原因很多,常见如下几种

1、没有索引或者没有用到索引(这是查询慢最常见的问题,是程序设计的缺陷) 2、I/O吞吐量小,形成了瓶颈效应。 3、没有 创建计算列导致查询不优化。 4、内存不足 5、网络速度慢 6、查询出的数据量过大(可以采用多次查询,其他的方法降低数据量) 7、 锁或者死锁(这也是查询慢最常见的问题,是程序设计的缺陷)sp_lock,sp_who,活动的用户查看,原因...