常用集合的原理分析(一) 集合例子

• 常用集合的底层的原理：ArrayList、Vector、LinckedList、HashMap、HashSet、LinkedHashMap、LruCache、SparseArray、ConcurrentHashMap

一、ArrayList

• 最佳的做法是将ArrayList作为默认的首选，当你需要而外的功能的时候，或者是当程序性能由于经常需要从表中间插入和删除而变差的时候，才会去选择LinkedList 来源于THinking in Java
• 源码分析
• 最重要的两个属性分别是: elementData 数组 size的大小

transient Object[] elementData;
 /**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
 //以及 size 大小
 private int size;

• transient: java:语言的关键字，变量修饰符，如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，用transient关键字标记的成员变量不参与序列化过程。
• 构造函数: new ArrayList() 的时候，会指定一个Object[]

 private static final Object[] EMPTY_ELEMENTDATA = {};
 public ArrayList() {
 super();
 this.elementData = EMPTY_ELEMENTDATA;
 }

• 指定长度

public ArrayList(int initialCapacity) {
 super();
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 this.elementData = new Object[initialCapacity];
 }

• new Collection() 添加一个集合

 public ArrayList(Collection<? extends E> c) {
 elementData = c.toArray();
 size = elementData.length;
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, 
Object[].class);
 }

• 添加元素add() 将指定的元素追加到列表的末尾

• ensureCapacityInternal()方法详情，如果是add 一个元素，那么就会走到ensureExplicitCapacity()的方法中！同时第一次扩容的最小的值为DEFAULT_CAPACITY=10;

private void ensureCapacityInternal(int minCapacity) {
 // 如果 是直接new ArrayList的话，那么扩容的最小的值为10
 if (elementData == EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 //开始扩展
 ensureExplicitCapacity(minCapacity);
}

• ensureExplicitCapacity(minCapacity),其中 minCapacity是最小的长度，如果是使用的 new ArrayList<E>() 然后 add(E),那么这个 minCapacity=10.具体请看代码的逻辑

private void ensureExplicitCapacity(int minCapacity) {
 modCount++;
 // overflow-conscious code
 if (minCapacity - elementData.length > 0)
 grow(minCapacity);
 }

• grow(minCapactity) 增加容量以确保它至少能容纳由最小容量参数指定的元素数量。

 private void grow(int minCapacity) {
 // overflow-conscious code
 int oldCapacity = elementData.length;
 //(oldCapacity >> 1)等于 oldCapacity%2 意思就是除以2，取整数
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 if (newCapacity - minCapacity < 0)
 newCapacity = minCapacity;
 if (newCapacity - MAX_ARRAY_SIZE > 0)
 newCapacity = hugeCapacity(minCapacity);
 // minCapacity is usually close to size, so this is a win:
 //最小容量通常接近大小，所以这是一个胜利：
 elementData = Arrays.copyOf(elementData, newCapacity);
 }

• 分析上面的问题，假如第一次添加数据，那么oldCapacity =0;0>>2=0; newCapacity - minCapacity < 0就是 ：0-10肯定小于0的,所以 newCapacity = minCapacity;，根据前面的分析，minCapacity=10!
• minCapacity is usually close to size, so this is a win: 翻译为：最小容量通常接近大小，所以这是一个胜利： 最后调用等到一个容器长度为10的elementData:
• 最后一步在 elementData[size++] = e;就是把 elementData[0] = e;赋值完成了，size才会++ ，等于size=1
• 关于 >>代表右移; 2的二进制是10，>>代表右移，10右移1位是二进制的1，<<代表左移，10左移1位是二进制的100，也就是十进制的4。
• 往指定角标中添加元素 ,过程和添加一个元素一样，只不过这个方法更加的高效System.arraycopy()

 public void add(int index, E element) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 // 首先扩容校验。
 ensureCapacityInternal(size + 1); // Increments modCount!!
 // TODO: 2018/8/16 使用了 native的方法
 // 复制，向后移动 接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。
 System.arraycopy(elementData, index, elementData, index + 1,
 size - index);
 elementData[index] = element;
 size++;
 }

• 在ArrayList中自定义了 writeObject 和 readObject ,目的是为了：JVM 会调用这两个自定义方法来实现序列化与反序列化 ArrayList 只序列化(序列化 (Serialization)将对象的状态信息转换为可以存储或传输的形式的过程。在序列化期间，对象将其当前状态写入到临时或持久性存储区。以后，可以通过从存储区中读取或反序列化对象的状态，重新创建该对象)了被使用的数据。

 private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException{
...
 }
 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
...
}

• ArrayList的线程不安全,通过下面的方式证明

• 两个线程不断的插入的话，就会导致插入的是null 我是i=34 我是i=10 我是i=35 我是i=11 null null 我是i=12 我是i=38 我是i=13 我是i=39
• 如果要使用安全的线程的话，可以通过List<String> data=Collections.synchronizedList(new ArrayList<String>());得到线程安全的集合，
• *Collections.synchronizedList 的原理,如下代码

public static <T> List<T> synchronizedList(List<T> list) {
 return (list instanceof RandomAccess ?
 new SynchronizedRandomAccessList<>(list) :
 new SynchronizedList<>(list));
}

• 可以在SynchronizedList类中方法加入了关键字 synchronized

public E get(int index) {
 synchronized (mutex) {return list.get(index);}
 }
 public E set(int index, E element) {
 synchronized (mutex) {return list.set(index, element);}
 }
 public void add(int index, E element) {
 

• 关于原型模式，ArrayList 实现了接口Cloneable;这个接口只有一个作用，就是在运行时候通知虚拟机可以安全的实现,在java的虚拟机中，只有实现了这个接口的类才可以被拷贝，否者会抛出CloneNotSupportedException

 public Object clone() {
 try {
 ArrayList<?> v = (ArrayList<?>) super.clone();
 v.elementData = Arrays.copyOf(elementData, size);transient
 v.modCount = 0;
 return v;
 } catch (CloneNotSupportedException e) {
 // this shouldn't happen, since we are Cloneable
 throw new InternalError(e);
 }
 }

• 我们可以看到这里有个深拷贝和 浅拷贝,幸运的是java中大部分都容器都实现了Cloneable这个接口，所以在程度上去实现深入拷贝不太难。
• 深拷贝：就是需要拷贝的类中，所有的东西，比如说：原型类中的数组，容器，饮用对象等
• 浅拷贝：就是只拷贝基本东西，容器这些不拷贝
• 更多的设计模式 二十三种设计模式
• ArrayList遍历的速度快，插入删除速度慢，随机访问的速度快

二、Vector

• 关注add get 方法:可以得出：使用 synchronized进行同步写数据，但是开销较大，所以 Vector 是一个同步容器并不是一个并发容器。

 public synchronized boolean add(E e) {
 modCount++;
 ensureCapacityHelper(elementCount + 1);
 elementData[elementCount++] = e;
 return true;
 }
 public synchronized E get(int index) {
 if (index >= elementCount)
 throw new ArrayIndexOutOfBoundsException(index);
 return elementData(index);
 }

• 应该避免使用Vector ，它只存在支持遗留代码的类中（它能正常的工作的唯一原因是：因为为了向前兼容，它被适配成为了List）
• 其他的不想多说，浪费电！

三、LinckedList

• 变量: 集合元素数量;链表头节点;链表尾节点

 //集合元素数量
 transient int size = 0;
 //链表头节点
 transient Node<E> first;
 //链表尾节点
 transient Node<E> last;

• Node类，数据结构的关键类，每一个元素值，都存在两个结点，前一个，后一个

 private static class Node<E> {
 E item;//元素值
 Node<E> next;//后置节点
 Node<E> prev;//前置节点
 Node(Node<E> prev, E element, Node<E> next) {
 this.item = element;
 this.next = next;
 this.prev = prev;
 }
 }

• 构造方法

 public LinkedList() {
 }
 public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }

• 关注 add(E)方法,可以看到这个返回值永远为true; 每次插入都是移动指针，和 ArrayList 的拷贝数组来说效率要高上不少

 public boolean add(E e) {
 linkLast(e);
 return true;
 }

• linkLast(E) 方法:生成新节点 并插入到 链表尾部， 更新last/first节点。

 void linkLast(E e) {
 final Node<E> l = last;
 final Node<E> newNode = new Node<>(l, e, null);
 last = newNode;
 if (l == null) //若原链表为空链表，需要额外更新头结点
 first = newNode;
 else//否则更新原尾节点的后置节点为现在的尾节点（新节点）
 l.next = newNode;
 size++;
 modCount++;
 }

• 如果说，最后的一个结点为null;那么我们新加入的元素，就是最后一个结点，如果最后一个结点不为null,那么我们插入的新的值就是最后结点的l.next = newNode.
• get()方法

 public E get(int index) {
 // 常看数组角标是否越界
 checkElementIndex(index);
 return node(index).item;
 }

• node(index)的方法

 Node<E> node(int index) {
 //二分查找来看 index 离 size 中间距离来判断是从头结点正序查还是从尾节点倒序查
 // assert isElementIndex(index);
 //通过下标获取某个node 的时候，（增、查 ），会根据index处于前半段还是后半段 进行一个折半，以提升查询效率
 if (index < (size >> 1)) {
 Node<E> x = first;
 //不断的往前面找 ，如果查找的角标比linkedList的size的取余还小的话，就通过不断的循环去得到相对应的值
 for (int i = 0; i < index; i++)
 x = x.next;
 return x;
 } else {
 Node<E> x = last;
 for (int i = size - 1; i > index; i--)
 x = x.prev;
 return x;
 }
 }

• 可以看出这是一个二分查找，如果 index < (size >> 1) , >>代表右移,其实就是 %2,这里查找下去，知道找到为止
• 如果假如，我们查找的index约接近size的一半，那么我们需要的次数就会越低，总结一句话：效率是非常低的，特别是当 index 越接近 size 的中间值。
• 来源于 gitHub
• 
  

四、HashMap

• 在 1.6 1.7 hashmap的类的代码一共1500行左右，在1.8一共有2000行左右! 这里直接看的是 JDK1.8 的代码。
• 关于变量

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 //左移运算符，num << 1,相当于num乘以2 最大的长度
 static final int MAXIMUM_CAPACITY = 1 << 30;// 相当于把1 位移30为等于 1 + 30个0的长度
 // 填充比 因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率
 // hashMap本来是以空间换时间，所以填充比没必要太大。但是填充比太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 //当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树
 static final int TREEIFY_THRESHOLD = 8;
 static final int UNTREEIFY_THRESHOLD = 6;
 static final int MIN_TREEIFY_CAPACITY = 64;

• 关于Node内部类

static class Node<K,V> implements Map.Entry<K,V> {
 final int hash;
 final K key;
 V value;
 Node<K,V> next;
 //todo 构造函数 hash值 key 和value 和 下一个结点
 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; }
 // 是去key的hash值和 value的hash值 然后做位异运算 转为二进制 相同为0，不同为1
 public final int hashCode() {
 // todo 位异或运算（^）
 // 运算规则是：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1
 return Objects.hashCode(key) ^ Objects.hashCode(value);
 }
 public final V setValue(V newValue) {
 V oldValue = value;
 value = newValue;
 return oldValue;
 }
 // todo 判断两个 node 结点是否相等，一个比较自身相等，一个是比较key和value
 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;
 }
 }

• Node类的中存储了 hash key value 和下一个结点 Node,后面解释
• Node 类的 hashCode是Objects.hashCode(key) ^ Objects.hashCode(value);位异或运算（^）: 运算规则是两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1
• 判断两个node是否相等：一个比较自身相等，一个是比较key和value
• HashMap的构造方法,指定容量和扩展因子

• 关于tableSizeFor(initialCapacity) 方法，说白了就是算法，给你一个接近的值，设置hashmap的长度为10，那么他的新的扩容的临界值=16

 int cap=10;
 int n = cap - 1;//9
 n |= n >>> 1;//9的二进制=1001 >>>表示无符号的右移 100 =十进制 4 n= 1001 |= 100
 System.out.println("n="+n); // n=13; 其实就是等于 n= 1001 |= 100 也就是n=1101 换成十进制等于13
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 int i= (n < 0) ? 1 : (n >= 1000000) ? 1000000 : n + 1;

• 无符号的右移（>>>）:按照二进制把数字右移指定数位，高位直接补零，低位移除！
• a=a|b 等于 a|=b的意思就是把a和b按位或然后赋值给a 按位或的意思就是先把a和b都换成2进制，然后用或操作
• 比如：9的二进制1001 >>>表示无符号的右移 得到100 等于十进制 4 n=1001 |= 100 ，最后 n=1101 转化为十进制等于n=13。
• 上面函数的运算过程

• 
  
• HashMap的构造方法,设置容器的长度 但是指定的默认的扩展因子为 0.75

 public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }

• HashMap的构造方法,什么都不指定 都给默认的,我们自己最常用的。

 //什么都不指定 都给默认的
 public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

*HashMap的构造方法, 也可以new一个 map进去，这种的方式 我们使用的比较少

 public HashMap(Map<? extends K, ? extends V> m) {
 //默认指定了扩展的因子
 this.loadFactor = DEFAULT_LOAD_FACTOR;
 putMapEntries(m, false);
 }

• putMapEntries()方法,如果是构造函数到这里来的话，就会进入到threshold = tableSizeFor(t);这里来，然后遍历m,然后一个个元素去添加，如果装载进来的map集合过于巨大，建议使用源map的原型模式clone方法克隆一个。

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 int s = m.size();
 if (s > 0) {
 // 如果是hashmap中填充了一个map 就会走到这里来 table == null =true
 if (table == null) { // pre-size
 float ft = ((float)s / loadFactor) + 1.0F;
 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
 (int)ft : MAXIMUM_CAPACITY);
 // t=ft
 if (t > threshold)
 //也就会走到这里来
 threshold = tableSizeFor(t);
 } else if (s > threshold) {
 // 扩容机制
 resize();
 }
 // copy的过程 遍历hashmap的话，这个应该是最高效的方式
 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
 K key = e.getKey();
 V value = e.getValue();
 putVal(hash(key), key, value, false, evict);
 }
 }
 }

• 关键方法put，了解如何储存的数据

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

• putVal方法的详情，假装put数据去分析。

 // 在构造函数中，也调用了这个方法，唯一不同的地方就是 evict=fasle
 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;
 /*如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置*/
 if ((p = tab[i = (n - 1) & hash]) == null)
 // todo LinkedHashMap 重新重写了这个方法，然后使用了 LinkedHashMap.Entry 里面多了两个结点 Entry<K,V> before, after;
 tab[i] = newNode(hash, key, value, null);
 ///*表示有冲突,开始处理冲突*/
 else {
 Node<K,V> e; K k;
 /*检查第一个Node，p是不是要找的值*/
 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);
 //如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，　　　　　　
 //treeifyBin首先判断当前hashMap的长度，如果不足64，只进行
 //resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 /*如果有相同的key值就结束遍历*/
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 }
 /*就是链表上有相同的key值*/
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 if (!onlyIfAbsent || oldValue == null)
 e.value = value;
 // todo LinkedHashMap 对其重写
 afterNodeAccess(e);
 return oldValue;
 }
 }
 ++modCount;
 /*如果当前大小大于门限，门限原本是初始容量*0.75*/
 if (++size > threshold)
 resize();
 // todo LinkedHashMap 对其重写
 afterNodeInsertion(evict);
 return null;
 }

