Java面试基础篇——第六篇:常见Map类的区别

原创
2018/07/19 12:02
阅读数 1.4K

常见的map类有: HashMap, ConcurrentHashMap (Jdk1.8) , LinkedHashMap, TreeMap, Hashtable。

  1. 其中我们最常用的莫过于HashMap, 和并发情况下使用的ConcurrentHashMap了,它们的主要区别就在于HashMap是非线程安全的,而ConcurrentHashMap是线程安全的。
  2. 并发情况下可以使用HashTable和ConcurrentHashMap ,它们的区别在于:  >* ConcurrentHashMap的hash计算公式:(key.hascode()^ (key.hascode()>>> 16)) & 0x7FFFFFFF, 而 HashTable的hash计算公式:key.hascode() & 0x7FFFFFFF
  • 2.HashTable存储方式都是链表+数组,数组里面放的是当前hash的第一个数据,链表里面放的是hash冲突的数据 ,ConcurrentHashMap是数组+链表+红黑树.
  1. 线程安全的保证: HashTable是在每一个操作方法上都加上synchronized关键字来达到线程安全的目的,而ConcurrentHashMap则是通过CAS算法(CompareAndSwap)来保证线程安全。
  2. ConcurrentHashMap 放弃了分段锁,而使用了Nodo锁,减低了锁的粒度,提高了性能,并使用CAS操作来保证Node操作的原子性。但是ConcurrentHashMap的一些操作使用了synchronized锁,而不是ReentrantLock,虽然说jdk8的synchronized的性能进行了优化,但是我觉得还是使用ReentrantLock锁能更多的提高性能。
  3. 顺序的 Map 实现类:LinkedHashMap,TreeMap

LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序,TreeMap 则是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。 6. HashMap和Hashtable

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	...
	}
public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
	}
  • HashMap是继承自AbstractMap类,而HashTable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable(可复制)、Serializable(可序列化)这三个接口. 而Dictionary类是一个废弃的类。可想而知,父类被废弃,子类自然也没人用啦~~
  • Hashtable比HashMap多提供了elments() 和contains() 两个方法。 elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。 contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上,containsValue() 就只是调用了一下contains() 方法。
  • Hashtable既不支持Null key也不支持Null value。HashMap只支持一个null key ,可以有一个或多个键的值为null.
  • Hashtable是线程安全的,它的每个方法中都加入了Synchronize方法。在多线程并发的环境下,可以直接使用Hashtable,不需要自己为它的方法实现同步
  • Hashtable默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。创建时,如果给定了容量初始值,那么Hashtable会直接使用你给定的大小,而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小.
  • 计算hash值的方法不同 : Hashtable直接使用对象的hashCode. Hashtable在计算元素的位置时需要进行一次除法运算,而除法运算是比较耗时的。HashMap为了提高计算效率,将哈希表的大小固定为了2的幂,这样在取模预算时,不需要做除法,只需要做位运算。位运算比除法的效率要高很多。HashMap的效率虽然提高了,但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高.为了解决这个问题,HashMap重新根据hashcode计算hash值后,又对hash值做了一些运算来打散数据。使得取得的位置更加分散,从而减少了hash冲突。当然了,为了高效,HashMap只做了一些简单的位处理。从而不至于把使用2的幂次方带来的效率提升给抵消掉。
展开阅读全文
打赏
0
8 收藏
分享
加载中
更多评论
打赏
0 评论
8 收藏
0
分享
返回顶部
顶部