小菜鸟

java菜鸟号正在起航

0%

Map

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 7.9k 阅读时长 ≈ 7 分钟

Map

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

Hashtable

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

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

1
2
3
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
1
2
3
4
5
6
7
8
9
10
11
12
@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中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

1
2
3
4
5
6
7
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数组来存储的

1
transient Node<K,V>[] table;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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决定，

1
2
3
4
5
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>
1
2
3
4
5
// 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表示按照访问顺序迭代LRU最近最少访问，值为false表示按照插入顺序迭代)

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

1
2
3
4
5
6
7
8
9
10
11
12
public LinkedHashMap() {
  super();
  accessOrder = false;
}

// LinkedHashMap的Entry比HashMap中的Node多了上一个元素before的引用和下一个元素after的引用，形成了一个双向链表
static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

LRU缓存

LRU是Least Recently Used的缩写，即最近最少使用，LRU缓存会把最近最少使用的数据移除，让给新的数据，而LinkedHashMap中有一个accessOrder可以完美的实现该操作，不过LinkedHashMap本身不会移除数据，所以需要重写removeEldestEntry方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int MAX_CACHE_SIZE;

    public LRUCache(int cacheSize) {
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        MAX_CACHE_SIZE = cacheSize;
    }
        // 移除很久未使用的数据
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_CACHE_SIZE;
    }

}

ConcurrentHashMap

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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线程安全，方法是synchronized修饰的，所以HashMap性能比Hashtable好

  • HashMap键值允许为null，Hashtable键值不允许为null

  • HashMap没有contains方法，Hashtable有contains方法，功能与containsValue相同

  • HashMap继承AbstractMap，Hashtable继承Dictionary类

  • HashMap初始容量为16，Hashtable初始容量为11；HashMap要求数组的容量一定要为2的整数幂，Hashtable不作要求；HashMap扩容是乘2，Hashtable是乘2+1

    1
    2
    3
    4
    // Hashtable 扩容
    int newCapacity = (oldCapacity << 1) + 1;
    // HashMap 扩容
    newCap = oldCap << 1

  • HashMap的Iterator迭代器是fail-fast的，而Hashtable的Enumerator是fail-safe的

  • HashMap迭代器使用的是Iterator，Hashtable使用的是Enumeration

  • hash取值方式不同，Hashtale直接使用的对象的hashCode，而HashMap会重新计算hash值

相关文章

欢迎关注我的其它发布渠道