深入理解Java集合

目录

一.集合概述 

二.List

2.1 手动实现简单的ArrayList

2.2 手动实现LinkeList

三.Map

3.1 手动实现HashMap

3.2 TreeMap

四.Set

4.1 手动实现HashSet

4.2 TreeSet

​

五.集合的遍历

5.1 遍历List

5.2 遍历Set

5.3 遍历Map

六.Collections

七.集合总结

一.集合概述 

二.List

2.1 手动实现简单的ArrayList

public class MyArrayList<E> {
	//底层是一个数组
	private Object[]  elementData;
	//定义一个变量标记数组所含内容的数量
	private int  size;
	//定义数组长度
	private static final int DEFALT_CAPACITY = 10 ;
	
	//无参构造初始化一个长度为10的Object数组
	public MyArrayList(){
		elementData = new Object[DEFALT_CAPACITY]; 
	}
	//有参构造传递一个int变量构造数组
	public MyArrayList(int  capacity) {
		
		if(capacity<0){
			throw  new  RuntimeException("容器的容量不能为负数");
		} else if(capacity==0){
			elementData  = new Object[DEFALT_CAPACITY];
		}else{
			elementData  = new Object[capacity];
		}
		
		
	}
	
	public int size(){
		return size;
	}
	
	public  boolean isEmpty(){
		return  size==0?true:false;
	}
	
	
	public  void  add(E  element){
		
		//什么时候扩容？？
		if(size == elementData.length){
			//扩容操作
			Object[]  newArray  =  new Object[elementData.length+(elementData.length>>1)];  //10-->10+10/2
			//使用系统函数进行拷贝，将旧数组中从0开始的内容拷贝到新数组中下标0开始的位置
			System.arraycopy(elementData, 0, newArray, 0, elementData.length); 
			elementData = newArray;
		}
		
		elementData[size++] = element;
	}
	
	public  E  get(int index) {
		
		checkRange(index);
		
		return  (E)elementData[index];
	}
	
	public void set(E element, int  index) {
		
		checkRange(index);
		
		elementData[index] = element;
		
	}
	
	public  void  checkRange(int index ){
		//索引合法判断 [0,size)    10    0-9
				if(index<0||index>size-1){
					//不合法
					throw  new RuntimeException("索引不合法:"+index);
				}
	}
	
	public void  remove(E  element){
		//element，将它和所有元素挨个比较，获得第一个比较为true的，返回。
		for(int i=0;i<size;i++){
			if(element.equals(get(i))){   //容器中所有的比较操作，都是用的equals而不是==
				
				//将该元素从此处移除
				remove(i);
			}
		}
	}
	
	public  void  remove(int index){
		
		//a,b,c,d,e,f,g,h
		//a,b,c,e,f,g,h,h
		int numMoved = elementData.length-index-1;
		if(numMoved>0){
			System.arraycopy(elementData, index+1, elementData, index, numMoved);
		}
		
		elementData[--size] = null;
		
	}
	
	
	@Override
	public String toString() {
		
		StringBuilder  sb = new StringBuilder();
		
		//[a,b,c]
		sb.append("[");
		for(int i=0;i<size;i++){
			sb.append(elementData[i]+",");
		}
		sb.setCharAt(sb.length()-1, ']'); 
		
		return  sb.toString();
	}
	
}
           

2.2 手动实现LinkeList

创建节点类

public class Node {
	
	Node  previous;		//上一个节点
	Node next;				//下一个节点

	Object element;		//元素数据
	
	public Node(Node previous, Node next, Object element) {
		super();
		this.previous = previous;
		this.next = next;
		this.element = element;
	}

	public Node(Object element) {
		super();
		this.element = element;
	}
	
}
           

实现类

public class MyLinkedList<E> {
	
	private  Node  first;
	private  Node  last;
	
	private  int size;
	
	public  void  add(int index, E  element) {
		
		checkRange(index);
		
		Node  newNode = new Node(element);
		Node  temp  =  getNode(index);
		
		if(temp!=null){
			Node up = temp.previous;
			
			up.next = newNode;
			newNode.previous = up;
			
			newNode.next = temp;
			temp.previous = newNode;
		}
		
	}
	
	public   void  remove(int index){
		checkRange(index);
		Node  temp  =  getNode(index);
		
		if(temp!=null){
			Node  up = temp.previous;
			Node down = temp.next;
			
			if(up!=null){
				up.next = down;
			}
			
			if(down!=null){
				down.previous = up;
			}
			
			if(index==0){
				first = down;
			}
			
			if(index == size-1){
				last = up;
			}
			
			size--;
		}
		
	}
	
	//[]    
	//["a","b","c","d","e","f"]           2
	public  E  get(int index) {  
	
		checkRange(index);
		
		Node temp = getNode(index);
		
		return temp!=null?(E)temp.element:null;
	}
	
