Android开发经验谈Android开发Android开发

常用集合的原理分析

2018-08-21  本文已影响34人  仕明同学

一、ArrayList

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

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

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


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

二、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);
    }

三、LinckedList

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

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

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

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

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

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

四、HashMap

 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;

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


         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;

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

 //什么都不指定 都给默认的
    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);
    }

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

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


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;
                 

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

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

五、ConcurrentHashMap

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

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

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

volatile关键字 Java多线程的三大核心

1、 原子性 :java原子性和数据库事务的原子性差不多，一个操作要么是全部执行成功或者是失败.

2、可见性

*synchronized 和加锁也能保证可见性，实现原理就是在释放锁之前其余线程是访问不到这个共享变量的。但是和volatile 相比较起来开销比较大 ！

3、顺序性


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

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

   private void stop(){
       flag = false ;
   }

六、HashSet

    //  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();

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

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

七、LinkedHashMap

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

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

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

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

八、LruCache

 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());

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


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

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

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

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

 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

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

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

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

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

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

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

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

 // 要使用这个方法 好点 。
    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++;
    }

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

 /**
     * 二分查找
     * @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;
    }


 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+"   ");
        }

最后说明几点

上一篇下一篇

猜你喜欢

热点阅读