常见集合特性

int cursor; // 代表下一个要访问的元素下标 
int lastRet = ‐1; // 代表上一个要访问的元素下标 
int expectedModCount = modCount;//代表对 ArrayList 修改次数的期望值，初始值为 modCount 
//如果下一个元素的下标等于集合的大小 ，就证明到最后了
public boolean hasNext() {
 return cursor != size; 
}
// 获取下一个元素，在最开始时，下一个元素指针cursor=0，上一个元素指针lastRet =-1；
// 每调用一次next方法，将lastRet改为=cursor，然后cursor+1。返回当前下标元素。
public E next() 
// 删除上一次遍历的元素，每调用一次，lastRet的值都改为-1，同时cursor-1；
// 所以每删除上一个元素，就得遍历下一个元素，不然会报错。即只能从头删到尾。
public void remove()
@SuppressWarnings("unchecked") 
public E next() { 
  checkForComodification();//判断expectedModCount和modCount是否相等,ConcurrentModificationException
   int i = cursor; 
   if (i >= size)//对 cursor 进行判断，看是否超过集合大小和数组长度 
    throw new NoSuchElementException(); 
   Object[] elementData = ArrayList.this.elementData; 
   if (i >= elementData.length) 
    throw new ConcurrentModificationException(); 
   cursor = i + 1;//自增 1。开始时，cursor = 0，lastRet = ‐1；每调用一次next方 法，cursor和lastRet都会自增1。 
   return (E) elementData[lastRet = i];//将cursor赋值给lastRet，并返回下标为 lastRet 的元素 
} 
public void remove() { 
  if (lastRet < 0)//判断 lastRet 的值是否小于 0 
    throw new IllegalStateException(); 
  checkForComodification();//判断expectedModCount和modCount是否相等,ConcurrentModificationException 
  try { 
    ArrayList.this.remove(lastRet);//直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素 
    cursor = lastRet;//将 lastRet 赋值给 curso 
    lastRet = ‐1;//将 lastRet 重新赋值为 ‐1，并将 modCount 重新赋值给 expectedMo dCount。 
    expectedModCount = modCount; 
  } catch (IndexOutOfBoundsException ex) { 
    throw new ConcurrentModificationException(); 
  } 
} 
final void checkForComodification() { 
  if (modCount != expectedModCount) 
   throw new ConcurrentModificationException(); 
  } 
}

// 序列化版 本号（类文件签名），如果不写会默认生成，类内容的改变会影响签名变化，
// 导致反序列化失败 
private static final long serialVersionUID = 8683452581122892189L;
// 如果实例化时未指定容量，则在 初次添加元素时会进行扩容使用此容量作为数组长度 
private static final int DEFAULT_CAPACITY = 10;
// static修饰，所有的未指定容量的实例(也未添加元素)共享此数组，两个空的数组有什么区 别呢？
// 就是第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化 的。
// 以便确认如何扩容。空的构造器则初始化为10，有参构造器则按照扩容因子扩容 
private static final Object[] EMPTY_ELEMENTDATA = {}; 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
// arrayList真正存放元素的地方，长度大于等于size
transient Object[] elementData; 
//arrayList中的元素个数
private int size;

// 无参构造器，构造一个容量大小为 10 的空的 list 集合，但构造函数只是给 elementData 
// 赋值了一个空的数组，其实是在第一次添加元素时容量扩大至 10 的。
public ArrayList() { 
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
} 
// 当使用无参构造函数时是把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementDat a。
// 当 initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。
// 当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object数组并赋值给 ele mentData。 
public ArrayList(int initialCapacity) { 
 if (initialCapacity > 0) { 
   this.elementData = new Object[initialCapacity]; 
 } else if (initialCapacity == 0) { 
   this.elementData = EMPTY_ELEMENTDATA; 
 } else {  
   throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); 
 } 
} 
//将 Collection 转化为数组，数组长度赋值给 size。 如果 size 不为零，则判断 elem entData 的 class 类型是否为 ArrayList，不是的话则做一次转换。 如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。 
public ArrayList(Collection<? extends E> c) { 
  Object[] a = c.toArray();  
   if ((size = a.length) != 0) { 
     if (c.getClass() == ArrayList.class) { 
       elementData = a; 
     } else { 
       elementData = Arrays.copyOf(a, size, Object[].class);
     } 
   } else { 
     // 指向空数组 
     elementData = EMPTY_ELEMENTDATA; 
   } 
}

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

