常用集合的原理分析

发布日期: 2018-08-22

文章字数: 13.2k

阅读时长: 58 分

阅读次数:

分析常用集合的底层的原理：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() 将指定的元素追加到列表的末尾

   public boolean add(E e) {
    // 比如说加了一个元素
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;//这里的推算是 elementData[0]=e
    return true;
}

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的线程不安全,通过下面的方式证明

final ArrayList<String> lists=new ArrayList<>();
      Thread t1= new Thread(){
          @Override
          public void run() {
              super.run();
              for (int i=0;i<25;i++){
                  lists.add("我是i="+i);
              }
          }
      };
      Thread t2= new Thread(){
          @Override
          public void run() {
              super.run();
              for (int i=25;i<50;i++){
                  lists.add("我是i="+i);
              }

          }
      };
      //主线程休眠1秒钟，以便t1和t2两个线程将lists填装完毕。
      t1.start();
      t2.start();
      try {
          Thread.sleep(1000);
          // 即使睡完觉了，但是也有可能长度不对
          for(int l=0;l<lists.size();l++){
              // todo   两个线程不断的插入的话，就会导致插入的是null     我是i=34   我是i=10   我是i=35   我是i=11   null   null   我是i=12   我是i=38   我是i=13   我是i=39
              System.out.print(lists.get(l)+"   ");
          }
      } catch (InterruptedException e) {
          e.printStackTrace();
      }

两个线程不断的插入的话，就会导致插入的是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 的拷贝数组来说效率要高上不少
1
2
3
4
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的构造方法,指定容量和扩展因子！

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;
     // 加入指定的容量为 10 那么新的扩容的临界值为 13
     this.threshold = tableSizeFor(initialCapacity);
 }

关于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。
上面函数的运算过程
- n |= n >>> 1;//9的二进制=1001 >>>表示无符号的右移 100 =十进制 4 n= 1001 |= 100
  - n |= n >>> 2; // 1101 移动两位 0011 |1101 等于1111
  - n |= n >>> 4;// 1111 移动4为 0000 |1111 =1111
  - n |= n >>> 8;// 1111 移动8为 0000 |1111 =1111
  - n |= n >>> 16;// 1111 移动16为 0000 |1111 =1111

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

1
2
3

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，了解如何储存的数据

1
2
3

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;的代码
1
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;
 }

扩容方法也比较复杂，带着问题来分析，第一次，put数据的时候，可以得出oldCap=0、oldThr=0;那么新的长度 newCap = DEFAULT_INITIAL_CAPACITY=16; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)=0.75*16=12,把新的长度赋值给threshold = newThr;
然后Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];,根据上面我们可以的得出 newCap=16;
- 由于 oldTab==null，所以，这几返回一个 newTab 这是一个长度为16的Node的数组
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;

1
2

