这是《并发编程的艺术》第5篇阅读笔记。之前都是jdk8的，然后在并发容器框架这一章讲了ConCurrentHashMap ,然后想着把jdk7的hashmap，concurrentHashMap,jdk8的hashmap，concurrentHashMap,四个拿出来分析比较一下。

首先是jdk7 的hashmap .还算比较简单，主要是高并发下的死锁，这个问题，那一段比较绕。

1 让我们来看源码

先看注释

    As a general rule, the default load factor (.75) offers a good tradeoff
 * between time and space costs.  Higher values decrease the space overhead
 * but increase the lookup cost (reflected in most of the operations of the
 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The
 * expected number of entries in the map and its load factor should be taken
 * into account when setting its initial capacity, so as to minimize the
 * number of rehash operations.  If the initial capacity is greater
 * than the maximum number of entries divided by the load factor, no
 * rehash operations will ever occur.
意思是： 默认的0.75 加载因子loadfactor（size/capacity）
是对于空间和时间的消耗，一个很好的平衡。
如果loadFacotor比较高的话，会降低空间的浪费，
但是会增加get方法的时间消耗。
所以，加载因子和初始的容量，应该考虑进去，
使得尽可能减少rehash的次数。

2 然后看构造方法

public HashMap(int initialCapacity, float loadFactor) {      
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];  //`这里就有和jdk8不同的地方，8是在put时候，inflateTable才初始化`
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

从构造方法看的话，首先他是通过左移1位，while循环左移，使得capacity是大于等于给定参数的2次幂。

image.png

然后等到插入3之后扩容了。

image.png

3 我们来看put方法和扩容机制

 public V put(K key, V value) {
        int hash = hash(key);
        int i = indexFor(hash, table.length);   //对hash值的低power位，和掩码做与操作，就是取模
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  //遍历这个bucket下的链表，如果找到key一样的
            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;
    }

3.1 看hash方法

hash方法，这里 只是一个防止弱的hash函数，（比如16的capacity,对象的hashcode是1,17,33，这种等差数列，进行一次再离散，相当于框架，帮程序员兜底了）不够离散，然后这里加了一个这个函数。其实一些人常说的rehash并不是指的这个。而是扩容之后，重新取模。取模采用和capacity的掩码，做与运算得到。扩容前后，对这个int型的hash值，并没有影响。。而且32位的hash值是只有4个G的空间，不可能无限增大。

3.2 addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {   //threshold = capacity * load factor
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);  //重新取模
        }

        createEntry(hash, key, value, bucketIndex);
    }

大于阈值，就吧Entry[]扩大为原来的两倍.

4 transfer方法 把原来的数据，按照头插法 插入新的Entry[] ，是扩容的关键，也是产生死循环的原因。

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

这段代码太绕，需要调试图解，让人看得更清楚一些。
我写了一个简单版的，而且参数极端的，一个map.

/**
 *
 * @author wb-xjx412741
 * @version $Id: FakeHashMap.java, v 0.1 2018年12月11日 17:36 wb-xjx412741 Exp $
 */
public class FakeHashMap<K,V> {

    private static final Integer index = 1;
    private Node<K,V>[] table =  new Node[4];
    private CountDownLatch start = new CountDownLatch(1);
    private CountDownLatch sleep = new CountDownLatch(1);

    static class Node<K,V>{
        private K key;
        private V  value;
        private Node<K,V> next;
        。。。。此处省略get,set方法和构造方法
       
    }

    public void put(K key, V value){
       Node node = new Node<>(key,value,null);
        if(table[index]!=null){
            Node tail = table[index];
            while(tail.next!=null){
                tail=  tail.next;
            }
            tail.next = node;
        }else{
            table[index] = node;
        }

    }

    public void transfer( Thread task) {
        if(task.getName().equals("Task1")){
            transfer(new Node[8]);
        }else if(task.getName().equals("Task2")){
            transfer2(new Node[8]);
        }

    }
    /**
     * task1  执行Node<K,V> next = e.next;完之后，睡觉10秒
     * @param newTable
     */
    public   void transfer(Node[] newTable) {
        for (Node<K,V> e : table) {
            while(null != e) {
                Node<K,V> next = e.next;
                try {
                    System.out.println("Task1 has runned a short time======");
                    start.countDown();
                    System.out.println("Task1 wait======");
                    sleep.await();
                } catch (InterruptedException e1) {
                    e1.printStackTrace();
                }
                e.next = newTable[index];
                newTable[index] = e;
                e = next;
            }
        }
        System.out.println("Task1 finished======");
    }
    public  void transfer2(Node[] newTable) {
        //start开关，先让transfer先执行
        try {
            start.await();
            System.out.println("Task2 begin======");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        for (Node<K,V> e : table) {
            while(null != e) {
                Node<K,V> next = e.next;
                e.next = newTable[index];
                newTable[index] = e;
                e = next;
            }
        }
        System.out.println("Task2 finished======");
        sleep.countDown();
    }
}

/**
 *
 * @author wb-xjx412741
 * @version $Id: FakeMapTest.java, v 0.1 2018年12月11日 18:30 wb-xjx412741 Exp $
 */
public class FakeMapTest {
    public static void main(String[] args) {
        FakeHashMap map = new FakeHashMap();
        map.put("1","A");
        map.put("2","B");
        map.put("3","C");
        CountDownLatch allReady = new CountDownLatch(2);
        new Thread(new Task2(map,allReady),"Task2").start();
        new Thread(new Task1(map,allReady),"Task1").start();
    }
}
class Task1 implements Runnable{
    private FakeHashMap map;
    //先让两个线程都跑起来
    private CountDownLatch allReady ;

    public Task1(FakeHashMap map, CountDownLatch allReady) {
        this.map = map;
        this.allReady = allReady;
    }
    @Override
    public void run() {
        try {
            allReady.countDown();
            allReady.await();
                map.transfer(Thread.currentThread());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
class Task2 implements Runnable{
    private FakeHashMap map;
    //先让两个线程都跑起来
    private CountDownLatch allReady ;
    public Task2(FakeHashMap map, CountDownLatch allReady) {
        this.map = map;
        this.allReady = allReady;
    }
    @Override
    public void run() {
        try {
            allReady.countDown();
            allReady.await();
            map.transfer(Thread.currentThread());
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

刚开始是运行Task1 ,
transfer的时候，运行到这一句，start.countDown();，然后开始运行Task2 ,Task1 挂起。
快照1 :

image.png

countDown之后，切换到Task2 , 让Task2 运行完成 ，最后拍个快照：

image.png

Task2线程栈中的newTable[1] 指向内存中的Node(3,C),而且改变了内存中，Node(1,A),Node(2,B),Node(3,C)的next指针关系，本来是1==》2==》3 ,现在是3=-》2==》1 ，因为是头插法。然后Task1中的next指向的是2
接下来切换回Task1 ,拍个快照
next
||
3=-》2==》1

image.png

然后第一个循环走完。e 指向2 ==》1 newTable[1] ==>1

image.png

第二个循环走完。 e指向1 newTable[1] ==>2==>1

image.png
第三个循环走完，结束，奇迹产生了，1和2互相循环指向
image.png