	private  void  checkRange(int index){
		if(index<0||index>size-1){
			throw  new RuntimeException("索引不合法:"+index);
		}
	}
	
	
	
	private   Node  getNode(int index){
		
		checkRange(index);
		
		Node  temp = null;
		
		if(index<=(size>>1)){   
			temp = first;
			for(int i=0;i<index;i++){
				temp = temp.next;
			}
		}else{
			temp = last;
			for(int i=size-1; i>index;i--){
				temp = temp.previous;
			}
		}
		
		return temp;
	}
	
	public  void  add(E  element) {
		Node  node  = new Node(element);
		
		if(first==null){
//			node.previous = null;
//			node.next = null;
			first = node;
			last = node;
		}else{
			
			node.previous = last;
			node.next = null;
			
			last.next = node;
			last = node;
			
		}
		
		size++;
		
	}
	
	@Override
	public String toString() {
		//[a,b,c]     first=a,    last=c
		//a,b,c
		StringBuilder   sb = new StringBuilder("[");
		Node  temp = first;
		while(temp!=null){
			sb.append(temp.element+",");
			temp = temp.next;
		}
		sb.setCharAt(sb.length()-1, ']'); 
		
		return sb.toString();
	}	
	
}
           

三.Map

3.1 手动实现HashMap

//节点类
public class Node3<K,V> {
	
	int  hash;
	K  key;
	V  value;
	Node3  next; 
	
}
           

//实现类
public class MyHashMap04<K,V> {
	
	Node3[]  table;    //位桶数组。bucket  array
	int size;				//存放的键值对的个数
	
	public MyHashMap04() {
		table = new Node3[16];    //长度一般定义成2的整数幂
	}
	
	
	public  V  get(K  key){
		
		int  hash = myHash(key.hashCode(), table.length);
		V value = null; 
		
		if(table[hash]!=null){
			Node3  temp = table[hash];
			
			while(temp!=null){
				
				if(temp.key.equals(key)){   //如果相等，则说明找到了键值对，返回相应的value
					value = (V)temp.value;
					break;
				}else{
					temp = temp.next;
				}
			}
			
		}
		
		return value;
	}
	
	
	public  void   put(K key,  V   value){
		
		//如果要完善，还需要考虑数组扩容的问题！！！
		
		//定义了新的节点对象
		Node3    newNode = new Node3();
		newNode.hash = myHash(key.hashCode(),table.length);
		newNode.key =  key;
		newNode.value = value;
		newNode.next = null;
		
		Node3 temp = table[newNode.hash];
		
		Node3  iterLast = null;  //正在遍历的最后一个元素
		boolean  keyRepeat = false;  
		if(temp==null){
			//此处数组元素为空，则直接将新节点放进去
			table[newNode.hash] = newNode;
			size++;
		}else{
			//此处数组元素不为空。则遍历对应链表。。
			while(temp!=null){
				
				//判断key如果重复，则覆盖
				if(temp.key.equals(key)){
					keyRepeat = true;
					temp.value =  value;  //只是覆盖value即可。其他的值(hash,key,next)保持不变。
					
					break;
					
				}else{
					//key不重复，则遍历下一个。
					iterLast = temp;
					temp = temp.next;
					
				}
			}
			
			if(!keyRepeat){   //没有发生key重复的情况，则添加到链表最后。
				iterLast.next = newNode;
				size++;
			}
			
		}
		
		
		
	}

	
	@Override
	public String toString() {
		//{10:aa,20:bb}
		StringBuilder  sb = new StringBuilder("{");
		
		//遍历bucket数组
		for(int i=0;i<table.length;i++){
			Node3  temp = table[i]; 
			
			//遍历链表
			while(temp!=null){
				sb.append(temp.key+":"+temp.value+",");
				temp  = temp.next;
			}
		}
		sb.setCharAt(sb.length()-1, '}'); 
		return sb.toString();
		
	}
}
           

3.2 TreeMap

/**
 * 测试TreeMap的使用
 * @author Administrator
 *
 */
public class TestTreeMap {
	public static void main(String[] args) {
		Map<Integer,String>  treemap1 = new TreeMap<>();
		treemap1.put(20, "aa");
		treemap1.put(3, "bb");
		treemap1.put(6, "cc");
		
		//按照key递增的方式排序
		for(Integer  key:treemap1.keySet()){
			System.out.println(key+"---"+treemap1.get(key)); 
		}
		
		
		Map<Emp,String>  treemap2 = new TreeMap<>();
		treemap2.put(new Emp(100,"张三",50000), "张三是一个好小伙");
		treemap2.put(new Emp(200,"李四",5000), "李四工作不积极");
		treemap2.put(new Emp(150,"王五",6000), "王五工作还不错");
		treemap2.put(new Emp(50,"赵六",6000), "赵六是个开心果");
		
		//按照key递增的方式排序
		for(Emp  key:treemap2.keySet()){
			System.out.println(key+"---"+treemap2.get(key)); 
		}		
		
	}
}

