数据结构

jdk1.7版本，hashmap的数据结构是数组+链表

/**
* 这个属性主要就是hashMap初始化的一个数组，它是一个由final定义不可改变的数组
*/
static final Entry<?,?>[] EMPTY_TABLE = {};

/**
 * 这个属性才是真正去存储元素的数组，在必要的时候进行扩容，数组的长度必须是2的整数倍
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
* 是hashmap中的一个静态内部类
*/
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    // 指针
    Entry<K,V> next;
    int hash;
    ...
}

为了加快hashmap的效率，在jdk1.8之后hashmap的数据结构变为数组+链表+红黑树

/**
* 存储添加的元素
*/
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;
    ...
}

/**
* 树结构
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	TreeNode<K,V> parent;  // red-black tree links
	TreeNode<K,V> left;
	TreeNode<K,V> right;
	TreeNode<K,V> prev;    // needed to unlink next upon deletion
	boolean red;
	TreeNode(int hash, K key, V val, Node<K,V> next) {
	    super(hash, key, val, next);
	}
	...
}

实例化

jdk1.7的中hashmap的属性

/**
  * 初始容量为16
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 1 * 2 ^ 4

 /**
  * 数组存放的最大容量为1 * 2 ^ 30
  */
 static final int MAXIMUM_CAPACITY = 1 << 30; // aka 1 * 2 ^ 30

 /**
  * 默认的加载因子，主要用于扩容
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  * 实际存放的元素个数，即通过put方法存放的元素个数
  */
 transient int size;

 /**
  * 扩容阈值
  */
 int threshold;

 /**
  * 加载因子
  */
 final float loadFactor;

 /**
  * 修改次数
  */
 transient int modCount;

jdk1.7hashmap实例化过程

/**
* 通过传入容量大小来初始化
*/
public HashMap(int initialCapacity) {
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
* 空构造方法会直接传入hashmap已经定义好的变量来初始化
*/
public HashMap() {
   this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

/**
* 通过传入自定义的长度和加载因子来初始化
*/
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;
   // 16
   threshold = initialCapacity;
   init();
}

jdk1.8的属性（1.8的属性比1.7的属性还要多得多，这里就展示一部分吧）和hashmap实例化过程 -> 实例化过程其实和jdk1.7没有太大的区别，大家可以自行去查看

像jdk1.7有的属性在1.8基本都有，像初始容量、默认的加载因子、最大存储容量和构造方法都是差不多的。
.....
/**
* 链表转红黑树的阈值
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 红黑树转为链表的阈值
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 红黑树最小存储的元素容量
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* 修改次数
*/
 transient int modCount;

不过在这里，当我们在业务上能够明确知道定义的hashmap的容量大小或者它能够接受的最大值是多少，这时候就应该尽量通过传入容量大小去初始化hashmap，好处是能够避免因为每次扩容而导致效率低的问题，但缺点也可能造成内存浪费。

添加操作

jdk1.7中的put方法

public V put(K key, V value) {
	 // 判断table数组是否为空
     if (table == EMPTY_TABLE) {
     	 // 初始化该数组 -> 方法介绍在下面
         inflateTable(threshold);
     }
     // 判断key是否为空
     if (key == null)
     	 // 如果key为空的话，它会将这个key为null的键值对组成的链表结构插入到下标为0的数组中
         return putForNullKey(value);
     // 对key求hash值
     int hash = hash(key);
     // 通过key的hash值和table的长度计算出该元素应插入数组的下标值
     int i = indexFor(hash, table.length);
     // 遍历链表
     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
         Object k;
         // 如果发生hash冲突的话就将新插入的value赋值给旧的value，key不变
         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
         }
     }
     modCount++;
     // 若没有发生hash冲突，就直接添加到链表中
     addEntry(hash, key, value, i);
     return null;
 }

inflateTable（）方法

/**
* 初始化table，tosize为数组的默认初始化容量大小16
*/
private void inflateTable(int toSize) {
   // 通过roundUpToPowerOf2（）方法去生成一个容量大小必须为2的倍数的capacity，这里产生一个问题，为什么一定要生成一个大小为2的倍数的容量呢？？后面解答
   int capacity = roundUpToPowerOf2(toSize);
   // 重新对扩容阈值赋值，并初始化table
   threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
   table = new Entry[capacity];
   initHashSeedAsNeeded(capacity);
}

roundUpToPowerOf（）方法和highestOneBit（int i）方法

