4、集合
Collection的方法: add(Object o):增加元素 addAll(Collection c):... clear():... contains(Object o):是否包含指定元素 containsAll(Collection c):是否包含集合c中的所有元素 iterator():返回Iterator对象,用于遍历集合中的元素 remove(Object o):移除元素 removeAll(Collection c):相当于减集合c retainAll(Collection c):相当于求与c的交集 size():返回元素个数 toArray():把集合转换为一个数组 TreeSet的方法: first():返回第一个元素 last():返回最后一个元素 lower(Object o):返回指定元素之前的元素 higher(Obect o):返回指定元素之后的元素 subSet(fromElement, toElement):返回子集合 List的方法: add(int index, Object o):在指定位置插入元素 addAll(int index, Collection c):... get(int index):取得指定位置元素 indexOf(Obejct o):返回对象o在集合中第一次出现的位置 lastIndexOf(Object o):... remove(int index):删除并返回指定位置的元素 set(int index, Object o):替换指定位置元素 subList(int fromIndex, int endIndex):返回子集合 Queue的方法: boolean add(E e) : 将元素加入到队尾,不建议使用 boolean offer(E e): 将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。推荐使用此方法取代add E remove(): 获取头部元素并且删除元素,不建议使用 E poll(): 获取头部元素并且删除元素,队列为空返回null;推荐使用此方法取代remove E element(): 获取但是不移除此队列的头 E peek(): 获取队列头部元素却不删除元素,队列为空返回null ArrayDeque和Deque的方法: addFirst(Object o):元素增加至队列开头 addLast(Object o):元素增加至队列末尾 poolFirst():获取并删除队列第一个元素,队列为空返回null poolLast():获取并删除队列最后一个元素,队列为空返回null pop():“栈”方法,出栈,相当于removeFirst() push(Object o):“栈”方法,入栈,相当于addFirst() removeFirst():获取并删除队列第一个元素 removeLast():获取并删除队列最后一个元素(3)ArrayList
添加: 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++; } public boolean addAll(Collection<? extends E>c){ Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size+numNew); System.arraycopy(a,0,elementData,size,numNew); size += numNew; return numNew !=0; } public boolean addAll(int index,Collection<? extends E>c){ rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size+numNew); int numMoved = size-index; if(numMoved > 0){ System.arraycopy(elementData,index,elementData,index+1,numMoved) System.arraycopy(a,0,elementData,index,numNew); size += numNew; return numNew != 0; } } 删除: public E remove(int index) { rangeCheck(index); 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; } 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; } protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } (3)HashMap代码 package kb08.util.map; import com.sun.org.apache.xpath.internal.operations.Bool; import kb08.util.Iterator; import kb08.util.List; import kb08.util.Map; import kb08.util.array.ArrayList; import kb08.util.link.LinkedList; public class HashMap<K,V> implements Map<K,V> { private static final int DEFAULT_CAPACITY = 16;//默认容量 private static final float EXPAND_FACTOR = 0.75f;//扩容因子 private static final float REDUCE_FACTOR = 0.25F;//收缩因子 private static final Object[] EMPTY = {}; private float expandFactor; private Object[] elementDate;//数据数组 private int size; public HashMap(){ this(DEFAULT_CAPACITY,EXPAND_FACTOR); } public HashMap(int capacity,float expandFactor){//用户自定义扩容因子和容量要满足一下范围,只是进行初始化 initElementData(capacity); this.expandFactor = expandFactor<=0.5 || expandFactor>=0.75 ? EXPAND_FACTOR : expandFactor; //输入一个扩容因子和EXPAND_FACTOR进行比较 } private void initElementData(int capacity){ elementDate = capacity<=1 ? EMPTY : new Object[Integer.highestOneBit(capacity-1)<<1]; } /** * 判定什么时候需要扩容 * @return -1:缩 0:不变 1:扩 */ private int needChange(){ double factor = size*1.0/elementDate.length; return factor>=expandFactor ? 1 : factor<=REDUCE_FACTOR ? -1 : 0; } private void expand(){ change(true); } private void reduce(){ change(false); } //扩容:散列均匀,减少链表的数量和长度 private void change(boolean expand){ Object[] copy = elementDate;//备份 size = 0; initElementData(expand ? elementDate.length<<1 : elementDate.length>>1); for (Object o : copy) { if (null==o){ continue; } if (o instanceof Entry){ put((Entry<K, V>) o); continue; } Iterator<Entry<K, V>> it = ((LinkedList<Entry<K, V>>) o).iterator(); while (it.hasNext()){ put(it.next()); } } } @Override public int size() { return size; } @Override public boolean isEmpty() { return 0==size; } @Override public boolean containsKey(K key) { return null != _get(key); } @Override public boolean containsValue(V value) { Iterator<V> it = values().iterator(); while (it.hasNext()){ V v = it.next(); if (value == v || (null!=value && value.equals(v)) || (null!=v && v.equals(value))){ return true; } } return false; } private Entry<K,V> _get(K key){ int index = index(key); Object o = elementDate[index]; Entry<K,V> e = null; if (null!=o){ if (o instanceof Entry){ e = (Entry<K,V>)o; }else{ Iterator<Entry<K,V>> it = ((LinkedList<Entry<K,V>>)o).iterator(); while (it.hasNext()) { if (key.equals(it.next().getKey())){ e = it.next(); break; } } } } return e; } @Override public V get(K key) { Entry<K,V> e = _get(key); return null == e ? null : e.getValue(); } private int index(K key){ return null==key ? elementDate.length-1 : key.hashCode()%(elementDate.length-1); } private V put(Entry<K,V> entry){ if (1==needChange()){ expand(); } int index = index(entry.getKey()); Object o = elementDate[index]; V v = null; boolean noRepeat = true; if (null==o){ elementDate[index] = entry; }else if (o instanceof Entry){ Entry<K,V> e = (Entry<K,V>) o;//e是旧值 if (null==e.getKey() || e.getKey().equals(entry.getKey())){ v = e.getValue(); e.setValue(entry.getValue()); noRepeat = false; }else { LinkedList<Entry<K,V>> list = new LinkedList<>(); list.add(e); list.add(entry); elementDate[index] = list; } }else { LinkedList<Entry<K, V>> list = (LinkedList<Entry<K, V>>) o; Iterator<Entry<K,V>> it = list.iterator(); while (it.hasNext()){ Entry<K,V> e = it.next(); if (e.getKey().equals(entry.getKey())){ v = e.getValue(); e.setValue(entry.getValue()); noRepeat = false; break; } } if (noRepeat){ list.add(entry); } } if (noRepeat){ size++; } return v; } @Override public V put(K key, V value) { return put(new Entry<>(key,value)); } @Override public V remove(K key) { if (needChange()==-1){ reduce(); } int index = index(key); Object o = elementDate[index]; V v = null; boolean exist = false; if (null != o){ if (o instanceof Entry){ v = ((Entry<K,V>)o).getValue(); elementDate[index] = null;//数组删除:提出元素后返回null exist = true; }else{ LinkedList<Entry<K, V>> list = (LinkedList<Entry<K, V>>) o; Iterator<Entry<K, V>> it = list.iterator(); while (it.hasNext()){ Entry<K, V> e = it.next(); if (e.getKey().equals(key)){ it.remove();//链表删除:remove v = e.getValue(); exist = true; break; } } if (exist && list.size()==1){ elementDate[index] = list.get(0); } } } if (exist){ size--; } return v; } @Override public List<K> keys() { List<K> list = new ArrayList<>(size);//把获取的键值放在数组中 for (Object o : elementDate) { if (null==o){ continue; } if (o instanceof Entry){ list.add(((Entry<K,V>)o).getKey()); }else { Iterator<Entry<K,V>> it = ((LinkedList<Entry<K,V>>)o).iterator(); while (it.hasNext()){ list.add(it.next().getKey()); } } } return list; } @Override public List<V> values() { List<V> list = new ArrayList<>(size); Iterator<K> it = keys().iterator(); while (it.hasNext()){ list.add(get(it.next())); } return list; } @Override public List<Entry<K, V>> entries() { List<Entry<K, V>> list = new ArrayList<>(size); Iterator<K> it = keys().iterator(); while (it.hasNext()){ list.add(_get(it.next())); } return list; } }