class Emp  implements Comparable<Emp>  {
	int id;
	String name;
	double salary;
	
	public Emp(int id, String name, double salary) {
		super();
		this.id = id;
		this.name = name;
		this.salary = salary;
	}

	@Override
	public String toString() {
		return  "id:"+id+",name:"+name+",salary:"+salary;
	}
	
	@Override
	public int compareTo(Emp o) {		//负数：小于，0：等于，正数：大于
		
		if(this.salary>o.salary){
			return 1;
		}else if(this.salary<o.salary){
			return -1;
		}else{
			if(this.id>o.id){
				return 1;
			}else if(this.id<o.id){
				return -1;
			}else{
				return 0;
			}
		}
		
	}
	
}
           

四.Set

4.1 手动实现HashSet

public class MyHashSet {
	
	HashMap map;
	
	private static final Object  PRESENT = new Object();
	
	public MyHashSet() {
		map = new HashMap();
	}
	
	public  int  size(){
		return  map.size();
	}
	
	public void add(Object o){
		map.put(o, PRESENT);
	}
	
	@Override
	public String toString() {
		
		StringBuilder   sb = new StringBuilder();
		sb.append("[");
		
		for(Object key:map.keySet()){
			sb.append(key+",");
		}
		sb.setCharAt(sb.length()-1, ']');  
		return  sb.toString();
		
	}
	
}
           

4.2 TreeSet

public class TestTreeSet {
	public static void main(String[] args) {
		Set<Integer>  set = new TreeSet<>();
		
		set.add(300);
		set.add(200);
		set.add(600);
		
		//按照元素递增的方式排好序
		for(Integer m:set){
			System.out.println(m);
		}
		
		Set<Emp2>  set2 = new TreeSet<>();
		set2.add(new Emp2(100,"张三",3000));
		set2.add(new Emp2(50,"李四",2000));
		set2.add(new Emp2(150,"王五",8000));
		set2.add(new Emp2(30,"赵六",20000));
		
		for(Emp2 m:set2){
			System.out.println(m);
		}
		
	}
}



class Emp2  implements Comparable<Emp2>  {
	int id;
	String name;
	double salary;
	
	public Emp2(int id, String name, double salary) {
		super();
		this.id = id;
		this.name = name;
		this.salary = salary;
	}

	@Override
	public String toString() {
		return  "id:"+id+",name:"+name+",salary:"+salary;
	}
	
	@Override
	public int compareTo(Emp2 o) {		//负数：小于，0：等于，正数：大于
		
		if(this.salary>o.salary){
			return 1;
		}else if(this.salary<o.salary){
			return -1;
		}else{
			if(this.id>o.id){
				return 1;
			}else if(this.id<o.id){
				return -1;
			}else{
				return 0;
			}
		}
		
	}
	
}
           

五.集合的遍历

5.1 遍历List

5.2 遍历Set

5.3 遍历Map

public static void testIteratorMap(){
		Map<Integer,String> map1 = new HashMap<>();
		map1.put(100, "aa");
		map1.put(200, "bb");
		map1.put(300, "cc");
		

		//第一种遍历Map的方式
		Set<Entry<Integer,String>>  ss =  map1.entrySet();
		for(Iterator<Entry<Integer,String>> iter=ss.iterator();iter.hasNext();){
			Entry<Integer,String> temp = iter.next();
			
			System.out.println(temp.getKey()+"--"+temp.getValue());
			
		}
		System.out.println("++++++++++++++++++++++++");
		//第二种遍历Map的方式
		Set<Integer>  keySet = map1.keySet();
		for(Iterator<Integer> iter=keySet.iterator();iter.hasNext(); ){
			Integer key = iter.next();
			System.out.println(key+"----"+map1.get(key));
		}
		
		
	}
           

六.Collections

/**
 * Collections辅助类的使用
 * Collection是接口，Collections是工具类
 *
 */
public class TestCollections {
	public static void main(String[] args) {
		List<String>  list  = new ArrayList<>();
		for(int i=0;i<10;i++){
			list.add("gao:"+i);
		}
		System.out.println(list);
		
		Collections.shuffle(list);	//随机排列list中的元素
		System.out.println(list);
		
		Collections.reverse(list); //逆序排列
		System.out.println(list);
		
		Collections.sort(list);		//按照递增的方式排序。自定义的类使用：Comparable接口。
		System.out.println(list);
		
		System.out.println(Collections.binarySearch(list, "gao:1")); 	//二分法查找，或者：折半查找
		
		
	}
}
           

七.集合总结