博客

Java中的容器有三大类：Set，List，Map；它们之间的关系如下图：

LIst：

继承于Collection，是抽象类，主要有两个子类ArraList和LinkList。特点：元素有序，可重复。

ArrayList：

• 底层是采用数组实现。
• 查找快，增删慢。
• 线程不安全

LinkedList：

• 底层采用链表实现。
• 查找慢，增删快。
• 线程不安全

Vector：

• 也是采用数组实现。
• 效率慢
• 线程安全

Map：

以键值对为一个元素进行储存。主要子类为HashMap和TreeMap。

HashMap：

• 采用哈希表进行实现。
• 哈希表是链表和数组的实现；综合了数组和链表的优点。
• 元素无序。
• 存储过程：
  
  
  
  
  TreeMap：
  
• 底层采用红黑二叉树实现。
• 元素按照key进行排序。
• 线程不安全。

HashTable：

• 效率慢。
• 线程安全。
• 不允许Key或者Value为null

Set：

继承于Collection，是抽象类，主要有两个子类HashSet和TreeSet。相比于List，特点：

不可重复

。

HashSet：

• 底层依据HashMap实现，将HashMap中的键值对的值设置成常量，只使用Key。
• 无序。
• 线程不安全。

TreeSet：

• 依据TreeMap实现；将TreeMap中的键值对的值设置成常量，只使用Key。
• 有序。
• 线程不安全。

手写ArrayList实现原理的代码：

import java.util.Arrays;

public class MyArrayList<E> {
    private Object[] elementData = null;
    private int  size = 0;  
    private  int capacity = 10; //容量

    public MyArrayList(){
        elementData = new Object[capacity];
    }
    /*
     * 带参数的构造函数，初始化数组容量
     */
    public MyArrayList(int n){
        elementData = new Object[n];
        capacity = n;
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i=0; i<size; i++){
            sb.append(elementData[i]+",");
        }
        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }

    /*
     * 在指定位置插入元素
     */
    public void add(int index, E e){
    	if(index<0||index>size){
    		throw new RuntimeException("插入非法位置");
    	}
    	if(size>=capacity){//进行扩容
    		Object[] temp = new Object[capacity+(capacity>>1)];
    		System.arraycopy(elementData, 0, temp, 0, size);
    		elementData = temp;
    	}
    	System.arraycopy(elementData, index, elementData, index+1, size-index);
    	elementData[index] = e;
    }
    
    /*
     * 在末尾添加元素
     */
    public  void add(E e){
    	if(size>=capacity){//进行扩容
    		Object[] temp = new Object[capacity+(capacity>>1)];
    		System.arraycopy(elementData, 0, temp, 0, size);
    		elementData = temp;
    	}
    	elementData[size++] = e;
    }
    
    public int size(){
    	return size;
    }
    
    public Object get(int index){
    	if(index<0||index>size){
    		throw new RuntimeException("下标不合法");
    	}
    	return elementData[index];
    }
    
    public void set (int index, E e){
    	if(index<0||index>size){
    		throw new RuntimeException("下标不合法");
    	}
    	elementData[index] = e;
    }
    
    public void remove(int index){
    	System.arraycopy(elementData, index+1, elementData, index, size-index);
    }
    
    public void remove(E e){
    	int index=0;
    	while(index<size){
    		if(elementData[index++].equals(e)){
    			remove(index-1);
    			break;
    		}
    	}
    }
    
    public static void main(String[] args) {
        MyArrayList<String> arr = new MyArrayList<String>(15);
        for(int i=0; i<10; i++){
        	arr.add("huicheng" + i);
        }
        //arr.add(3, "asd");
        arr.remove("huicheng1");
        System.out.println(arr);
    }
}

手写LinkedList实现原理的代码：

import java.util.*;

class Node{
	Node previous;	//上一个节点
	Node next;		//下一个节点
	Object element;
}


public class MyLinkedList<E> {
	private Node first;  //头指针
	private Node last;	 //尾指针
	private int size;
	
	public MyLinkedList(){
		first = null;
		last = null;
		size = 0;
	}
	
	public int size(){
		return size;
	}
	
