HashMap,HashSet,Hashtable,Vector,ArrayList 的关系

jopen 5年前

 

这么几个比较常用的但是比较容易混淆的概念同出于 java.util 包。本文仅作几个类的浅度解析。(本文基于JDK1.7,源码来自openjdk1.7。)

├── Collection  │   ├── List │   │   ├── ArrayList  │   │   ├── Vector  │   │   └── LinkedList and so on;  │   Set  │   ├── HashSet  │   └── LinkedHashSet and so on;  └── Map      ├── Hashtable      ├── HashMap      └── WeakHashMap and so on;

Collection和Map

按理来说和这两者没有什么特别关系。然而本文中仍然将这两个混在一起:

  • 第一,HashSet,HashMap,Hashtable长得太像了,没有理由不写再一起。
  • 第二,HashSet是个Set,其实骨子里是个Map。

List

继承List的类,泛型为Integer时,注意和其他的类型不同。(因为Index是Integer)

线程安全

简单来说,List是个一维数组。Vector和ArrayList区别在于:

Vector是个线程安全的,而ArrayList不是。这点看源码可以看出来,Vector中各种synchronized,甚至连size属性都丧心病狂地synchronized了。

同样,Iterator指定Vector和ArrayList,如果中间发生变化则会抛出ConcurrentModificationException异常。不仅仅是List,很多地方的Iterator都有这个异常,

自增大小

ArrayList没办法设置自增大小,但是仍然可以自增。Vector可以设置自增大小。

ArrayList的自增函数:

Vector的自增函数:

private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?                     capacityIncrement : oldCapacity);    //在这里,如果没有设置自增大小的话,那么默认自增大小则是原来的Vector大小。    if (newCapacity - minCapacity < 0)      newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)      newCapacity = hugeCapacity(minCapacity);    elementData = Arrays.copyOf(elementData, newCapacity);  }

ArrayList自增函数:
private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    int newCapacity = oldCapacity + (oldCapacity >> 1);    //新长度则是旧长度的大小加上一个移位运算(一半的大小)。    if (newCapacity - minCapacity < 0)      newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)      newCapacity = hugeCapacity(minCapacity);    // minCapacity is usually close to size, so this is a win:    elementData = Arrays.copyOf(elementData, newCapacity);  }

所以可以简单的认为Vector默认自增一倍的长度,ArrayList则是默认自增一半的长度。

同样,对他们的源码分析:Vector可以设置自增大小,而ArrayList则无法设置(没有这个构造方法)。

public Vector(int initialCapacity, int capacityIncrement)

最后,可以List list=new ArrayList<>();,然后list=new Vector<>();,使用基类List可以实现ArrayList和Vector的快速赋值。

Map

Map可以当成是简单的“Key-Value”数据库,例如memcached和redis。

Hashtable基于Directory,有种说法是Directory已经过时,所以更推荐使用Map。

线程安全

Hashtable也是线程安全的,和Vector一样,连size函数都丧心病狂地同步了。

public synchronized int size() {                                                                                                                   return count;  }     

HashMap不是线程安全的,当然也可以用其他的黑科技实现同步,例如SynchronizedMap和ConcurrentHashMap。那个以后再说……

空值

HashMap允许在Key和Value中都出现null值。例如:

v.toString()  {null=null, 1=66, 2=null, 3=4d, 4=0f, 5=null}

而Hashtable则不允许K/V的任何一个出现null值,但是允许空字符串。

Hashtable<String,String> v=new Hashtable<String,String>();  v.put("3s",null);

直接报错:java.lang.NullPointerException。这个和内部实现有关,Hashtable需要用到hashCode,所以必须要确保K/V不为null。

相关代码写死在源码里:

public synchronized V put(K key, V value) {   // Make sure the value is not null   if (value == null) {       throw new NullPointerException();   }   //下面对hashCode做点事情。

Set

HashSet本质上是一个Collection,类似于List,是列表/集合,不是K-V的Map,但是它骨子里是一个HashMap……

这么说可能会更易于理解:HashSet对外是“类”的集合,实际上是内部维护了一个HashMap进行实现。

实际上存储的是两个:hashCode和类本身(字符串/自定义类等)。

HashSet进行add的时候,会先进行验证hashCode:(HashSet进行add操作实际上是对Map的put操作)

public V put(K key, V value) {    if (table == EMPTY_TABLE) {      inflateTable(threshold);    }    if (key == null)      return putForNullKey(value);    int hash = hash(key);//本函数里有hashCode    int i = indexFor(hash, table.length);    for (Entry<K,V> e = table[i]; e != null; e = e.next) {      Object k;      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {        V oldValue = e.value;        e.value = value;        e.recordAccess(this);        return oldValue;      }    }    modCount++;    addEntry(hash, key, value, i);    return null;  }

一个对HashSet的自定义类的操作:

 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")));      }    }   

代码来自 java中HashSet详解

粗看上去是会返回true的,实际返回false。因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外,还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法,两个 Name 对象的 hashCode() 返回值并不相同,因此 HashSet 会把它们当成 2 个对象处理,因此程序返回 false。如果想返回true,需要重写equals方法和hashCode方法。

至于hashCode,就是另一篇文章才解释得清的了。

集合操作

Set其实做集合操作更加简单。例如:

import java.util.*;  public class SetOperation {         public static void main(String[] args) {    Set<Integer> result = new HashSet<Integer>();    Set<Integer> set1 = new HashSet<Integer>(){{        add(1);        add(3);        add(5);    }};    Set<Integer> set2 = new HashSet<Integer>(){{        add(1);        add(2);        add(3);    }};    result.clear();    result.addAll(set1);    result.retainAll(set2);    System.out.println("交集:"+result);    result.clear();    result.addAll(set1);    result.removeAll(set2);    System.out.println("差集:"+result);    result.clear();    result.addAll(set1);    result.addAll(set2);    System.out.println("并集:"+result);          }  }

输出:

交集:[1, 3] 差集:[5] 并集:[1, 2, 3, 5] 

参考文档

hashSet中的equals方法和hashCode方法