HashMap、TreeMap、Hashtable、HashSet和ConcurrentHashMap区别

深碍√TFBOYSˉ_ 2022-08-04 05:06 183阅读 0赞

**一、HashMap和TreeMap区别**

1、HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。

TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。  
  
2、HashMap、TreeMap都继承AbstractMap抽象类；TreeMap实现SortedMap接口，所以TreeMap是有序的！HashMap是无序的。  
    接口层次：  
    public interface SortedMap<K,V> extends Map<K,V>  
    public interface NavigableMap<K,V> extends SortedMap<K,V>  
    public class HashMap<K,V>     extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable  
    public class HashMap<K,V>    extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable  
      
3、两种常规Map性能  
    HashMap：适用于在Map中插入、删除和定位元素。  
    Treemap：适用于按自然顺序或自定义顺序遍历键(key)。      
  
4.总结：HashMap通常比TreeMap快一点(树和哈希表的数据结构使然)，建议多使用HashMap，在需要排序的Map时候才用TreeMap。  
  
  
**二、HashMap和Hashtable的区别**  
HashMap和Hashtable都实现了Map接口，但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有：线程安全性，同步(synchronization)，以及速度。  
  
HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。  
HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。  
另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。  
由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。  
HashMap不能保证随着时间的推移Map中的元素次序是不变的。  
  
我们能否让HashMap同步？  
HashMap可以通过下面的语句进行同步：  
Map m = Collections.synchronizeMap(hashMap);  
  
Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。  
  
  
**三、HashSet和HashMap的区别**  
    HashSet是基于HashMap实现的。

public class HashSet<E> extends AbstractSet<E>	implements Set<E>, Cloneable, java.io.Serializable
    {
        static final long serialVersionUID = -5024744406713321676L;
    
        private transient HashMap<E,Object> map;
    
        private static final Object PRESENT = new Object();
    
        public HashSet() {
            map = new HashMap<>();
        }
        public HashSet(Collection<? extends E> c) {
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
        }
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
        public boolean remove(Object o) {
            return map.remove(o)==PRESENT;
        }
        .......
    }

<table> 
 <tbody> 
  <tr> 
   <td align="center">HashMap</td> 
   <td align="center">HashSet</td> 
  </tr> 
  <tr> 
   <td>HashMap实现了Map接口</td> 
   <td>HashSet实现了Set接口</td> 
  </tr> 
  <tr> 
   <td>HashMap储存键值对</td> 
   <td>HashSet仅仅存储对象</td> 
  </tr> 
  <tr> 
   <td>使用put()方法将元素放入map中</td> 
   <td>使用add()方法将元素放入set中</td> 
  </tr> 
  <tr> 
   <td>HashMap中使用键对象来计算hashcode值&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
   <td>HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false</td> 
  </tr> 
  <tr> 
   <td>HashMap比较快，因为是使用唯一的键来获取对象</td> 
   <td>HashSet较HashMap</td> 
  </tr> 
 </tbody> 
</table>

**四、ConcurrentMap**

ConcurrentHashMap 表现区别：不可以有null键，线程安全，原子操作。一个ConcurrentHashMap 由多个segment 组成，每个segment 包含一个Entity 的数组。这里比HashMap 多了一个segment 类。该类继承了ReentrantLock 类，所以本身是一个锁。当多线程对ConcurrentHashMap 操作时，不是完全锁住map， 而是锁住相应的segment 。这样提高了并发效率。缺点：当遍历ConcurrentMap中的元素时，需要获取所有的segment 的锁，使用遍历时慢。锁的增多，占用了系统的资源。使得对整个集合进行操作的一些方法

**五、LinkedHashMap是HashMap的一个子类**

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

[ ConcurrentHashMap原理分析 ][ConcurrentHashMap_]

六、java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap.

[ConcurrentHashMap_]: http://blog.csdn.net/paincupid/article/details/47712341