public void add(int index, E element) { 
  rangeCheckForAdd(index);//下标越界检查 
  ensureCapacityInternal(size + 1); //同上判断扩容,记录操作数
  // 依次复制插入位置及后面的数组元素，到后面一格，不是移动，因此复制完后，
  // 添加的下标位置和下一个位置指向对同一个对象 
  System.arraycopy(elementData, index, elementData, index + 1, size ‐ index); 
  elementData[index] = element;//再将元素赋值给该下标 
  size++;
}

private void grow(int minCapacity) { 
  int oldCapacity = elementData.length;//获取当前数组长度 
  int newCapacity = oldCapacity + (oldCapacity >> 1);//默认将扩容至原来容量的 1.5 倍
  // 如果1.5倍太小的话，则将我们所需的容量大小 赋值给newCapacity  
  if (newCapacity ‐ minCapacity < 0)
   newCapacity = minCapacity; 
  // 如果1.5倍太大或者我们需要的容量太大，那就直接
  // 拿newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MA X_ARRAY_SIZE 来扩容
  if (newCapacity ‐ MAX_ARRAY_SIZE > 0) 
   newCapacity = hugeCapacity(minCapacity); 
  // 然后将原数组中的数据 复制到大小为 newCapacity 的新数组中，并将新数组赋值给 elementData。
  elementData = Arrays.copyOf(elementData, newCapacity); 
}

public E remove(int index) {
  //  删除是否越界
  rangeCheck(index);
  //  操作数加1
  modCount++;
  //  找出删除元素
  E oldValue = 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;
}

List aa= new ArrayList<>();
aa.add("111");
aa.add("112");
aa.add("113");
System.out.println(aa); // [111, 112, 113]
// 直接调内部方法清空
aa.clear();
System.out.println(aa);  // []
//  for循环清空，遍历list总数次，每次删除第一个元素
int b =aa.size();
for (int i = 0; i < b; i++) {
    aa.remove(0);
}
System.out.println(aa);  // []
//  迭代器清空，每次判断下一个元素是否存在，存在先遍历该元素，然后删除该元素
Iterator  it =aa.iterator();
while (it.hasNext()){
    it.next();
    it.remove();
}

LinkedList（） // 用于创建一个空的链表。
LinkedList(Collection<? extends E> collection) // 创建一个LinkedList，保护Collection中的全部元素。

boolean add（Object element）// 它将元素附加到列表的末尾。
void addFirst(E element) // 元素附加到列表的头部
void addLast(Eelement) // 元素附加到列表的尾部

Object getFirst() // 它返回链表的第一个元素。
Object getLast() // 它返回链接列表的最后一个元素。

int indexOf(Object element) // 如果找到元素，它将返回元素第一次出现的索引。否则，它返回-1。
int lastIndexOf(Object element) // 如果找到元素，它将返回元素最后一次出现的索引。否则，它返回-1。

E remove(int location)
E removeFirst() // 删除并返回链接列表的头部一个元素
E removeLast() // 删除并返回链接列表的尾部一个元素

void clear() // 它删除列表中的所有元素。
Object clone() // 它用于制作现有链接列表的副本。
Object set(int index，Object element) // 它用于用新元素替换列表中的现有元素。
boolean contains(Object element) // 如果元素存在于列表中，则返回true。

// LinkedList内部有迭代器类，可以使用迭代器遍历
Iterator<String> it = li.iterator();
while (it.hasNext()) {
  System.out.println(it.next());      
}
// for循环遍历
for(int i=0;i<lList.size();i++){
  System.out.println(lList.get(i));
}

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            //e为空时循环结束
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                // 成环的代码主要是在这三行代码
                // 首先插入是从头开始插入的
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }