Java_集合类

柔情只为你懂 2022-03-10 01:22 312阅读 0赞

1.List  
ArrayList  
LinkedList  
2.Map  
HashMap  
HashTable  
TreeMap  
LinkedHashMap  
3.Set  
HashSet  
TreeSet  
LinkedHashSet

## ArrayList ： ##

List接口的可变数组的实现。实现了所有可选列表操作，并允许包括null在内的所有元素。  
非线程安全。  
底层使用的数据结构为数组。  
适合查改，弱于增删。

//用指定的元素代替此列表中指定位置上的元素，并返回位于以前位于该位置上的元素。

public E set (intdex, E element) {
    	RangeCheck(index); //检查index是否合法
    	E oldValue = (E)elementData[index];
    	elementData[index] = element;
    	return oldValue;
    }

//将制定的元素添加到此列表的尾部。直接添加速度块。

public boolean addE(E e) {
    	ensureCapacity(size + 1);//确保容量满足
    	elementData[size++] = e;
    	return true;
    }

ArrayList实现分析  
//将指定的元素插入此列表中的指定位置。  
//如果当前的位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索 引加1）。  
//涉及数组拷贝，插入速度不急add(E element)方法

public void add (int index, E element) {
    	if (index > size ||  index < 0)
    		throw new indexOutOfBoundsException("index:"+index+",Size:"+size);
    	//如果数组长度不足，将进行扩容。	
    	ensureCapacity(size + 1);
    	System.arraycopy(elementData,index,elementData,index+1,size-index);
    	elementData [index] = element;
    	size++;
    }

//移除此列表中指定位置上的元素。  
//设计数组拷贝。

public  E remove (int index) {
    	RangeCheck(index);
    	
    	modCount++;
    	E oldValue = (E) elementData[index];
    	
    	int numMoved = size - index -1;
    	if (numMoved > 0)
    		System.arrycopy (elementData,index+1,elementData,index,numMoved);
    	elementData[--size] = null;
    
    	return oldValue;
    }

//数组扩容，按照1.5倍方式扩充。涉及数组拷贝，速度慢。

public void ensureCapacity(int minCapacity) {
    	modCount ++;
    	int oldCapacity = elementData.length;
    	if (minCapacity > oldCapacity) {
    		int newCapacity= (oldCapacity * 3)/2 +1;
    		if (newCapacity<minCapacity)
    			newCapacity = minCapacity;
    	elementData = Arrays.copyOf(elementData,newCapacity);
    	}
    }

## LinkedList: ##

List接口的链接列表实现。实现所有可选的列表操作，并允许所有元素(包括null)。  
实现Deque接口，为add，poll提供先进先出队列操作以及其他堆栈和双端队列操作。  
非线程安全。  
适合增删，弱于查改。

private transient Entry<E> header = new Entry <E> (null,null,null);
    private static class Entry<E> {
    	E element ;
    	Entry<E> next;
    	Entry<E>previous;
    	//构造方法：目标对象paramE将被放置在paramEntry1之前，paramEntry2之后
    	Entry (E paramE , Entry<E> paramEntry1,Entry<E>paramEntry2) {
    		this.element = paramE;
    		this.next = paramEntry1;
    		this.previdous = paranEntry2;
    		}
    }

LinkedList 实现分析

//根据序号获取Entry对象
    private Entry<E> entry (int paranInt) {
    	if ((paramlnt<0) || (paramlnt >= this.size)) {
    		throw new lindexOutOfBoundsException("Index: " + parament + "Size: " +this.size);  }
    	Entry localEntry = this.header;
    	int i;
    	//最多遍历size/2个元素
    	if (paramlnt < this.size>>1) {
    		for (i=0;i<=paramlnt;i++)
    			localEntry = localEntry.next;
    	}else {
    		for (i<this.size;i>paramlnt;i--)
    			localEntry = localEntry.previous;
    	}
    	return localEntry;
    }

LinkedList实现分析

/***
    *要添加的元素：paramE
    *目标对象： paramEntry
    *插入速度快
    */
    private Entry<E> addBefore (E paramE, Entry<E> paramEntry) {
    	//要添加的对象，设置其previous和next
    	Entry localEntry = new Entry(paranE, paramEntry,paramEntry,paramEntry.previous);	
    
    	localEntry.previous.next = localEntry;
    	localEntry.next.previous = localEntry;
    
    	this.size +=1;
    	this.modCount +=1;
    	return localEntry;
    }

LinkedList添加元素

//指定位置添加元素，需要先找到index的元素，然后添加
    public void add(int index, E element) {
    	addBefore( element, (index==size ? header: entry(index)));
    }
    //队首添加元素
    public void addFirst (E paramE) {
    	addBefore(paramE,this.header.next);
    }
    //队尾添加元素
    public void addLast (E paramE) {
    	addBefore(paramE,this.header);
    }

//删除速度快
    private E remove(Entry<E> e) {
    	if (e == header)
    		throw new NoSuchElementException();
    		//保留将被移除的节点e的内容
    	E result = e.element;
    		//将前一节点的next引用赋值为e的下一节点
    	e.previous.next = e.next;
    		//将e的下一节点的previous赋值为的上一节点	
    	e.next.previous=e.previous;
    		//解除e节点对前后节点的引用
    	e.next = e.previous = null;
    	e.element = null;
    	size --;
    	modCount++;
    	return result;
    }

//删除

public E remove () {
    	return removeFirst();
    }
    public E remove (int index) {
    	return remove(entry(index));
    }
    public E remoeFirst() {
    	return remove(header.next);
    }
    public E removeLast() {
    	return remove(header.previous);
    }

查询 ArrayList 修改 LinkedList

## HashMap: ##

基于哈希表的Map接口实现。提供所有可选的映射操作，并允许使用null值和null值；  
非线程安全；  
不保证映射的顺序，特别是它不保证该顺序恒久不变。

//HashMap 数据结构
    transient Entry [] table;
    
    static class Entry <K,V> implements Map.Entry<K,V> {
    	final K key;
    	V value;
    	Entry <K,V> next;
    	final int hash;
    	...
    }

HashMap实现分析

