HashMap实现原理分析

概述

HashMap是Java集合框架（Java Collection Framework， JCF）中一个基础类，它在1998年12月，加入到Java 2版本中。在此之后，Map接口本身除了在Java 5中引入了泛型以外，再没有发生过明显变化。然而HashMap的实现，则为了提升性能，不断地在改变。

1.hash表的复习

在正式学习HashMap源码之前，先复习一下hash表的实现。

1.1 什么是哈希表

哈希表（Hash table，也叫散列表），是根据关键字值（key,value）直接进行访问的数据结构。也就是说，它通过把关键字映射到表中一个位置来访问的纪录，以加快查找的速度。这个映射函数叫做散列函数，存放纪录的数组叫散列表。

1.2 哈希函数

1.2.1 直接定址法

取关键字或关键字的某个线性函数值为哈希地址。

H(key) = key 或  H(key) = a*key+b 

1.2.2 除法散列法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词.

H(key) = key % p （p<=m）

1.2.3 平方散列法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

H(key) = ((key * Key) >> X) << Y

1.2.4 fibonacci散列法

和平方散列法类似，此种方法使用斐波那契数列的值作为乘数而不是自己。
对于16位整数而言，这个乘数是40503。
对于32位整数而言，这个乘数是2654435769。
对于64位整数而言，这个乘数是11400714819323198485。

H(key) = ((key * 2654435769) >> X) << Y

1.3 冲突解决

1.3.1 开放寻址法

开放寻址法把所有的元素都存放在散列表中，也就是每个表项包含动态集合的一个元素（元素可以为NULL）。

1.在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项（连续检查是可以通过不同的算法获得偏移位），直到找到一个空槽来放置这个元素为止。
2.当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。
3.在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将此位置元素置空。因为这样做的话，会导致在无法判断此位置是否有元素。应该用个特殊的值表示该元素已经删除。

Hi=(H(key) + di) MOD m , [i=1,2，…，k(k<=m-1)]

其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法:

di=1,2,3，…，m-1，称线性探测再散列。
di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列。
di=伪随机数序列，称伪随机探测再散列。

1.3.2 再散列法（再散列法）

产生碰撞时，再使用另一个散列函数计算地址，直到碰撞不再发生，这种方法不易产生“聚集”，但增加了计算时间（一个地址的产生可能会经过多个散列函数的计算）

Hi=Hn(key), [n=1,2 ...,]

有一个包含一组哈希函数 H1…Hn 的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数 H1。如果导致碰撞，则尝试使用 H2，以此类推，直到 Hn。所有的哈希函数都与 H1 十分相似，不同的是它们选用的乘法因子。

1.3.3 拉链法

产生碰撞时，把哈希到同一个槽中的所有元素都放到一个链表中。拉链法采用额外的数据结构来处理碰撞，其将哈希表中每个位置（slot）都映射到了一个链表。

1.3.4 公共溢出区

建立一个公共溢出区，当发生碰撞时，把碰撞元素放到缓冲区。

1.4 负载因子

负载因子(load factor)，它用来衡量哈希表的 空/满 程度，一定程度上也可以体现查询的效率，
计算公式为:

负载因子 = 总键值对数 / 箱子个数

负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。

2红黑树的复习

2.HashMap

2.1 HashMap的定义

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable, Serializable {
    /**
    默认的哈希表的负载因子
    */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
    hashMap的最大容量
    */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
    hashMap的默认容量
    */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    /**
    HashMap要调整的下一个容量大小
    */
    int threshold;
    /**
    hashMap容量的变量
    */
    int threshold;
    /**
    哈希表负载因子的变量
    */
    final float loadFactor;
    /**
    构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的 HashMap
    */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    /**
    构造一个带指定初始容量和默认加载因子 (0.75) 的 HashMap。
    */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    /**
    构造一个带指定初始容量和加载因子的 HashMap。
    */
    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);
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    /**
    返回给定容量大小的下一个容量。
    */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    /**
    构造map的结构或者将map的内容全部赋值
    evict 初始化hashMap时是false，其余的情况为true。
    */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size 初始化空间
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold) //重新调整空间
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = http://www.mamicode.com/e.getValue();"hljs-keyword">false, evict);
        }
    }
}

    }

HashMap实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则，而AbstractMap类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作。
在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

2.2数据存储结构

HashMap是基于哈希表存储“Key－Value”对象应用的数据结构。存入HashMap的键必须具备两个关键函数：
（1）equals()：判断两个Key是否相同，用来保证存入的Key的唯一性；
（2）hashCode()：genj key-value对象的Key来计算其引用在散列表中存放的位置。

    transient Node<K,V>[] table;

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = http://www.mamicode.com/value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

总结：
1.HashMap中有一个叫table的Node数组。
2.这个数组存储了Node类的对象。HashMap类有一个叫做Node的内部类。这个Node类包含了key-value作为实例变量。
3.每当往Hashmap里面存放key-value对的时候，都会为它们实例化一个Node对象，这个Node对象就会存储在前面提到的Node数组table中。根据key的hashcode()方法计算出来的hash值来决定。 hash值用来计算key在Entry数组的索引。

2.2.3 resize

//不使用红黑树的阀值
static final int UNTREEIFY_THRESHOLD = 6;
//使用红黑树的阀值
static final int TREEIFY_THRESHOLD = 8;

  final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                //hash表达到最大时，返回旧的hash表。
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //容量允许的时候，内存扩大一倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
              //初始化带指定容量因子和碰撞因子的hashmap。
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //默认初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        //循环遍历，将旧的hash表中的数据复制到新的hash表中。
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                    //拆分链表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //用(e.hash & oldCap)规则切割链表，为零在loHead，否则在hiHead
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    //拆分红黑树
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
    //UNTREEIFY_THRESHOLD 使用红黑树的阀值
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

//链表构造法
final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

        //红黑树的构造方法
 final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。
http://www.cnblogs.com/huaizuo/p/5371099.html 红黑树hash的计算方法。

2.2.4 put操作

 /**
 对外暴露的方法。
 */
 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 /**
 对key进行散列
 */
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 /**
 objec 中hashcode的实现，native关键字这里代表了有操作系统进行实现。
 */
 public native int hashCode();
 /**
 hash -->key对应的hash值
 value-->对应的值
 onlyIfAbsent-->true，不改变已经存在的值
 evict-->false,该表再创建模式
 */
 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)
            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 {
                for (int binCount = 0; ; ++binCount) {
                    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 = http://www.mamicode.com/e.value;"hljs-keyword">if (!onlyIfAbsent || oldValue =http://www.mamicode.com/= null)
                    e.value = http://www.mamicode.com/value;"hljs-keyword">return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

put方法的基本过程如下：
（1）对key的hashcode进行hash计算，获取应该保存到数组中的index。
（2）判断index所指向的数组元素是否为空，如果为空则直接插入。
（3）如果不为空，则依次查找entry中next所指定的元素，判读key是否相等，如果相等，则替换旧的值，返回。
（4）如果都不相等，则将此链表头元素赋值给待插入Node的next变量，让后将待插入元素插入到Node数组中去。
(5)Java 8 在没有降低哈希冲突的度的情况下，使用红黑书代替链表，

 static final int TREEIFY_THRESHOLD = 8;  
 static final int UNTREEIFY_THRESHOLD = 6;  
 ```  
 展示了Java 8的HashMap在使用树和使用链表之间切换的阈值。当冲突的元素数增加到8时，链表变为树；当减少至6时，树切换为链表。中间有2个缓冲值的原因是避免频繁的切换浪费计算机资源。  
 Java 8 HashMap使用的树是红黑树，它的实现基本与JCF中的TreeMap相同。通常，树的有序性通过两个或更多对象比较大小来保证。Java 8 HashMap中的树也通过对象的Hash值（这个hash值与哈希桶索引值不同，索引值在这个hash值的基础上对桶大小M取模，译者注）作为对象的排序键。因为使用Hash值作为排序键打破了Total Ordering（可以理解为数学中的小于等于关系，译者注），因此这里有一个tieBreakOrder()方法来处理这个问题。



###2.2.5 get 方法

public V get(Object key) {
Node

从上面的代码以及注释中可以看出，get操作还是比较简单的，先是根据key进行hash映射，得到其在table中的index，然后遍历真个Entry[index]链表。


##3.java 关键字
###3.1 transient的作用及使用方法
一个对象只要实现了Serilizable接口，这个对象就可以被序列化。将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。  
1）一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
2）transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。  
3）被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。
例外情况：
对象的序列化可以通过实现两种接口来实现，若实现的是Serializable接口，则所有的序列化将会自动进行，若实现的是Externalizable接口，则没有任何东西可以自动序列化，需要在writeExternal方法中进行手工指定所要序列化的变量，这与是否被transient修饰无关。
###3.2 native关键字
1。native 是用做java 和其他语言（如c++）进行协作时用的也就是native 后的函数的实现不是用java写的。
2。既然都不是java，那就别管它的源代码了

##4.hashMap与hashSet的区别

public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable
{
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 HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

}

由上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
##5.HashMap与HashTable

public class Hashtable

1.HashTable是一个线程安全的API，它的方法通过synchronized关键字进行修饰。尽管并不推荐使用HashTable来开发一个高性能的应用，但是它确实能够保证你的应用线程安全。相反，HashMap并不保证线程安全。因此当你构建一个多线程应用时，请使用ConcurrentHashMap。
2.关联数组与数组最大的不同，就是对于每一个数据，关联数组会有一个key与之关联，当使用关联数组时，每个数据都可以通过对应的Key来获取。关联数组有许多别名，比如Map（映射）、Dictionary（字典）和Symbol-Table（符号表）。尽管名字不同，他们的含义都是相同的。
3.字典和符号表都是非常直观的术语，无须解释它们的行为。映射来自于数学领域。在函数中，一个域（集合）中的值被与另一个域（集合）中的值关联，这种关联关系叫做映射。


##6 HashMap与线程安全
HashMap底层的数据结构是一个Entry数组，通过对key值进行hash映射，确定key-value对的存放位置。当多个不同key映射到同一个hash值时，它们在Entry数组中以链表的形式存在，新加入的元素会放在链表的头部。
可见HashMap的线程不安全的主要原因是HashMap的结构发生了变化，而从上一篇文章中可以知道，HashMap的结构变化发生在数组容量变更时，即当数组元素个数超过了阈值threshold=capacity*loadFactor时，HashMap将resize()
#####2.2.3.1单线程下单扩容
#####2.2.3.2多线程下单扩容
#####2.2.3.3线程不安全的表现
1、多线程put操作后，get操作导致死循环。
2、多线程put非NULL元素后，get操作得到NULL值。
3、多线程put操作，导致元素丢失。
###如何安全的使用HashMap
1.Hashtable
2.ConcurrentHashMap
3.Synchronized Map
###Hashtable
HashMap是Java 1.2引进的Map接口的一个实现。HashMap是新框架中用来代替Hashtable的类，也就是说建议使用HashMap，不要使用Hashtable。
Hashtable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized 关键字，而HashMap的源代码中则连 synchronized 的影子都没有，当然，注释除外。HashTable源码中是使用synchronized来保证线程安全的，
###ConcurrentHashMap
多线程操作要格外小心。知道JDK 1.5引入了ConcurrentHashMap才使得Map重新能够安全的在多线程下操作了。
ConcurrentHashMap具体是怎么实现线程安全的呢，肯定不可能是每个方法加synchronized，那样就变成了HashTable。
从ConcurrentHashMap代码中可以看出，它引入了一个“分段锁”的概念，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中。
在ConcurrentHashMap中，就是把Map分成了N个Segment，put和get的时候，都是现根据key.hashCode()算出放到哪个Segment中：
###SynchronizedMap

/**
*性能对比例程
*/
public class CrunchifyConcurrentHashMapVsSynchronizedMap {

public final static int THREAD_POOL_SIZE = 5;

public static Map<String, Integer> crunchifyHashTableObject = null;
public static Map<String, Integer> crunchifySynchronizedMapObject = null;
public static Map<String, Integer> crunchifyConcurrentHashMapObject = null;

public static void main(String[] args) throws InterruptedException {

    // Test with Hashtable Object
    crunchifyHashTableObject = new Hashtable<>();
    crunchifyPerformTest(crunchifyHashTableObject);

    // Test with synchronizedMap Object
    crunchifySynchronizedMapObject = Collections.synchronizedMap(new HashMap<String, Integer>());
    crunchifyPerformTest(crunchifySynchronizedMapObject);

    // Test with ConcurrentHashMap Object
    crunchifyConcurrentHashMapObject = new ConcurrentHashMap<>();
    crunchifyPerformTest(crunchifyConcurrentHashMapObject);

}

public static void crunchifyPerformTest(final Map<String, Integer> crunchifyThreads) throws InterruptedException {

    System.out.println("Test started for: " + crunchifyThreads.getClass());
    long averageTime = 0;
    for (int i = 0; i < 5; i++) {

        long startTime = System.nanoTime();
        ExecutorService crunchifyExServer = Executors.newFixedThreadPool(THREAD_POOL_SIZE);

        for (int j = 0; j < THREAD_POOL_SIZE; j++) {
            crunchifyExServer.execute(new Runnable() {
                @SuppressWarnings("unused")
                @Override
                public void run() {

                    for (int i = 0; i < 500000; i++) {
                        Integer crunchifyRandomNumber = (int) Math.ceil(Math.random() * 550000);

                        // Retrieve value. We are not using it anywhere
                        Integer crunchifyValue = http://www.mamicode.com/crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));"2500K entried added/retrieved in " + totalTime + " ms");
    }
    System.out.println("For " + crunchifyThreads.getClass() + " the average time is " + averageTime / 5 + " ms\n");
}

}

##Redis
Redis 是一个高效的 key-value 缓存系统，也可以理解为基于键值对的数据库。它对哈希表的设计有非常多值得学习的地方，在不影响源代码逻辑的前提下我会尽可能简化，突出重点。

数据结构
在 Redis 中，字典是一个 dict 类型的结构体，定义在 src/dict.h 中:

typedef struct dict {
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
这里的 dictht 是用于存储数据的结构体。注意到我们定义了一个长度为 2 的数组，它是为了解决扩容时速度较慢而引入的，其原理后面会详细介绍，rehashidx 也是在扩容时需要用到。先看一下 dictht 的定义:

typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long used;
} dictht;
可见结构体中有一个二维数组 table，元素类型是 dictEntry，对应着存储的一个键值对:

typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
从 next 指针以及二维数组可以看出，Redis 的哈希表采用拉链法解决冲突。

添加元素
向字典中添加键值对的底层实现如下:

dictEntry *dictAddRaw(dict *d, void *key) {
int index;
dictEntry *entry;
dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d);
if ((index = _dictKeyIndex(d, key)) == -1)
    return NULL;

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;

dictSetKey(d, entry, key);
return entry;

}
dictIsRehashing 函数用来判断哈希表是否正在重新哈希。所谓的重新哈希是指在扩容时，原来的键值对需要改变位置。为了优化重哈希的体验，Redis 每次只会移动一个箱子中的内容，下一节会做详细解释。

仔细阅读指针操作部分就会发现，新插入的键值对会放在箱子中链表的头部，而不是在尾部继续插入。这个细节上的改动至少带来两个好处:

找到链表尾部的时间复杂度是 O(n)，或者需要使用额外的内存地址来保存链表尾部的位置。头插法可以节省插入耗时。
对于一个数据库系统来说，最新插入的数据往往更有可能频繁的被获取。头插法可以节省查找耗时。
增量式扩容
所谓的增量式扩容是指，当需要重哈希时，每次只迁移一个箱子里的链表，这样扩容时不会出现性能的大幅度下降。

为了标记哈希表正处于扩容阶段，我们在 dict 结构体中使用 rehashidx 来表示当前正在迁移哪个箱子里的数据。由于在结构体中实际上有两个哈希表，如果添加新的键值对时哈希表正在扩容，我们首先从第一个哈希表中迁移一个箱子的数据到第二个哈希表中，然后键值对会被插入到第二个哈希表中。

在上面给出的 dictAddRaw 方法的实现中，有两句代码:

if (dictIsRehashing(d)) _dictRehashStep(d);
// …
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
第二句就是用来选择插入到哪个哈希表中，第一句话则是迁移 rehashidx 位置上的链表。它实际上会调用 dictRehash(d,1)，也就是说是单步长的迁移。dictRehash 函数的实现如下:

int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */

while(n-- && d->ht[0].used != 0) {
    dictEntry *de, *nextde;

    while(d->ht[0].table[d->rehashidx] == NULL) {
        d->rehashidx++;
        if (--empty_visits == 0) return 1;
    }
    de = d->ht[0].table[d->rehashidx];
    /* Move all the keys in this bucket from the old to the new hash HT */
    while(de) {
        unsigned int h;

        nextde = de->next;
        /* Get the index in the new hash table */
        h = dictHashKey(d, de->key) & d->ht[1].sizemask;
        de->next = d->ht[1].table[h];
        d->ht[1].table[h] = de;
        d->ht[0].used--;
        d->ht[1].used++;
        de = nextde;
    }
    d->ht[0].table[d->rehashidx] = NULL;
    d->rehashidx++;
}

/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
    zfree(d->ht[0].table);
    d->ht[0] = d->ht[1];
    _dictReset(&d->ht[1]);
    d->rehashidx = -1;
    return 0;
}

return 1;

}
这段代码比较长，但是并不难理解。它由一个 while 循环和 if 语句组成。在单步迁移的情况下，最外层的 while 循环没有意义，而它内部又可以分为两个 while 循环。

第一个循环用来更新 rehashidx 的值，因为有些箱子为空，所以 rehashidx 并非每次都比原来前进一个位置，而是有可能前进几个位置，但最多不超过 10。第二个循环则用来复制链表数据。

最外面的 if 判断中，如果发现旧哈希表已经全部完成迁移，就会释放旧哈希表的内存，同时把新的哈希表赋值给旧的哈希表，最后把 rehashidx 重新设置为 -1，表示重哈希过程结束。

默认哈希函数
与 Java 不同的是，Redis 提供了 void * 类型 key 的哈希函数，也就是通过任何类型的 key 的指针都可以求出哈希值。具体算法定义在 dictGenHashFunction 函数中，由于代码过长，而且都是一些位运算，就不展示了。

它的实现原理是根据指针地址和这一块内存的长度，获取内存中的值，并且放入到一个数组当中，可见这个数组仅由 0 和 1 构成。然后再对这些数字做哈希运算。因此即使两个指针指向的地址不同，但只要其中内容相同，就可以得到相同的哈希值。

归纳对比

首先我们回顾一下 Java 和 Redis 的解决方案。

Java 的长处在于当哈希函数不合理导致链表过长时，会使用红黑树来保证插入和查找的效率。缺点是当哈希表比较大时，如果扩容会导致瞬时效率降低。

Redis 通过增量式扩容解决了这个缺点，同时拉链法的实现(放在链表头部)值得我们学习。Redis 还提供了一个经过严格测试，表现良好的默认哈希函数，避免了链表过长的问题。

Objective-C 的实现和 Java 比较类似，当我们需要重写 isEqual() 方法时，还需要重写 hash 方法。这两种语言并没有提供一个通用的、默认的哈希函数，主要是考虑到 isEqual() 方法可能会被重写，两个内存数据不同的对象可能在语义上被认为是相同的。如果使用默认的哈希函数就会得到不同的哈希值，这两个对象就会同时被添加到 NSSet 集合中，这可能违背我们的期望结果。

根据我的了解，Redis 并不支持重写哈希方法，难道 Redis 就没有考虑到这个问题么？实际上还要从 Redis 的定位说起。由于它是一个高效的，Key-Value 存储系统，它的 key 并不会是一个对象，而是一个用来唯一确定对象的标记。

一般情况下，如果要存储某个用户的信息，key 的值可能是这样: user:100001。Redis 只关心 key 的内存中的数据，因此只要是可以用二进制表示的内容都可以作为 key，比如一张图片。Redis 支持的数据结构包括哈希表和集合(Set)，但是其中的数据类型只能是字符串。因此 Redis 并不存在对象等同性的考虑，也就可以提供默认的哈希函数了。

Redis、Java、Objective-C 之间的异同再次证明了一点:

“`

总结：
1.HashMap线程不安全，主要是多线程put，get是会出现同步问题；
2.多线程操作HashMap是容易出现循环链表，导致get方法调用时可能出现死循环；
3.安全的使用Map有三种方式：Hashtable，SynchronizedMap，ConcurrentHashMap。其中Hashtable不推荐使用，ConcurrentHashMap效率最高。