	public E get(int index){
		if(index<0||index>=size){
			throw new RuntimeException("下标越界");
		}
		Node temp = new Node();
		temp = first;
		for(int i=0; i<index; i++){
			temp = temp.next;
		}
		return (E)temp.element;
	}
	
	
	/*
	 * 删除指定下标元素
	 */
	public void remove(int index){
		if(index<0||index>=size){
			throw new RuntimeException("下标越界");
		}
		Object t= get(index);
		Node temp = first;
		for(int i=0; i<index; i++){
			temp = temp.next;
		}
		Node pre = temp.previous;
		Node hou = temp.next;
		pre.next = hou;
		hou.previous = pre;
		size--;
	}
	/*
	 * 在末尾添加元素
	 */
	public void add(E e){
		Node temp = new Node();
		temp.element = e;
		if(first==null){
			first = temp;
			last = temp;
			temp.next = null;
			temp.previous = null;
		}else{
			last.next = temp;
			temp.previous = last;
			last = temp;
		}
		size++;
	}
	
	/*
	 *在指定位置插入元素
	 */
	public void add(int index, E e){
		if(index<0||index>=size){
			throw new RuntimeException("下标越界");
		}
		
		Node newNode = new Node();
		newNode.element = e;
		Node temp = first;
		for(int i=0; i<index; i++){
			temp = temp.next;
		}
		Node pre = temp.previous;
		pre.next = newNode;
		newNode.previous = pre;
		newNode.next = temp;
		temp.previous = newNode;
		size++;
	}
	public String toString(){
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		Node temp = first;
		for(int i=0; i<size; i++){
			sb.append(temp.element+",");
			temp = temp.next;
		}
		sb.deleteCharAt(sb.length()-1);
		sb.append("]");
		return sb.toString();
	}
	public static void main(String[] args){
		MyLinkedList<String> link = new MyLinkedList<String>();
		for(int i=0; i<10; i++){
			link.add("huicheng" + i);
		}
		link.add(3, "asdf");
		System.out.println(link);
	}
}

手写HashMap实现原理的代码：

class Node1<K, V>{
	int hash;  		//哈希值
	Node1 next;		//下一个节点
	K key;
	V value;
}

public class MyHashMap<K, V> {
	
	Node1[] table; //位桶数组
	int size;  //键值对的个数
	
	public MyHashMap(){
		table = new Node1[16];
	}
	
	public V get(Object k){
		V value = null;
		int key = MyHash(k.hashCode(), table.length); 
		if(table[key]!=null){
			Node1<K,V> temp = table[key];
			while(temp!=null){
				if(temp.key==k){
					return temp.value;
				}else{
					temp = temp.next;
				}
			}
		}
		return value;
	}
	/*
	 * 重写toString()
	 */
	public String toString(){
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		Node1<K,V> temp = new Node1<K,V>();
		for(int i=0; i<table.length; i++){//遍历数组
			temp = table[i];
			
			while(temp!=null){//遍历链表
				String str = "["+temp.key.toString()
							+":"
							+temp.value.toString()+"]";
				
				sb.append(str+",");
				temp = temp.next;
			}
			
		}
		sb.deleteCharAt(sb.length()-1);
		sb.append("]");
		return sb.toString();
	}
	
	public void put(K k, V v){
		Node1<K,V> newnode = new Node1<K,V>();
		newnode.key = k;
		newnode.hash = MyHash(k.hashCode(), table.length);
		newnode.value = v;
		Node1 temp = table[newnode.hash];
		
		if(temp==null){
			table[newnode.hash] = newnode;
		}else{
			Node1<K,V> inlast = new Node1<K,V>(); //指向最后一个元素
			while(temp!=null){
				if(temp.key.equals(newnode.key)){
					System.out.println("重复了");
					temp.value = newnode.value;
					return;
				}else{
					inlast = temp;
					temp = temp.next;
				}
			}
			inlast.next = newnode;//链接添加的元素
		}
		size++;
	}
	/*
	 * 计算哈希值
	 */
	private int  MyHash(int key, int length){
		return key%length;
	}
	public static void main(String[] args){
		MyHashMap<Integer, String> map = new MyHashMap<Integer,String>();
		for(int i=0; i<9; i++){
			map.put(i, "hc"+i);
		}
		map.put(19, "text");
		System.out.println(map.get(19));
		System.out.println(map.toString());	
	}
}