private static int roundUpToPowerOf2(int number) {
   // 这是一个三元运算符，主要的方法就是在Integer类中的highestOneBit静态方法。
   return number >= MAXIMUM_CAPACITY
           ? MAXIMUM_CAPACITY
           : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 这个方法其实就是用来对传入的 i 进行五次或运算和位运算，然后在返回 i - (i >>> 1)
// 目的就是为了取 i 的二进制的最高位，例如传入的是9（1001），通过五次运算之后得到1111，
// 然后在通过 i - (i >>> 1)得到1000，这样就能保证获取的值为2的倍数。
public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

这里来解决在上述所产生的问题，为什么一定要生成一个大小为2的倍数的容量呢？来看看一个方法，这个方法是用来通过key的hash值和table的长度计算出该元素应插入数组的下标值

static int indexFor(int h, int length) {
	 // 这里的这一行的代码就可以解释为什么一定要生成一个大小为2的倍数的容量了
	 // 我们知道通过与运算符（&）来求值的话，若一个值的二进制中有0那么实际上不管另外
	 // 一个数的二进制中是否为0或者1，&出来的结果都是0。
	 // 例如：
	 // h = 1011，length = 1011，length - 1 = 1010
	 // 则 h & （length - 1） = 1010
	 // 这样会导致一个问题就是如果你传进来的参数table.length不是2的倍数，假设为1011，那么它减去1之后
	 // 生成的二进制的末尾必定是0，比如：1011 - 0001 = 1010；
	 // 这样的话就会造成数组上的有些位置将永远访问不到，前面也说了不管0/1 & 0都为0，造成空间的浪费，而且也增加了hash冲突的可能性。
     return h & (length-1);
}

jdk1.8中的put方法

public V put(K key, V value){
    return putVal(hash(key), key, value, false, true);
}

// 通过传入的key计算hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判断数组是否为空，若空则通过resize（）方法初始化数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 判断下标为（n - 1） & hash所对应的数组中的链表是否为空，即是否发生了哈希碰撞
    if ((p = tab[i = (n - 1) & hash]) == null)
    	// 若无，则在链表中创建一个结点存储元素
        tab[i] = newNode(hash, key, value, null);
    // 若发生了哈希碰撞
    else {
        Node<K,V> e; K k;
        // 如果下标为（n - 1） & hash对应的数组的链表不为空，判断传入的key和key所对应的hash值
        // 是否和p结点中的key和key对应hash值相同，若相同，将p结点赋值给e结点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 若当前p的数据结构为树结构并不是链表或者数组结构的话，则通过树结构的形式去添加元素
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 以上如果均不满足，就通过链表的形式去添加元素
        else {
        	// binCount用来记录将链表转为红黑树结构的界限值
            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;
                }
                // 若下一个结点不为空，则断传入的key和key所对应的hash值
        		// 是否和e结点中的key和key对应hash值相同，若相同，将e结点赋值给p结点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 若发生了哈希碰撞，则将key所对应的新值去覆盖旧值，key不变
        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（）进行扩容，容量扩到原本的两倍
        resize();
    afterNodeInsertion(evict);
    return null;
}

大家有没有发现在jdk1.7和jdk1.8中都有一个共同的属性modCount，我当时也很好奇这个属性到底有什么用？这会涉及到迭代器的问题。

迭代器中有两种迭代机制：1、fail-fast快速失败，2、fail-safe安全失败机制；像hashmap、ArrayList、linkedList这些线程不安全的集合使用的都是fail-fast快失败机制

此属性在非线程安全的集合中是非常重要的，当我们使用的迭代器去遍历集合的时候，modcount记录了我们修改集合的次数（添加或者删除），若有其它线程去操作这个集合的时候，Iterator会去比较当前的modcount和expectedModCount是否相同，如果不相同就会抛出ConcurrentModificaionException并发修改异常。
！！注意！！
此异常并不是只有在多线程的情况下才会发生，在单线程情况下，如果使用迭代器遍历集合，也会造成并发修改异常，例如以下代码

List<String> list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
// 初始化迭代器
Iterator it = list.iterator();
int i = 0;
while(it.hasNext()){
    if(i==2){
        list.remove("3");// 边遍历边去修改集合结构就会报并发修改异常
    }
    System.out.println("第"+i+"个元素"+it.next());
    i++ ;
}

本次博客纯属是为了在学习源码的时候记录的笔记，可能会有很多地方理解错误，还望各位大神能更正我的错误