SparseArray实现原理

SparseArray

SparseArray原理：
SparseArray采用两个数组,用来存放key以及value值的，核心思想是通过折半查找来找到key对应的位置，然后取出值，或者插入值！

二分查找

static int binarySearch(int[] array, int size, int value) {
  int lo = 0;
  int hi = size - 1;

  while (lo <= hi) {
    final int mid = (lo + hi) >>> 1;
    final int midVal = array[mid];

    if (midVal < value) {
      lo = mid + 1;
    } else if (midVal > value) {
      hi = mid - 1;
    } else {
      return mid; // value found
    }
  }
  //没有找到，返回最后下标的相反值
  return ~lo; // value not present
}

初始化

public SparseArray(int initialCapacity) {
  if (initialCapacity == 0) {
    mKeys = EmptyArray.INT;
    mValues = EmptyArray.OBJECT;
  } else {
    mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
    mKeys = new int[mValues.length];
  }
  mSize = 0;
}

get

public E get(int key, E valueIfKeyNotFound) {
  // 通过二分查找找到key对应的在keys数组下标的位置i，找到就返回values[i]
  int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

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

put

public void put(int key, E value) {
  // 找到位置
  int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

  if (i >= 0) {
   //找到，直接替换原来的值
    mValues[i] = value;
  } else {
    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);
    }

     //扩容顺序插入，保证数组里面的值是有序的
    mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
    mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
    mSize++;
  }
}