• 1、可以发现 table肯定为null,没有初始化，所以第一个判断条件肯定成立tab = table) == null || (n = tab.length) == 0,这里有个小小的问题，当tab = table) == null成立的时候，后面||的代码是不会执行的，所以不会抛出空指针的异常。也就会执行n = (tab = resize()).length;的代码

 transient Node<K,V>[] table;// 第一次table没有去初始化，肯定为null

• 2、关于 resize()的方法，其实这个也是很关键的方法，扩容

 // 扩容机制 HasMap的扩容机制resize();
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) {
 threshold = Integer.MAX_VALUE;
 return oldTab;
 }
 /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY)
 /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
 newThr = oldThr << 1; // double threshold
 }
 else if (oldThr > 0) // initial capacity was placed in threshold
 newCap = oldThr;
 /*如果旧表的长度的是0，就是说第一次初始化表*/
 else { // zero initial threshold signifies using defaults
 // todo 在new hashMap中的长度 ，然后调用了 put的方法的时候，就会发生一次扩容 ，长度为16
 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) {
 for (int j = 0; j < oldCap; ++j) {
 Node<K,V> e;
 if ((e = oldTab[j]) != null) {
 oldTab[j] = null;
 if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
 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为偶数一队，e.hash&oldCap为奇数一对
 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;
}

• 
  
• 3、回到putVal的方法中，那么 n = (tab = resize()).length;也就是n=16
• 
  
• 4、那么(p = tab[i = (n - 1) & hash]) == null是否成立呢，其实我们可以猜测下，第一次肯定是成立的，这里有个运算符，位与运算符&,把做运算的两个数都转化为二进制的，然后从高位开始比较，如果两个数都是1则为1，否者为0.如下面的 HashMap中的算法

 int newHash=hash("test");
 // 1的hash值=1 test :hash值=3556516
 System.out.println( "newHash 1的hash值="+newHash);
 i = (16 - 1) & newHash;
 // i值=1 test值=4
 System.out.println("newHash的 i值="+i);
 int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 

• 5、这样就是走到这里来tab[i] = newNode(hash, key, value, null);，也就是tab[0]=newNode。这里有个面试，面试经常问，这里注意到 tab 是 resize()方法返回的，在resize()方法中，又把table = newTab;,那么我们改动 tab能否去改变 table呢？其实是能够的，这里传递是地址值，如下面的Demo

 String[] newS=setTest();
 newS[0]="16";
 // newS =[Ljava.lang.String;@1e0b9a
 System.out.println("newS ="+newS);
 //newS =[Ljava.lang.String;@1e0b9a
 System.out.println("test ="+test);
 System.out.println("test="+test.length);
 System.out.println("test="+test[0]);
}
String[] test;
public String[] setTest(){
 String[] newS=new String[10];
 test=newS;
 return newS;
}

• 以上就是 HashMap第一次put数据的完整过程。
• 当多次的put数据的时候，如果 某个位置上的 hash值相同的话，准确的讲i = (n - 1) & hash 是这个值，取出来的 tab不为null，那么储存的结构转化为链表

for (int binCount = 0; ; ++binCount) {
 /*指针为空就挂在后面*/
 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 //如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，　　　　　　
 //treeifyBin首先判断当前hashMap的长度，如果不足64，只进行
 //resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 /*如果有相同的key值就结束遍历*/
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 

• 当一个位置上的大于 TREEIFY_THRESHOLD - 1 也就是 7的话，看是否需要改变冲突节点的存储结构.treeifyBin首先判断当前hashMap的长度，如果不足64，只进行resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树.如下图的结构
• 
  

 final void treeifyBin(Node<K,V>[] tab, int hash) {
 int n, index; Node<K,V> e;
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 TreeNode<K,V> hd = null, tl = null;
 do {
 TreeNode<K,V> p = replacementTreeNode(e, null);
 if (tl == null)
 hd = p;
 else {
 p.prev = tl;
 tl.next = p;
 }
 tl = p;
 } while ((e = e.next) != null);
 if ((tab[index] = hd) != null)
 hd.treeify(tab);
 }
 }

• 是所有链表上的数据结构都会转，不可能在一个链表上，即存在红黑树，也存在链表
• get方法相对应就简单了

 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;
 }

• HashMap 是一个线程不安全的容器，发生扩容时会出现环形链表从而导致死循环
• HashMap 是一个无序的 Map，因为每次根据 key的 hashCode映射到Entry 数组上，所以遍历出来的顺序并不是写入的顺序。
• HashMap 遍历的速度慢，底层决定了，插入删除的速度快，随机访问的速度也比较快