深入HashMap源码，线程安全性分析

### 相关源码
该章节需首先掌握hash表的数据结构相关知识。

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

下面一幅图，形象的反映出HashMap的数据结构：数组加链表实现

![](http://img.blog.csdn.net/20170321225220165)
#### 相关属性

```java    
    //默认的初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    //存储数据的Node数组，长度是2的幂。  
    transient Node<K,V>[] table;  
    //keyset 方法要返回的结果  
    transient Set<Map.Entry<K,V>> entrySet;  
    //map中保存的键值对的数量  
    transient int size;  
    //hashmap 对象被修改的次数  
    transient int modCount;  
    // 容量乘以装载因子所得结果，如果key-value的 数量等于该值，则调用resize方法，扩大容量，同时修改threshold的值。  
    int threshold;  
    //装载因子  
    final float loadFactor;  
```

#### HashMap构造函数
使用指定的初始容量和默认装载因子初始化HashMap，其中初始容量只能是2的次方数。

```java
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
```
    
#### 自动扩容
HashMap 内部的 Node 数组默认的大小是16，假设有100万个元素，那么最好的情况下每个 hash 桶里都有62500个元素，这时get(),put(),remove()等方法效率都会降低。为了解决这个问题，HashMap 提供了自动扩容机制，当元素个数达到数组大小 loadFactor 后会扩大数组的大小，在默认情况下，数组大小为16，loadFactor 为0.75，也就是说当 HashMap 中的元素超过16乘以0.75=12时，会把数组大小扩展为2*16=32，并且重新计算每个元素在新数组中的位置。

HashMap存储结构

```java
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
```

#### hash()    
  
```java
    //计算出hash值
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
```    
    
#### put方法的实现

```java
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    /**
     * key的hash值
     * key
     * value
     * onlyIfAbsent如果是true，则不修改已存在的value值
     * true
     * return value值，if none ->null
    **/
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断table是否初始化，若未初始化，使用resize()初始化table容量，并设置threshold值
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //根据hash值定位数组索引，如果对应的数组索引无值，调用newNode()方法，创建Node结点    
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //若是hash值和key值都相等，则更新相应结点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //添加treeNode结点类型的键值对    
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        创建新Node，并添加到链表尾部
                        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;
        //更新容量和threshold
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
```

#### get方法的实现

```java
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
```
    
### 线程安全问题
- 多个线程同时使用put方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程的 put 的数据被覆盖。
- 多个线程同时检测到元素个数超过数组大小* loadFactor ，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失。

### 解决方法

Hashtable，ConcurrentHashMap
,Synchronized Map

    //Hashtable
    Map<String, String> hashtable = new Hashtable<>();
    //synchronizedMap
    Map<String, String> synchronizedHashMap = Collections.synchronizedMap(new HashMap<String, String>());
    //ConcurrentHashMap
    Map<String, String> concurrentHashMap = new ConcurrentHashMap<>();
    
#### Hashtable

HashTable 源码中是使用 synchronized 来保证线程安全的，比如下面的 get 方法和 put 方法：

    public synchronized V get(Object key) {
        ···
    }
    public synchronized V put(K key, V value) {
        ···
    }
    
#### ConcurrentHashMap
http://www.cnblogs.com/dolphin0520/p/3932905.html

#### SynchronizedMap

```java
    private static class SynchronizedMap<K,V>
       implements Map<K,V>, Serializable {
       private static final long serialVersionUID = 1978198479659022715L;
       private final Map<K,V> m;     // Backing Map
       final Object      mutex;        // Object on which to synchronize
       SynchronizedMap(Map<K,V> m) {
           this.m = Objects.requireNonNull(m);
           mutex = this;
       }
       SynchronizedMap(Map<K,V> m, Object mutex) {
           this.m = m;
           this.mutex = mutex;
       }
       public int size() {
           synchronized (mutex) {return m.size();}
       }
       public boolean isEmpty() {
           synchronized (mutex) {return m.isEmpty();}
       }
       public boolean containsKey(Object key) {
           synchronized (mutex) {return m.containsKey(key);}
       }
       public boolean containsValue(Object value) {
           synchronized (mutex) {return m.containsValue(value);}
       }
       public V get(Object key) {
           synchronized (mutex) {return m.get(key);}
       }
       public V put(K key, V value) {
           synchronized (mutex) {return m.put(key, value);}
       }
       public V remove(Object key) {
           synchronized (mutex) {return m.remove(key);}
       }
       // 省略其他方法
   }
```   
其中ConcurrentHashMap性能最高

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

深入HashMap源码，线程安全性分析 #3

相关源码

相关属性

HashMap构造函数

自动扩容

hash()

put方法的实现

get方法的实现

线程安全问题

解决方法

Hashtable

ConcurrentHashMap

SynchronizedMap

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

深入HashMap源码，线程安全性分析 #3

Description

相关源码

相关属性

HashMap构造函数

自动扩容

hash()

put方法的实现

get方法的实现

线程安全问题

解决方法

Hashtable

ConcurrentHashMap

SynchronizedMap

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions