Map

Map是一个接口，下面介绍一下Map接口的一些常用的实现类

Hashtable

Hashtable是在java1.0中实现的最早的Map，继承自Dictionary类，底层使用的哈希表，是线程安全的，因为该类中的方法都是用了synchronized修饰，但是也因此存在了效率问题

如果想要使用具有用线程安全能力的map可以使用Collections.synchronizedMap()方法或者使用ConcurrentHashMap

public class Hashtable<K,V>    extends Dictionary<K,V>    implements Map<K,V>, Cloneable, java.io.Serializable {

@SuppressWarnings("unchecked")public synchronized V get(Object key) {  Entry<?,?> tab[] = table;  int hash = key.hashCode();  int index = (hash & 0x7FFFFFFF) % tab.length;  for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {    if ((e.hash == hash) && e.key.equals(key)) {      return (V)e.value;    }  }  return null;}

内部所使用的是一个Entry数组进行存储的，Entry实际上是一个链表，key和value都保存在Entry中

/** * The hash table data.*/private transient Entry<?,?>[] table;private static class Entry<K,V> implements Map.Entry<K,V> {  final int hash;  final K key;  V value;  Entry<K,V> next;  protected Entry(int hash, K key, V value, Entry<K,V> next) {    this.hash = hash;    this.key =  key;    this.value = value;    this.next = next;  }  @SuppressWarnings("unchecked")  protected Object clone() {    return new Entry<>(hash, key, value,                       (next==null ? null : (Entry<K,V>) next.clone()));  }  // Map.Entry Ops  public K getKey() {    return key;  }  public V getValue() {    return value;  }  public V setValue(V value) {    if (value == null)      throw new NullPointerException();    V oldValue = this.value;    this.value = value;    return oldValue;  }  public boolean equals(Object o) {    if (!(o instanceof Map.Entry))      return false;    Map.Entry<?,?> e = (Map.Entry<?,?>)o;    return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&      (value==null ? e.getValue()==null : value.equals(e.getValue()));  }  public int hashCode() {    return hash ^ Objects.hashCode(value);  }  public String toString() {    return key.toString()+"="+value.toString();  }}

HashTable的key和value都不允许为null，可以看到在put操作的时候，会校验value值是否为null，而且会获取key的hashCode，所以key和value都不可以为null

public synchronized V put(K key, V value) {  // Make sure the value is not null  if (value == null) {    throw new NullPointerException();  }  // Makes sure the key is not already in the hashtable.  Entry<?,?> tab[] = table;  int hash = key.hashCode();  int index = (hash & 0x7FFFFFFF) % tab.length;  @SuppressWarnings("unchecked")  Entry<K,V> entry = (Entry<K,V>)tab[index];  for(; entry != null ; entry = entry.next) {    if ((entry.hash == hash) && entry.key.equals(key)) {      V old = entry.value;      entry.value = value;      return old;    }  }  addEntry(hash, key, value, index);  return null;}

HashMap

当前用的最多的还是HashMap

HashMap是线程不安全的，底层也是哈希表，与HashTable不同的是，key和value可以为null

可以看到在put方法取key的hash值时对key进行了判断，key为null的话，hash值为0

public V put(K key, V value) {  return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {  int h;  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

HashMap的底层使用Node数组来存储的

transient Node<K,V>[] table;

HashMap如果出现hash冲突的话，会在放到链表中，但是如果hash冲突过多的话，会导致链表太长，查询时性能会下降，在链表长度超过一定值时，会进行结构改造，将链表转换为树状结构，这里TREEIFY_THRESHOLD是8

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {  Node<K,V>[] tab; Node<K,V> p; int n, i;  if ((tab = table) == null || (n = tab.length) == 0) // table为null，进行初始化    n = (tab = resize()).length;  if ((p = tab[i = (n - 1) & hash]) == null)    tab[i] = newNode(hash, key, value, null);  else {    Node<K,V> e; K k;    if (p.hash == hash &&        ((k = p.key) == key || (key != null && key.equals(k))))      e = p;    else if (p instanceof TreeNode)      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);    else {      // 遍历map      for (int binCount = 0; ; ++binCount) {        // 遍历完依旧没有该key，需要添加一个新的节点        if ((e = p.next) == null) {          p.next = newNode(hash, key, value, null);          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st            // 链表转为树状结构            treeifyBin(tab, hash);          break;        }        if (e.hash == hash &&            ((k = e.key) == key || (key != null && key.equals(k))))          break;        p = e;      }    }    if (e != null) { // existing mapping for key      V oldValue = e.value;      if (!onlyIfAbsent || oldValue == null)        e.value = value;      afterNodeAccess(e);      return oldValue;    }  }  ++modCount;  if (++size > threshold)    resize();  afterNodeInsertion(evict);  return null;}

TreeMap

TreeMap底层是红黑树，实现了SortedMap接口，顺序由key控制(默认是按key进行，key必须实现Comparable接口或者在构造器传入自定义的Comparator)，通过Comparator或者Comparable决定，

public class TreeMap<K,V>    extends AbstractMap<K,V>    implements NavigableMap<K,V>, Cloneable, java.io.Serializable public interface NavigableMap<K,V> extends SortedMap<K,V>

// key进行比较final int compare(Object k1, Object k2) {    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)        : comparator.compare((K)k1, (K)k2);}

LinkedHashMap

LinkedHashMap属于一个双向链表，通过键值来维护，遍历顺序为插入顺序，相当于一个有顺序的HashMap

增加了两个属性来保证迭代顺序，分别是双向链表的头结点header和标志位accessOrder(值为true表示按照访问顺序迭代，值为false表示按照插入顺序迭代)

默认构造器accessOrder为false是按照插入顺序迭代的

public LinkedHashMap() {  super();  accessOrder = false;}

ConcurrentHashMap

ConcurrentHashMap是并发包下的类，属于线程安全的HashMap。

java8中ConcurrentHashMap放弃了Segment分段加锁的机制，采用了Node+CAS+Syncronized保证并发安全。

大量地采用了自旋+CAS操作

key和value都不可以为null，否则会抛出空指针异常

final V putVal(K key, V value, boolean onlyIfAbsent) {        if (key == null || value == null) throw new NullPointerException();        int hash = spread(key.hashCode());        int binCount = 0;        for (Node<K,V>[] tab = table;;) {            Node<K,V> f; int n, i, fh;            if (tab == null || (n = tab.length) == 0)                tab = initTable();            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {                if (casTabAt(tab, i, null,                             new Node<K,V>(hash, key, value, null)))                    break;                   // no lock when adding to empty bin            }            else if ((fh = f.hash) == MOVED)                tab = helpTransfer(tab, f);            else {                V oldVal = null;                synchronized (f) {                    if (tabAt(tab, i) == f) {                        if (fh >= 0) {                            binCount = 1;                            for (Node<K,V> e = f;; ++binCount) {                                K ek;                                if (e.hash == hash &&                                    ((ek = e.key) == key ||                                     (ek != null && key.equals(ek)))) {                                    oldVal = e.val;                                    if (!onlyIfAbsent)                                        e.val = value;                                    break;                                }                                Node<K,V> pred = e;                                if ((e = e.next) == null) {                                    pred.next = new Node<K,V>(hash, key,                                                              value, null);                                    break;                                }                            }                        }                        else if (f instanceof TreeBin) {                            Node<K,V> p;                            binCount = 2;                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                                           value)) != null) {                                oldVal = p.val;                                if (!onlyIfAbsent)                                    p.val = value;                            }                        }                    }                }                if (binCount != 0) {                    if (binCount >= TREEIFY_THRESHOLD)                        treeifyBin(tab, i);                    if (oldVal != null)                        return oldVal;                    break;                }            }        }        addCount(1L, binCount);        return null;    }

HashMap和HashTable的区别HashMap线程不安全，HashTable线程安全HashMap性能比HashTable好HashMap键值允许为null，HashTable键值不允许为nullHashMap继承AbstractMap，HashTable继承Dictionary类HashMap初始容量为16，HashTable初始容量为11HashMap扩容是翻一倍，HashTable是翻一倍+1HashMap的Iterator迭代器是fail-fast的，而HashTable的Enumerator是fail-safe的