* 当一个位置上的大于 ` TREEIFY_THRESHOLD - 1` 也就是 `7`的话，看是否需要改变冲突节点的存储结构.`treeifyBin`首先判断当前`hashMap`的长度，如果不足`64`，只进行`resize`，扩容`table`，如果达到64，那么将冲突的存储结构为红黑树.如下图的结构
![HashMap](https://upload-images.jianshu.io/upload_images/5363507-d8230dc20a3b52b2.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

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` 遍历的速度慢，底层决定了，插入删除的速度快，随机访问的速度也比较快

#### 五、ConcurrentHashMap
* 支持线程安全的并发容器 `ConcurrentHashMap`,原理和`HashMap`差不多，区别就是采用了` CAS + synchronized` 来保证并发安全性
* `putVal` 加了同步锁 `synchronized `

final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//根据 key 计算出 hashcode
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 判断是否需要进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f); //如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
else {
//如果都不满足，则利用 synchronized 锁写入数据
V oldVal = null;
// todo put 数据的时候加入了锁
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException(“Recursive update”);
}
}
if (binCount != 0) {
//如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}

*  `get`方法

public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果是红黑树那就按照树的方式获取值
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 就不满足那就按照链表的方式遍历获取值
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}

1	* 基本上的变量都是被`volatile`关键字修饰

transient volatile Node<K,V>[] table;
private transient volatile Node<K,V>[] nextTable;
private transient volatile long baseCount;

…

###  `volatile`关键字  `Java `多线程的三大核心 
####  1、 原子性 :java原子性和数据库事务的原子性差不多，一个操作要么是全部执行成功或者是失败.
  * JVM 只保证了基本的原子性，但是类似 i++ 之类的操作，看着好像是原子的操作，其实里面涉及到了三个步骤
    *  获取 i 的值
    *  自增
    *  在赋值给 i
  * 这三个步骤 要实现`i++` 这样的原子操作就需要用到 `synchronized `或者是 了`lock  `进行加锁处理。
  *  如果是基础类的自增操作可以使用` AtomicInteger` 这样的原子类来实现(其本质是利用了` CPU` 级别的 的 `CAS` 指令来完成的)。` AtomicInteger` 是线程安全的
* 其中用的最多的方法就是: incrementAndGet() 以原子的方式自增

AtomicInteger atomicInteger=new AtomicInteger();
int i = atomicInteger.incrementAndGet();
System.out.println(“i=”+i);

public final int incrementAndGet() {
     return U.getAndAddInt(this, VALUE, 1) + 1;
 }

####  2、可见性
  *  现在的计算机，由于 `cpu` 直接从 主内存中读取数据的效率不高。所以都会对应的 `cpu`高速缓存，先将主内存中的数据读取到缓存中，线程修改数据之后首先更新到缓存中，之后才会更新到主内存。如果此时还没有将数据更新到主内存其他的线程此时读取就是修改之前的数据 
  
  *  `volatile `关键字就是用于保存内存的可见性，当线程A更新了` volatite`的修饰的变量的话，他会立即刷新到主线程，并且将其余缓存中该变量的值清空，导致其余线程只能去主内存读取最新的值
  
  *` synchronized` 和加锁也能保证可见性，实现原理就是在释放锁之前其余线程是访问不到这个共享变量的。但是和` volatile` 相比较起来开销比较大 ！
  
  * 但是` volatile `不能够替换` synchronized `因为`volatile` 不能够保证原子性 (要么执行成功或者失败，没有中间的状态) 

#### 3、顺序性

int a = 100 ; //1
int b = 200 ; //2
int c = a + b ; //3

 
  * 正常的代码的执行顺序应该是`1》》2》》3 `。但是有时候 `JVM `为了提高整体的效率会进行指令重排导致执行顺序可能是 `2》》1》》3 `。但是`JVM` 也不能是 什么都进行重排，`是在保证最终结果和代码顺序执行结果是一致的情况下才可能会进行重排`
  * 重排在单线程中不会出现问题，但是在多线程中就会出现顺序不一致的问题 
  *  `java `中可以使用 `volatile` 关键字来保证顺序性，`synchronized `和`lock` 也可以来保证有序性，和保证 原子性的方式一样，通过同一段时间只能一个线程访问来实现的 
  * 除了 `volatile` 关键字显式的保证顺序之外，`jvm HIA`通过 `happen-before` 原则来隐式来保证顺序性。

*  `volitle`的应用，主要是在单利，个人感觉这是常用的在移动端的开发!当然可以使用内部类或者是单利去实现，[更多的设计模式](https://www.jianshu.com/p/4e01479b6a2c)   
   *  1、`volatile` 实现一个双重检查锁的单例模式

   public class Singleton {
    private static volatile Singleton singleton;

    private Singleton() {
    }

    public static Singleton getInstance() {
        if (singleton == null) {
            synchronized (Singleton.class) {
                if (singleton == null) {
                    singleton = new Singleton();
                }
            }
        }
        return singleton;
    }
}
 1
2
3
4
5
6
  * 这里的 `volatile` 关键字主要是为了防止指令重排。 如果不用` volatile `，`singleton = new Singleton()`;，这段代码其实是分为三步：
    * 分配内存空间。(1)
     *  初始化对象。(2)
     * 将 singleton 对象指向分配的内存地址。(3)
  * 加上` volatile` 是为了让以上的三步操作顺序执行，反之有可能第三步在第二步之前被执行就有可能导致某个线程拿到的单例对象还没有初始化，以致于使用报错。
*  2、控制停止线程的标记

private volatile boolean flag ;
private void run(){
new Thread(new Runnable() {
@Override
public void run() {
doSomeThing();
}
});
}

private void stop(){
    flag = false ;
}

 *  如果没有用`volatile` 来修饰` flag `，就有可能其中一个线程调用了 `stop()`方法修改了` flag `的值并不会立即刷新到主内存中，导致这个循环并不会立即停止.这里主要利用的是 `volatile` 的内存可见性 .


#### 六、HashSet
* `HashSet` 是一个不允许存储重复元素的集合。
* `HashSet`的源码只有三百多行，原理非常简单，主要底层还是`HashMap`。
*  `map` 和 `PERSENT`:

//  map ：用于存放最终数据的。
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
// PRESENT ：是所有写入 map 的 value 值。
private static final Object PRESENT = new Object();

1	* 构造方法:底层一个hashMap

public HashSet() {
    map = new HashMap<>();
}

* 关键的就是这个 `add() `方法。 可以看出它是将存放的对象当做了 `HashMap `的健，`value` 都是相同的 `RESENT `。由于 `HashMap` 的 `key` 是不能重复的，所以每当有重复的值写入到 `HashSet `时，`value `会被覆盖，但 `key `不会受到影响，这样就保证了` HashSet` 中只能存放不重复的元素。

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}



#### 七、LinkedHashMap
*  `HashMap` 是一个无序的 `Map`，每次根据 `key` 的 `hashcode` 映射到 `Entry` 数组上，所以遍历出来的顺序并不是写入的顺序。 因此 `JDK` 推出一个基于` HashMap `但具有顺序的` LinkedHashMap `来解决有排序需求的场景。它的底层是继承于` HashMap `实现的，由一个双向链表所构成。
* ` LinkedHashMap` 的排序方式有两种：
     *  根据写入顺序排序。
      *  根据访问顺序排序(LRU底层的原理)。 其中根据访问顺序排序时，每次` get `都会将访问的值移动到链表末尾，这样重复操作就能得到一个按照访问顺序排序的链表。
*  `LinkedHashMap`中的 `Entry`:利用了头节点和其余的各个节点之间通过 `Entry `中的 `after `和 `before `指针进行关联

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

* 变量

// 用于指向双向链表的头部
transient LinkedHashMap.Entry<K,V> head;
//用于指向双向链表的尾部

transient LinkedHashMap.Entry<K,V> tail;
// LinkedHashMap 如何达到有序的关键
//   todo   还有一个 accessOrder 成员变量，默认是 false，默认按照插入顺序排序，为 true 时按照访问顺序排序，也可以调用
final boolean accessOrder;

1	* 构造方法，`LRUchace `最近最少使用的缓存底层就是这个构造函数。

public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

1
2

* 侧重关注 `put`，会走父类`HashMap`中的`put`方法，具体请看`HashMap` `put` 方法的解释
   * 1、 在 `LinkedHashMap` 重写了,`newNode`的方法。 使用了` LinkedHashMap.Entry `里面多了两个结点    `Entry<K,V> before, after`;

  Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLast
    linkNodeLast(p);
    return p;
}
 1
*  2、实现了`afterNodeAccess()`方法， ` void afterNodeAccess(Node<K,V> p) { }`！此函数执行的效果就是将最近使用的Node，放在链表的最末尾。特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了！


 //  此函数执行的效果就是将最近使用的Node，放在链表的最末尾
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作
    if (accessOrder && (last = tail) != e) {
        //将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null
        p.after = null;
        //p前一个节点不存在，情况一
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
            //p的后一个节点不存在，情况二
        else
            last = b;
        if (last == null)
            head = p;
        else {    //正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p
            p.before = last;
            last.after = p;
        }
        //将p设置为将p设置为尾节点
        tail = p;
        ++modCount;    // 修改计数器+1
    }
}

 1
*  3、 `put`方法 执行的第二个步骤   ，这个方法没什么用尽可能删除最老的 插入后把最老的`Entry`删除，不过`removeEldestEntry`总是返回`false`，所以不会删除，估计又是一个方法给子类用的


void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // todo hashmap中移除 Node结点
        removeNode(hash(key), key, null, false, true);
    }
}
 // 如果映射表示缓存，这是有用的：它允许通过删除过时条目来减少内存消耗的映射。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
1
*  4 、`afterNodeRemoval()`移除结点也会重写，因为结点都不一样


   void afterNodeRemoval(Node<K,V> e) { // unlink
    //与afterNodeAccess一样，记录e的前后节点b，a
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //p已删除，前后指针都设置为null，便于GC回收
    p.before = p.after = null;
    //与afterNodeAccess一样类似，一顿判断，然后b，a互为前后节点
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
1
2

* `get()`方法详情,然后调用父类`HashMap` 的`getNode()`去找结点

public V get(Object key) {
Node<K,V> e;
//调用HashMap的getNode的方法，
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}

1	* `HashMap`中的`getNode()` 方法

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

1	* 关于访问顺序排序的Demo,我只想说明了一下，等于用了的数据，就会放在链表的末尾，这个类也是安卓中`LruCache`的底层原理

LinkedHashMap<String, Integer> map1 = new LinkedHashMap<String, Integer>(10, (float) 0.75,true);
map1.put(“1”,1) ;
map1.put(“2”,2) ;
map1.put(“3”,3) ;
map1.put(“4”,4) ;
map1.put(“5”,5) ;
map1.put(“6”,6) ;
map1.put(“7”,7) ;
map1.put(“8”,8) ;
map1.put(“9”,9) ;
map1.put(“10”,10) ;
map1.get(“6”);
// {1=1, 2=2, 3=3, 4=4, 5=5, 7=7, 8=8, 9=9, 10=10, 6=6}
System.out.println(“map1==”+map1);

  ![LinkedHashMap的原理.png](https://upload-images.jianshu.io/upload_images/5363507-704c9d041bbdeae2.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)




#### 八、LruCache
* `Android`中提供了一种基本的缓存策略，即`LRU（least recently used）`。基于该种策略，当存储空间用尽时，缓存会清除最近最少使用的对象
*  `LRU（Least Recently Used）`最近最少使用的，看了源码才知道核心是`LRUCache`类，这个类的核心其实是 `LinkedHashMap`类.
*  Demo 如下

LruCache<Integer,String> lruCache=new LruCache<>(5);
lruCache.put(1,”1”);
lruCache.put(2,”2”);
lruCache.put(3,”3”);
lruCache.put(4,”4”);
lruCache.put(5,”5”);

lruCache.get(1);
lruCache.get(2);
lruCache.get(3);
lruCache.get(4);
Map<Integer, String> snapshot = lruCache.snapshot();


//lruCache={5=5, 1=1, 2=2, 3=3, 4=4}    5最少使用到
System.out.println("lruCache="+snapshot.toString());
//当多添加一个的话，那么5就会被删除，加入6上去
lruCache.put(6,"6");
// new  lruCache={1=1, 2=2, 3=3, 4=4, 6=6}
Map<Integer, String> snapshot1 = lruCache.snapshot();
System.out.println(" new  lruCache="+snapshot1.toString());

1	* 构造方法,可以明显看出，底层使用的是`LinkedHashMap`.

public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException(“maxSize <= 0”);
}
this.maxSize = maxSize;
// 初始化这里就是 new的 true的所以使用的顺序排序
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

1
2


*  `put`方法 :重要的就是在添加过缓存对象后，调用` trimToSize()`方法，来判断缓存是否已满，如果满了就要删除近期最少使用的算法.同时线程也是安全的。

public final V put(K key, V value) {
//不可为空，否则抛出异常
if (key == null || value == null) {
throw new NullPointerException(“key == null || value == null”);
}

    V previous;
    // 多线程 可以使用
    synchronized (this) {
        //插入的缓存对象值加1
        putCount++;
        //增加已有缓存的大小
        size += safeSizeOf(key, value);
        //向map中加入缓存对象
        previous = map.put(key, value);
        if (previous != null) {
            //如果已有缓存对象，则缓存大小恢复到之前
            size -= safeSizeOf(key, previous);
        }
    }
    //entryRemoved()是个空方法，可以自行实现
    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }
    //调整缓存大小(关键方法)
    trimToSize(maxSize);
    return previous;
}

1	* 1、`safeSizeOf`方法,这个`sizeof`的方法，就是我们自己需要重写的，记得图片加载框架的设计，就会运用到他

private int safeSizeOf(K key, V value) {
    //  每一个的需要缓存的大小
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}
protected int sizeOf(K key, V value) {
    return 1;
}

* 2、调整缓存大小(关键方法) `trimToSize(maxSize);` `maxSize`也就是指定的大小，当`     if (size <= maxSize) { break; }`这个判断不成立的时候，就会往下走，迭代器就会去获取第一个对象，即队尾的元素，近期最少访问的元素。然后把它删除该对象，并更新缓存大小 `  map.remove(key);`

private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()

                        + ".sizeOf() is reporting inconsistent results!");
            }

            if (size <= maxSize) {
                break;
            }
            //迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
            Map.Entry<K, V> toEvict = null;
            for (Map.Entry<K, V> entry : map.entrySet()) {
                toEvict = entry;
            }
            if (toEvict == null) {
                break;
            }
            key = toEvict.getKey();
            value = toEvict.getValue();
            //删除该对象，并更新缓存大小
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
        }
        // 空实现
        entryRemoved(true, key, value, null);
    }
}

1 2	* 关于 `get`方法！也是一个同步的方法。

public final V get(K key) {
//key为空抛出异常
if (key == null) {
throw new NullPointerException(“key == null”);
}

V mapValue;
synchronized (this) {
    //获取对应的缓存对象
    //get()方法会实现将访问的元素更新到队列头部的功能
    // todo LinkedHashMap  里面已经实现了 如果 添加到头部去
    mapValue = map.get(key);
    if (mapValue != null) {
        hitCount++;
        return mapValue;
    }
    missCount++;
}

…
}

1 2	* `LruCache`使用的`Demo`,这个 `Demo` 就看看，没吊用。

public class ImageCache {
//定义LruCache，指定其key和保存数据的类型
private LruCache<String, Bitmap> mImageCache;

    ImageCache() {
        //获取当前进程可以使用的内存大小，单位换算为KB
        final int maxMemory = (int)(Runtime.getRuntime().maxMemory() / 1024);

        //取总内存的1/4作为缓存
        final int cacheSize = maxMemory / 4;

        //初始化LruCache
        mImageCache = new LruCache<String, Bitmap>(cacheSize) {

            //定义每一个存储对象的大小
            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
            }
        };
    }

    //获取数据
    public Bitmap getBitmap(String url) {
        return mImageCache.get(url);
    }

    //存储数据
    public void putBitmap(String url, Bitmap bitmap) {
        mImageCache.put(url, bitmap);
    }
}


#### 九、SparseArray
*  `SparseArray`是`android`里为`<Interger,Object>` 这样的`Hashmap`而专门写的类,目的是提高效率，其核心是折半查找函数（`binarySearch`）。` SparseArray  `仅仅提高内存效率，而不是提高执行效率，所以也决定它只适用于`android`系统（内存对android项目有多重要）`SparseArray`不需要开辟内存空间来额外存储外部映射，从而节省内存。

* 变量,核心就是两个数组:`mKeys`  `mValues`

//是否可以回收，即清理mValues中标记为DELETED的值的元素
private boolean mGarbage = false;
private int[] mKeys; //保存键的数组
private Object[] mValues; //保存值的数组
private int mSize; //当前已经保存的数据个数

* 构造方法 ：如果`initialCapacity=0`那么`mKeys,mValuse`都初始化为`size=0`的数组，当`initialCapacity>0`时，系统生成`length=initialCapacity`的`value`数组，同时新建一个同样长度的`key`数组。

 public SparseArray() {
    this(10);
  }
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        /* ArrayUtils.newUnpaddedObjectArray 的源码
   public static Object[] newUnpaddedObjectArray(int minLen) {
   return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen);
      }
         */
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

* 关于`put`方法,关键是通过二分查找，查找相对应的`i`角标,如果存在的话，直接赋值新的值，如果不存在的话，取 `~i` 位非运算符（`~`）: 十进制变二进制：原码--反码--加一（补码），相当于 value +1 然后 取反  就可以了.然后就会走到 ` mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);`和 ` mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);` 中，这样就完成了赋值的过程。

public void put(int key, E value) {
// 二分查找，这个i的值,
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果找到了，就把这个值给替换上去，或者是赋值上去
// 这里也就可以解释出为啥替换为最新的值
if (i >= 0) {
mValues[i] = value;
} else {
//这里就是key要插入的位置，上面二分查找方法提到过
//位非运算符（~）
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
       // 一个新的值  ，就会把key 和 value 和 i值插入到两个数组中
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        // todo    然后长度 加上 1   nice
        mSize++;
    }
}

1 2	* `get`方法:通过二分查找法，在`mKeys`数组中查询`key`的位置，然后返回`mValues`数组中对应位置的值，找不到则返回默认值

public E get(int key, E valueIfKeyNotFound) {
// 二分查找感觉不像啊卧槽
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

1 2	* `delete`其实就是把这个 `mValues[i]`标记为 `DELETED`.

public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
/
i>0表示，找到了key对应的下标，否则应该是负数。同时判断mValues[i] 是不是Object这个对象，如果不是，直接替换为Object（DELETE起到标记删除位置的作用）,并标记 mGarbage=true，注意：这里delete只操作了values数组，并没有去操作key数组; /
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}

1	* `removeReturnOld` 其实就是多了一步，把要删除的值返回，其余同`delete`一样

 public E removeReturnOld(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            final E old = (E) mValues[i];
            mValues[i] = DELETED;
            mGarbage = true;
            return old;
        }
    }
    return null;
}

1 2	* `clear` 这里要留意，`clear`只是清空了`values`数组，并没有操作`keys`数组,这里也是传递的地址值，然后通过`for`循环，把每个元素清空！

public void clear() {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}

* 其实还有个方法`append`,添加数据的时候最好去使用它，因为它会判断下`mSize != 0 && key <= mKeys[mSize - 1]`、如果满足了才会调用 `put`方法，不满足，直接添加数据，而不是一上来就开始进行二分查找。

// 要使用这个方法好点。
public void append(int key, E value) {
// 判断了是否需要二分查找，还是直接插入
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}

    if (mGarbage && mSize >= mKeys.length) {
        // 通过gc的方法，把DELETED值的 values 清空
        gc();
    }
    // 可以直接都要这里来 ，是最节约能量
    mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
    mValues = GrowingArrayUtils.append(mValues, mSize, value);
    mSize++;
}

1	* 关于原型模式中的深拷贝的实现，这里也帮我指明了，一定要记得拷贝类中的容器

@Override
@SuppressWarnings(“unchecked”)
public SparseArray clone() {
SparseArray clone = null;
try {
clone = (SparseArray) super.clone();
// 原型模式的深拷贝两个容器的拷贝的过程—-！！！
clone.mKeys = mKeys.clone();
clone.mValues = mValues.clone();
} catch (CloneNotSupportedException cnse) {
/ ignore /
}
return clone;
}


* 其他的 `SparseBooleanArray  SparseIntArray SparseLongArray` 的原理一样
*  `SparseArray`与`HashMap`无论是怎样进行插入,数据量相同时,前者都要比后者要省下一部分内存,但是效率呢？----在倒序插入的时候,`SparseArray`的插入时间和`HashMap`的插入时间远远不是一个数量级.由于`SparseArray`每次在插入的时候都要使用二分查找判断是否有相同的值被插入.因此这种倒序的情况是`SparseArray`效率最差的时候.

* 附赠一个二分查找

/**

 * 二分查找
 * @param ints  需要被查找的数组
 * @param length  数组的长度
 * @param value  查找的值
 */
private int binarySearch(int[] ints, int length, int value) {

    int i = 0;
    int h = length - 1;
    while (i <= h) {
        /**
         * >>>与>>唯一的不同是它无论原来的最左边是什么数，统统都用0填充。
         * —比如你的例子，byte是8位的，-1表示为byte型是11111111(补码表示法）
         * b>>>4就是无符号右移4位，即00001111，这样结果就是15。
         * 这里相当移动一位，除以二
         */
        //中间的角标
        final int mid = (i + h) >>> 1;// 第一次 2 第二次 mid=3 第三次mid=4
        final int midVal = ints[mid];// 第一次 3 第二次 midVal=4 第三次mid=5
        if (midVal < value) {
            i = mid + 1;// 第一次 3  第二次 i=4
        } else if (value < midVal) {
            h = mid - 1;
        } else if (value == midVal) {
            return mid; //第三次mid=5 返回了
        }
    }
    // 这个取反 ，相当于 value +1 然后 取反  就可以了
    return ~value;
}

1	* 附赠`System.arraycopy()` 的用法

int[] mKeys={10,5,14,5,46};
int[] newKeys=new int[5];
/*

 * @param      src      源数组。
 * @param      srcPos    表示源数组要复制的起始位置，
 * @param      dest     目的地数组。
 * @param      destPos  在目标数据中的起始位置。
 * @param      length   要复制的数组元素的数目。
 */
// todo  source of type android.util.SparseArray is not an array
// destPsot +length  不能超过 新的数组的长度
System.arraycopy(mKeys,0, newKeys, 2, 3);
for (Integer str : newKeys) {
    System.out.print("newKeys="+str+"   ");
}

最后说明几点

ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。
ArrayList遍历的速度快，插入删除速度慢，随机访问的速度快
LinkedList 插入，删除都是移动指针效率很高。查找需要进行遍历查询，效率较低。二分查找，如果查找的index的越接近size的一半的话，这样查找的效率很低
HashMap 是一个线程不安全的容器，发生扩容时会出现环形链表从而导致死循环
HashMap 是一个无序的 Map，因为每次根据 key的 hashCode映射到Entry 数组上，所以遍历出来的顺序并不是写入的顺序。
HashMap 遍历的速度慢，底层决定了，插入删除的速度快，随机访问的速度也比较快
ConcurrentHashMap 并发容器，区别就是采用了CAS + synchronized 来保证并发安全性
位与运算符&,把做运算的两个数都转化为二进制的，然后从高位开始比较，如果两个数都是1则为1，否者为0
无符号的右移（>>>）:按照二进制把数字右移指定数位，高位直接补零，低位移除！
a=a|b 等于 a|=b的意思就是把a和b按位或然后赋值给a 按位或的意思就是先把a和b都换成2进制，然后用或操作
- 位异或运算（^）: 运算规则是两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1
- HashSet 底层其实就是 HashMap，只不过是一个value都一样的HashSet.
- LRU（Least Recently Used）最近最少使用的，看了源码才知道核心是LRUCache类，这个类的核心其实是 LinkedHashMap类.
~i 位非运算符（~）: 十进制变二进制：原码–反码–加一（补码），相当于 value +1 然后取反就可以了
SparseArray SparseBooleanArray SparseIntArray SparseLongArray 的原理一样
SparseArray与HashMap无论是怎样进行插入,数据量相同时,前者都要比后者要省下一部分内存,但是效率呢？—-在倒序插入的时候,SparseArray的插入时间和HashMap的插入时间远远不是一个数量级.由于SparseArray每次在插入的时候都要使用二分查找判断是否有相同的值被插入.因此这种倒序的情况是SparseArray效率最差的时候.
二分查找，是当角标越接近数组长度的一半，效率越低
卧槽，刚看了一下总共将近一万字，光写的过程用了16个小时，整理资料大概是10个小时。