最近迷上了小灰的算法之旅，在读到数组这一章有了许多收获，在此总结一下。
一、 数组基本操作时间复杂度分析：
1.更新以及查找的时间复杂度都时O(1)
2.插入：可能涉及到数组扩容以及元素移动的问题，所以时间复杂度为O(n)
3.删除：在保障原来元素顺序的情况之下，时间复杂度为O(n)，还有种机灵的做法是将删除位置元素和最后一位元素进行交换，数组元素个数减一即可，时间复杂度为O(1)。
二、数组具有根据元素下标随机访问的特点，Hash表(散列表)运用的数组的这一特点，快速查找。
在Java中HashMap键值对为一个Entry对象，根据键的hashcode值转化为数组的下标。解决hash冲突有两种解决办法：①开放寻址法。②链表法
在Java中开放地址法在ThreadLocal有所运用。这里着重了解链表法，采用头插法在数组的每个元素的位置建立一条链表。
扩容操作可以减少hash冲突的发生，扩容操作与两个因素有关，一是加载因子（0.75），二是当前散列表的长度，扩容条件：HashMap.size >= Capacity * LoadFactor,扩容之后需要对原来散列表中的元素进行重新映射到新的散列表之中，因为是根据数组长度进行映射的。
jdk8及其之后为采用红黑树这种数据结构，加快了元素的插入以及查询效率。