上海做网站 公司,青岛提供网站建设哪家便宜,建网站和建网店的区别,开展门户网站建设一、Collection 1、ArrayList
底层采用数组实现#xff0c;操作大多基于对数组的操作。 在添加和删除时需要做 System.arraycopy(native层方法) 拷贝工作。 添加元素时可能会扩容#xff0c;这要大量的拷贝工作#xff0c;删除元素时#xff0c;会把后面的元素向前拷贝。…一、Collection 1、ArrayList
底层采用数组实现操作大多基于对数组的操作。 在添加和删除时需要做 System.arraycopy(native层方法) 拷贝工作。 添加元素时可能会扩容这要大量的拷贝工作删除元素时会把后面的元素向前拷贝。所以增、删时效率不高。但set()、get()效率高。
1.ArrayList 的增、删方法
//这是添加元素的方法size默认为0
public boolean add(E e) {ensureCapacityInternal(size 1);//元素添加到集合 技术点size表示选赋值后加1size表示先加1后赋值。elementData[size] e;return true;
}private void ensureCapacityInternal(int minCapacity) {//如果是使用无参构造会进入到这里那么minCapacity 值为10第一次进来 minCapacity 是1最大值就是 DEFAULT_CAPACITY 了。if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}//最核心的grow方法
private void ensureExplicitCapacity(int minCapacity) {modCount;//如果第一次进入minCapacity 为10条件成立进行扩容。当集合数据存满后继续扩容。if (minCapacity - elementData.length 0)grow(minCapacity);
}
//扩容核心方法
private void grow(int minCapacity) {//默认为零int oldCapacity elementData.length;//oldCapacity 1 是位运算右移一位相当于是除以2。所以从这里可以看出扩容后newCapacity 是原来的1.5倍。//如果集合数据存满后再次扩容newCapacity105int newCapacity oldCapacity (oldCapacity 1);//如果是无参构造 第一次进入 newCapacity为0minCapacity为10条件成立if (newCapacity - minCapacity 0)newCapacity minCapacity;if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);//扩容开始 拷贝elementData数组为新数组长度为newCapacityelementData Arrays.copyOf(elementData, newCapacity);
}//根据索引删除
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, index1, elementData, index, numMoved);elementData[--size] null; return oldValue;
}//根据对象删除
public boolean remove(Object o) {if (o null) {for (int index 0; index size; index)if (elementData[index] null) {fastRemove(index);return true;}} else {//遍历进行查找for (int index 0; index size; index)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
}
2.ArrayList 的改、查方法
// set() 方法
public E set(int index, E element) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));E oldValue (E) elementData[index];elementData[index] element;return oldValue;
}// get() 方法
public E get(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));return (E) elementData[index];
}
2、ArrayDeque 3、LinkedList
双向链表结构Node中保存了数据、前指针、后指针。 增删数据时只更换修改节点的前后指针无需拷贝速度较快。 查询时需要遍历速度较慢。 链表不存在容量不足的问题没有扩容机制更适合删除和添加。
//头节点指针
transient NodeE first;//尾节点指针
transient NodeE last;public LinkedList() {
}
//Node实例next上一个元素的指针prev下一个元素的指针。
private static class NodeE {E item;NodeE next;NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}
1.LinkedList的增、删方法
add 尾部时(默认新元素插入尾部)
void linkLast(E e) {final NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;
}
add插入到链表头部
private void linkFirst(E e) {final NodeE f first;final NodeE newNode new Node(null, e, f);first newNode;if (f null)last newNode;elsef.prev newNode;size;modCount;
}remove删除头节点
private E unlinkFirst(NodeE f) {// assert f first f ! null;final E element f.item;final NodeE next f.next;f.item null;f.next null; // help GCfirst next;if (next null)last null;elsenext.prev null;size--;modCount;return element;
}remove尾结点
private E unlinkLast(NodeE l) {// assert l last l ! null;final E element l.item;final NodeE prev l.prev;l.item null;l.prev null; // help GClast prev;if (prev null)first null;elseprev.next null;size--;modCount;return element;
}remove按对象删除需要遍历节点
public boolean remove(Object o) {if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);return true;}}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}
2.LinkedList的set、get方法
set根据index修改元素需要遍历元素
public E set(int index, E element) {checkElementIndex(index);NodeE x node(index);E oldVal x.item;x.item element;return oldVal;
}get查询采用二分查找
//node方法用于查找当前节点
//判断index值是不是小于整个链表长度的一半整个if/else逻辑是在判断查找的位置是距离链表头近还是链表尾近
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];}
}
4、TreeSet 二、Map 1、TreeMap 2、HashMap
默认长度16扩容因子0.75。无序线程不安全key、value 都可以为 nullkey是包装类型。 jdk1.7用头插法由 数组 链表 组成链表是为了解决哈希冲突。 jdk1.8用尾插法由 数组链表红黑树红黑树条件链表长度大于8且数组长度大于64。 1.核心代码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {// 声明了一个局部变量 tab,局部变量 Node 类型的数据 p,int 类型 n,iNodeK,V[] tab; NodeK,V p; int n, i;// 首先将当前 hashmap 中的 table(哈希表)赋值给当前的局部变量 tab,然后判断tab 是不是空或者长度是不是 0,实际上就是判断当前 hashmap 中的哈希表是不是空或者长度等于 0if ((tab table) null || (n tab.length) 0)// 如果是空的或者长度等于0,代表现在还没哈希表,所以需要创建新的哈希表,默认就是创建了一个长度为 16 的哈希表n (tab resize()).length;// 将当前哈希表中与要插入的数据位置对应的数据取出来,(n - 1) hash])就是找当前要插入的数据应该在哈希表中的位置,如果没找到,代表哈希表中当前的位置是空的,否则就代表找到数据了, 并赋值给变量 pif ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);//创建一个新的数据,这个数据没有下一条,并将数据放到当前这个位置else { //代表要插入的数据所在的位置是有内容的// 声明了一个节点 e, 一个 key kNodeK,V e; K k;if (p.hash hash //如果当前位置上的那个数据的 hash 和我们要插入的 hash 是一样,代表没有放错位置// 如果当前这个数据的 key 和我们要放的 key 是一样的,实际操作应该是就替换值((k p.key) key || (key ! null key.equals(k))))// 将当前的节点赋值给局部变量 ee p;else if (p instanceof TreeNode)//如果当前节点的 key 和要插入的 key 不一样,然后要判断当前节点是不是一个红黑色类型的节点e ((TreeNodeK,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);//创建一个新的节点数据并放到当前遍历的节点的后面if (binCount TREEIFY_THRESHOLD - 1) // 重新计算当前链表的长度是不是超出了限制treeifyBin(tab, hash);//超出了之后就将当前链表转换为树,注意转换树的时候,如果当前数组的长度小于MIN_TREEIFY_CAPACITY(默认 64),会触发扩容,我个人感觉可能是因为觉得一个节点下面的数据都超过8 了,说明 hash寻址重复的厉害(比如数组长度为 16 ,hash 值刚好是 0或者 16 的倍数,导致都去同一个位置),需要重新扩容重新 hashbreak;}// 如果当前遍历到的数据和要插入的数据的 key 是一样,和上面之前的一样,赋值给变量 e,下面替换内容if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // 如果当前的节点不等于空,V oldValue e.value;// 将当前节点的值赋值给 oldvalueif (!onlyIfAbsent || oldValue null)e.value value; // 将当前要插入的 value 替换当前的节点里面值afterNodeAccess(e);return oldValue;}}modCount;// 增加长度if (size threshold)resize();// 如果当前的 hash表的长度已经超过了当前 hash 需要扩容的长度, 重新扩容,条件是 haspmap 中存放的数据超过了临界值(经过测试),而不是数组中被使用的下标afterNodeInsertion(evict);return null;
}2.扩容的方法
final NodeK,V[] resize() {// 创建一个临时变量用来存储当前的tableNodeK,V[] oldTab table;// 获取原来的table的长度大小判断当前的table是否为空如果为空则把0赋值给新定义的oldCap,否则以table的长度作为oldCap的大小int oldCap (oldTab null) ? 0 : oldTab.length;// 创建临时变量用来存储旧的阈值把旧table的阈值赋值给oldThr变量int oldThr threshold;// 定义变量newCap和newThr来存放新的table的容量和阈值默认都是0int newCap, newThr 0;// 判断旧容量是否大于0if (oldCap 0) {// 判断旧容量是否大于等于 允许的最大值2^30if (oldCap MAXIMUM_CAPACITY) {// 以int的最大值作为原来HashMap的阈值这样永远达不到阈值就不会扩容了threshold Integer.MAX_VALUE;// 因为旧容量已经达到了最大的HashMap容量不可以再扩容了将阈值变成最大值之后将原table返回return oldTab;}// 如果原table容量不超过HashMap的最大容量将原容量*2 赋值给变量newCap如果newCap不大于HashMap的最大容量并且原容量大于HashMap的默认容量else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 将newThr的值设置为原HashMap的阈值*2newThr oldThr 1; // double threshold}// 如果原容量不大于0即原table为null,则判断旧阈值是否大于0else if (oldThr 0) // 如果原table为Null且原阈值大于0说明当前是使用了构造方法指定了容量大小只是声明了HashMap但是还没有真正的初始化HashMap创建table数组只有在向里面插入数据才会触发扩容操作进而进行初始化// 将原阈值作为容量赋值给newCap当做newCap的值。由之前的源码分析可知此时原阈值存储的大小就是调用构造函数时指定的容量大小所以直接将原阈值赋值给新容量newCap oldThr;// 如果原容量不大于0并且原阈值也不大于0。这种情况说明调用的是无参构造方法还没有真正初始化HashMap只有put()数据的时候才会触发扩容操作进而进行初始化else { // zero initial threshold signifies using defaults// 则以默认容量作为newCap的值newCap DEFAULT_INITIAL_CAPACITY;// 以初始容量*默认负载因子的结果作为newThr值newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 经过上面的处理过程如果newThr值为0说明上面是进入到了原容量不大于0旧阈值大于0的判断分支。需要单独给newThr进行赋值if (newThr 0) {// 临时阈值 新容量 * 负载因子float ft (float)newCap * loadFactor;// 设置新的阈值 保证新容量小于最大总量 阈值要小于最大容量否则阈值就设置为int最大值newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 将新的阈值newThr赋值给threshold为新初始化的HashMap来使用threshold newThr;// 初始化一个新的容量大小为newCap的Node数组SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];// 将新创建的数组赋值给table完成扩容后的新数组创建table newTab;// 如果旧table不为null说明旧HashMap中有值if (oldTab ! null) {// 如果原来的HashMap中有值则遍历oldTab取出每一个键值对存入到新tablefor (int j 0; j oldCap; j) {// 创建一个临时变量e用来指向oldTab中的第j个键值对NodeK,V e;// 将oldTab[j]赋值给e并且判断原来table数组中第j个位置是否不为空if ((e oldTab[j]) ! null) {// 如果不为空则将oldTab[j]置为null释放内存方便gcoldTab[j] null;// 如果e.next null说明该位置的数组桶上没有连着额外的数组if (e.next null)// 此时以e.hash(newCap-1)的结果作为e在newTab中的位置将e直接放置在新数组的新位置即可newTab[e.hash (newCap - 1)] e;// 否则说明e的后面连接着链表或者红黑树判断e的类型是TreeNode还是Node,即链表和红黑树判断else if (e instanceof TreeNode)// 如果是红黑树则进行红黑树的处理。将Node类型的e强制转为TreeNode之所以能转换是因为TreeNode 是Node的子类// 拆分树具体源码解析会在后面的TreeNode章节中讲解((TreeNodeK,V)e).split(this, newTab, j, oldCap);// 当前节不是红黑树不是null并且还有下一个元素。那么此时为链表else { // preserve order/*这里定义了五个Node变量其中lo和hi是lower和higher的缩写也就是高位和低位,因为我们知道HashMap扩容时容量会扩到原容量的2倍也就是放在链表中的Node的位置可能保持不变或位置变成 原位置oldCap,在原位置基础上又加了一个数位置变高了这里的高低位就是这个意思低位指向的是保持原位置不变的节点高位指向的是需要更新位置的节点*/// Head指向的是链表的头节点Tail指向的是链表的尾节点NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;// 指向当前遍历到的节点的下一个节点NodeK,V next;// 循环遍历链表中的Nodedo {next e.next;/*如果e.hash oldCap 0注意这里是oldCap而不是oldCap-1。我们知道oldCap是2的次幂也就是1、2、4、8、16...转化为二进制之后都是最高位为1其它位为0。所以oldCap e.hash 也是只有e.hash值在oldCap二进制不为0的位对应的位也不为0时才会得到一个不为0的结果。举个例子我们知道10010 和00010 与1111的运算结果都是 0010 但是110010和010010与10000的运算结果是不一样的所以HashMap就是利用这一点来判断当前在链表中的数据在扩容时位置是保持不变还是位置移动oldCap。*/// 如果结果为0即位置保持不变if ((e.hash oldCap) 0) {// 如果是第一次遍历if (loTail null)// 让loHead e设置头节点loHead e;else// 否则,让loTail的next eloTail.next e;// 最后让loTail eloTail e;}/*其实if 和else 中做的事情是一样的本质上就是将不需要更新位置的节点加入到loHead为头节点的低位链表中将需要更新位置的节点加入到hiHead为头结点的高位链表中。我们看到有loHead和loTail两个Node,loHead为头节点然后loTail是尾节点在遍历的时候用来维护loHead即每次循环更新loHead的next。我们来举个例子比如原来的链表是A-B-C-D-E。我们这里把-假设成next关系这五个Node中只有C的hash oldCap ! 0 ,然后这个代码执行过程就是:第一次循环 先拿到A把A赋给loHead,然后loTail也是A第二次循环 此时e的为B而且loTail ! null,也就是进入上面的else分支把loTail.next B此时loTail中即A-B,同样反应在loHead中也是A-B,然后把loTail B第三次循环 此时e C由于C不满足 (e.hash oldCap) 0,进入到了我们下面的else分支其实做的事情和当前分支的意思一样只不过维护的是hiHead和hiTail。第四次循环 此时e的为DloTail ! null,进入上面的else分支把loTail.next D此时loTail中即B-D,同样反应在loHead中也是A-B-D,然后把loTail D*/else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);// 遍历结束即把table[j]中所有的Node处理完// 如果loTail不为空也保证了loHead不为空if (loTail ! null) {// 此时把loTail的next置空将低位链表构造完成loTail.next null;// 把loHead放在newTab数组的第j个位置上也就是这些节点保持在数组中的原位置不变newTab[j] loHead;}// 同理只不过hiHead中节点放的位置是joldCapif (hiTail ! null) {hiTail.next null;// hiHead链表中的节点都是需要更新位置的节点newTab[j oldCap] hiHead;}}}}}// 最后返回newTabreturn newTab;
}
