常用的数据结构分析
常用的数据结构
ArrayList：底层由数组实现，所以它在内存中是一块连续的空间
/**
两种情况，一种是直接在添加，那么它是添加在数组的最后，这个时候只需要让size++的元素填充为e
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
在指定的位置插入，System.arraycopy首先会将当前index到数组最后的元素后移拷贝一份，再将插入的元素插入index
*/
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
所以在add的时候如果是发生在中间的情况下，那么会发生一次数据拷贝
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove的操作同理，取出index坐标下的对象，然后通过数据拷贝将index+1到末尾的数据向前拷贝一位，并将数组中最后一位置为null，等待GC。
public E get(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
return (E) ArrayList.this.elementData[offset + index];
}
而因为ArrayList在内存中是一个连续的内存空间，所以当它声明后它的地址是已知的，如果在内部存入一个Object的对象（4个字节）那么只需要在这个地址上加4就能查询到对应的数据。
所以ArrayList在进行查询，和直接添加时效率高，但是在进行中间插入以及删除时会因为要进行一次数据拷贝，效率不高。
与ArrayList通常进行比较的是LinkedList，一个由链表机构构成的数据结构，它在内存中不是一块连续的空间，双向链表。
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 void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//返回指定下标的对象,get的实现也是通过这个方法来进行，所以我们没有办法通过第一个节点知道第10节点的对象，必须要进行循环查询。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
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;
}
}
//在succ之前插入一个元素，就是把succ的前驱节点设置给e，pred的后驱指向e，succ的前驱指向e，这样就完成了数据插入的操作。删除反之。
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
所以LinkedList是一种增删效率快，但是查询慢的数据结构。
那么有没有一种数据结构是同时具有两者优点的，HashMap
HashMap在1.7之前后之后的版本是不同的实现
之前的HashMap结构是由数组➕链表构成的
之后的HashMap是由数组➕链表➕红黑树构成的
hash碰撞的出现，以及解决方法？
HashMap的默认大小-》16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap什么时候扩容？由什么决定的？
长度为2的次幂的意义？
减小碰撞的可能
例子：
Length1 =10
Length2= 16
H1 110 = 6
H2 111 = 7
L1 ：9 = 1001
L2 ：15 = 1111
分别求模
110
1001 0000
111
1001 0001
110
1111 0110
111
1111 0111
可以发现非2次幂的情况下，中间两位为0，那么它就没有计算的意义，只有高位和低位有决定作用，而在2次幂的情况下，都为1那么都参与运算，减少了hashcode的冲突可能。
加载因子：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
阙值：0.75*16（length） = 12，就是如果是默认长度的情况下，如果数组长度》=12的话，那么就扩容。
扩容的意义：均匀分布，减小冲突
Android特有的数据结构：
SparseArray:双数组分别存储key和value，但key必须为int类型的数据，通过二分查找的方式去查询key的位置。
ArrayMap:
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
通过key的hash值查找在mHashes中的下标位置，并将key和value存入对应规则的indx下标对应的位置。
这里解决了SparseArray的key只能为int类型的限制，也是通过两个数组实现，两个数组分别存储的是key的Hash值，另外一个数组存储的是key和value，所以mArray的长度是mHashes的2倍，在mArray的下标也是2倍为key，2倍加1为value。
ArrayMap是如何解决Hash碰撞的：
int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
//通过hash获取一个下标后，在实际存储key和value的数组中拿出来跟实际的key比较一下，
//如果一样说明就是我们需要查找的下标位置
if (key.equals(mArray[index<<1])) {
return index;
}
// Search for a matching key after the index.
int end;
//因为如果出现hash碰撞的情况下，会将mHashes中存储的index加1直到没有冲突为止
//上一步获取到的key和实际的key不一样，就是出现了hash碰撞，那么在以这个index+1的起点向右查找,因为hash发生了碰撞，那么在一个范围内存储的hash是一样的，我们只需要在这个一样hash范围内查找
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
//向前查找
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;
}
所以相对于HashMap，这两者都是优化了内存空间的使用，因为HashMap是采用空间换时间的策略，只要到达75%的容量就会翻倍扩容，哪怕是只存储一个数据。
位运算：
- <<: 左移运算符号： num<<1 ,相当于num乘以2
-
: 右移运算符号： num>>1 ,相当于num除以2
-
:无符号右移，忽略符号位，空位都以0补齐