public v put (K key, V value) {
    	if (key == null ) //null键视为相同的键
    		return putForNullKey (value); //根据key的keyCode重新计算hash值。
    	int hash = hash(ket.hashCode()); //搜索指定hash值在对应table中的索引。
    	int i = indexFor(hash，talbe.length); 
    			//如果i索引处的Entry不为null，通过循环不断遍历e元素的下一个元素。
    	for (Entry <K ,V> e = talbe[i]; e!= null; e= e.next() {
    		Object k;
    		if (e.hash == hash && 
    								((k = e.key == key ||  key.equal(k))) {
    			V oldValue = e.value;
    			e.value = value;
    			e.recordAccess(this);
    			return oldValue;
    		}
    	}
    	modCount ++;
    	addEntry (hash,key,value,i);
    	return null;
    }

//hash函数，加入了高位计算，防止低位不变，高位变化时，造成的hash冲突
    static int hash (int h) {
    	h ^=(h>>>20)^(h>>>12);
    	return h ^ (h >>>7) ^(h>>>4);
    }
    
    void addEntry (int hash, K key, V value, int bucketindex) {
    	//获取指定bucketindex 索引处的Entry
    	Entry<K,V> e = table [bucketIndex];
    	//将新创建的Entry放入 bucketlndex 索引处，并让新的Entry指向原来的Entry
    	table[budketIndex] = new Entry <K,V> (hash,key,value,e);
    	//如果Map中的key-value对的数量超过了极限。
    	if (size++> = threshold)
    	//把table对象的长度扩充到原来的2倍。
    		resize (2*table.lenth);
    	}
    	//根据hash值查找对应的table位置
    	static int inedxFor (int h, int length) {
    		return h & (length - 1);
    	}

//put的反过程
    public V get (Object key) {
    	if (key == null ) 
    		return getForNullKey();
    	int (hash = hash (key.hashCode());
    	for (Entry <K,V> e = table [indexFor(hash,table.length)];
    		e != null;
    		e  = e.next;){ 
    		Object k;
    		if (e.hash ==hash && ((k = e.key)==key||key.equals(k)))
    			return e.value
    		}
    		return null;
    }

## HashTable ##

的特点  
HashTable和HashMap 采用相同的存储机制，二者的实现基本一致；  
不允许有null值的存在；  
HashTable 是线程安全，内部的方法基本都是synchronized;  
迭代器具有强一致性。

## TreeMap ##

: 红黑树  
Entry 是红黑树的节点，它包含了红黑树的6个基本组成成分：key(键），value（值），left （左孩子），right（右孩子），parent （父节点），color（颜色），Entry节点根据key进行排序，Entry节点包含的内容为value。  
红黑树排序时，根据Entry中的key进行排序。Entry中的key比较大小是根据比较器conparator来进行判断的。

空间利用率高 （HashMap的数组大小必须为2的n次方/TreeMap中树的每一个节点就代表了一个元素）  
性能稳定（Hash碰撞会导致HashMap查询开销提高 / 扩容时会rehash，开销高/  
TreeMap的操作均能在O(log n)内完成。

## LinkedHashMap: ##

Map接口的哈希表和链接列表实现，提供所有可选的映射操作，并允许使用null值和null键 / 非线程安全 / 具有可预知的迭代顺序

//LinkedHashMap实现分析
    void addEntry(int hash,K key, V value, int bukerlndex) {
    	//调用create方法，将新元素以双向链表的形式加入到映射中。
    	createEntry (hash,key,value,bucketlndex);
    	Entry <K,V> eldest = header.after;
    	if (removeEldestEntry (eldest)) {
    		removeEntryForKey(eldest.key):
    	}else {
    		if (size >= threshold)
    			resize(2*table.length);
    	}
    }
    void certeEntry(int hash, K key, V value,int bucketindex) {
    	HashMap .Entry <K,V> old = table [bucketindex];
    	Entry <K,V>  e  = new Entry <K,V> (hash,key,value,old);
    	table [bucketindex] = e;
    	//调用元素的addBrefore方法，将元素加入到双向链接列表。
    	e.addBefore(header);
    	size++;
    }

//LinkedHashMap实现分析
    public V get( Object key) {
    	//调用父类HasMap的getEntry()方法，取得 要查找的元素。
    	Entry <K,V> e =(Entry<K,V>getEntry(key);
    	if (e==null)
    		return null'
    	//记录访问顺序。
    	e.recourdAccess(this);
    	return  e,value;
    }
    void recordAccess(HashMap<K,V>)m;
    //如果定义了LinkedHashMap的迭代顺序为访问顺序，
    //则删除以前位置上的元素，并将最新访问的元素添加到链表表头；
    if (lm.accessOder) {
    	lm.modCount++;
    	remove();
    	addBefore (lm.header);;
    	}
    }

Map的适用范围：  
HashMap适用于一般的键值映射需求；  
HashTabel适用于有多线程并发的场合；  
TreeMap适用于要按照键排序的迭代场合；  
LinkedHashMap 适用于特殊顺序的迭代场合；（如LRU算法）

## HashSet ##

实现分析

//底层使用HashMap来保存HashSet中所有元素。
    private transient Hash <E,Object> map;
    //定义一个虚拟的Object对象作为HashMap的value
    private static final Object PRESENT = new Object();
    //借助HashMap的add方法可以返回key之前的value 值，如果为null则说明之前尚添加该key,即该HashSet还可以添加元素
    public boolean add (E e) {
    	return map.put (e.PRESENT) ==null;
    }
    //借助HashMap的方法来查找
    public boolean contains (Object o ) {
    	return map.containKey(o);
    	}

set 的特点

HashSet通过HashMap实现  
TreeSet通过TreeMap实现  
LinkedHashSet 通过 LinkedHashMap实现  
Set类于Map类拥有近似的使用特性