Java常见数据结构

List

List是一个接口，它继承了Collection接口，可以说是有序的Collection，可以根据索引（下标）随机取出对应位置的元素。

常用的方法（有的方法描述跟官方可能不太一致，使用的时候参考文档）

void add(T item)  //添加元素
void add(T item, int index) //在指定位置处添加元素
void remove(int position) //删除第几个元素
void removeAll() //删除所有元素
int size();//List的元素个数
boolean isEmpty();//判断List是否为空

List和Set都继承了Collection接口，但它们各有不同：

List中的元素可重复，有序
Set中的元素不可重复，无序

List有三种实现的数据结构：ArrayList、 LinkedList 和 Vector，后面介绍。

Vector

Vector 类实现了一个动态数组，和ArrayList不同，Vector中的操作是线程安全即同步的。
Vector实际上是通过一个数组去保存数据的。当我们构造Vecotr时；若使用默认构造函数，则Vector的默认容量大小是10
当Vector容量不足以容纳全部元素时，Vector的容量会增加。若容量增加系数 >0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。
Vector的克隆函数，即是将全部元素克隆到一个数组中。

ArrayList

ArrayList底层使用数组实现，可以说ArrayList是一个可以动态增长的数组，毫无疑问ArrayList访问数据的效率高，插入删除数据的效率较低，这都跟数组的自身特性相关联。

简单实现：

List接口自定义
package edu.nwpu.structure;

import java.util.Iterator;

public interface List <T>{
    void add(T element);

    void remove(int index);

    void set(int index,T element);

    T get(int index);

    void print();

    int size();

    Iterator<T> iterator();
}

package edu.nwpu.structure;

import java.util.Arrays;
import java.util.Iterator;

/**
 * @author June
 * @param <T>
 *
 */
public class MyList<T> implements List<T> {
    final int DEFAULT_SIZE = 10;
    final int MAX_SIZE=Integer.MAX_VALUE-8;
    Object[] elements = {};
    int size = 0;

    @Override
    public void add(T element) {
        if(size>=MAX_SIZE) {
            throw new RuntimeException("数组无法扩容");
        }
        if (elements.length == 0) {
            elements = Arrays.copyOf(elements, DEFAULT_SIZE);
        }
        if (size >= elements.length) {
            int oldSize = elements.length;
            int newSize = oldSize + (oldSize >> 1);
            elements = Arrays.copyOf(elements, newSize);
        }
        elements[size++] = element;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("下标错误");
        }
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        elements[--size] = null;
    }

    @Override
    public void set(int index, T element) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("下标错误");
        }
        elements[index] = element;
    }

    @SuppressWarnings("unchecked")
    @Override
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("下标错误");
        }
        return (T) elements[index];
    }

    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    class Itr implements Iterator<T> {
        int cursor = 0;
        int lastRet = -1;

        @Override
        public boolean hasNext() {
            if (cursor >= size) {
                return false;
            }
            return true;
        }

        @SuppressWarnings("unchecked")
        @Override
        public T next() {
            return (T) elements[cursor++];
        }

    }

    @Override
    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.println(elements[i]);
        }

    }

    @Override
    public int size() {

        return size;
    }

    public static void main(String[] args) {
        MyList<String> list = new MyList<>();
        list.add("hello");
        list.add("world");
        list.add("加油啊");
        System.out.println(list.get(1));
        list.remove(0);
        list.print();
        System.out.println(list.size);
    }

}

注意点：

ArrayList依赖于数组实现的,初始长度为10的Object[],并且可随需要而增加的动态数组当元素超过10,那么ArrayList底层会新生成一个数组,长度为原来的1.5倍,然后将原数组内容复制到新数组中,并且后续增加的内容会放到新数组中,当新数组无法容纳增加的元素,重复该过程。

ArrayList对随机访问性能很好,但进行大量插入,删除操作,性能很差,因为操作之后后续元素需要移动。

LinkedList

LinkedList底层使用双向循环链表，其容量也是可以动态伸缩，因为采用链表实现，具有插入删除高效，随机访问困难的特点。
在这里插入图片描述

为了实现的方便，暂时使用单向链表，看个大概思路即可

List接口自定义
package edu.nwpu.structure_LinkedList;

public interface List<T> {
    void add(T data);
    void delete(T data);
    void delete(int index);
    void set(int index,T data);
    void print();
    int size();
    boolean isEmpty();
}

package edu.nwpu.structure_LinkedList;

public class LinkList<T> implements List<T> {

    Node head;
    int size = 0;

    @Override
    public void add(T data) {
        if (head == null) {
            head = new Node(data, null);
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new Node(data, null);
        }
        size++;
    }

    @Override
    public void delete(T data) {
        Node temp = head;
        boolean flag = true;//判断标志位，用来表明是否存在数据data，默认为true
        //因为这里使用的单向链表并且首节点存放数据，所以先从链表首节点开始找到第一个不同于data的链表节点作为新的head
        //这样做是因为下面使用的方法存在无法检验头节点数据的问题
        while(temp!=null) {
            if(temp.data.equals(data)) {
                temp=temp.next;
                flag=false;
                size--;
            }else {
                head=temp;//找到了第一个不同于data的链表节点作为新的head
                break;
            }
        }
        if(temp==null) {
            head=null;//这种是整个链表都是存放的数据data的极端情况
        }else {
            while(temp.next!=null) {
                Node wantNode=temp.next;
                if(wantNode.data.equals(data)) {
                    temp.next=wantNode.next;
                    wantNode=null;
                    flag=false;
                    size--;
                }else {
                    temp=wantNode;
                }
            }
        }
        if(flag) {
            throw new RuntimeException("没有该元素");
        }


    }

    @Override
    public void delete(int index) {
        if(size==0) {
            throw new RuntimeException("空list");
        }else {
            if(index>=size||index<0) {
                throw new RuntimeException("越界");
            }else {
                if(index ==0) {
                    head =head.next;
                    size--;
                }else {
                    Node temp =head;
                    while(index>1) {
                        temp=temp.next;
                        index--;
                    }
                    Node wantNode=temp.next;
                    temp.next=wantNode.next;
                    wantNode=null;
                    size--;
                }
            }
        }

    }

    @Override
    public void set(int index, T data) {
        if(index>=size||index<0) {
            throw new RuntimeException("越界");
        }else {
            Node temp =head;
            while(index!=0) {
                temp=temp.next;
                index--;
            }
            temp.data=data;
        }

    }

    @Override
    public void print() {
        Node temp=head;
        while(temp!=null) {
            System.out.println(temp.data);
            temp=temp.next;
        }

    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    class Node {
        Object data;
        Node next;

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    public static void main(String[]args) {
        LinkList<Integer> linkList=new LinkList<Integer>();
        linkList.add(11);
        linkList.add(12);
        linkList.add(13);
        linkList.add(14);
        linkList.add(15);
        linkList.add(16);
        linkList.add(17);
        linkList.delete(Integer.valueOf(11));
        linkList.delete(Integer.valueOf(12));
        linkList.delete(Integer.valueOf(15));
        linkList.delete(Integer.valueOf(17));
        linkList.delete(0);
        linkList.delete(0);
//        linkList.delete(0);
        System.out.println(linkList.size);
        System.out.println(linkList.isEmpty());
        linkList.print();
    }

}

LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.，它和ArrayList一样实现了List接口，但是她执行插入和删除操作时比ArrayList更加高效，因为她是基于链表的，但同时也决定了她在随机访问方面要比ArrayList弱一点。

HashSet

HashSet能够最快的获取集合中的元素，效率非常高（以空间换时间）。它会根据hashcode和equals来判断是否是同一个对象，如果hashcode一样，并且equals返回true，则是同一个对象，不能重复存放。

需要重写的方法：

equals()方法：用来实现Set中元素的不重复性，如果不覆盖（override）equals()方法，默认使用父类Object的equals方法，则只是比较对象的引用是否相同。
hashCode() 方法：有知道对象的hash值，才能根据这个hash值确定存放在散列表中的位置。同样，如果不覆盖（override）hashCode()方法，默认使用父类Object的hashCode()方法。
toString()方法：toString()方法在打印对象时会调用。如果不覆盖（override）toString()方法，默认使用父类Object的toString()方法。

注意:set的add方法会自动判断里面收的元素是否有相同，从而保证元素的唯一性。

boolean isExists = false;
Iterator iterator = set.iterator();
while (it.hasNext()) {
    String oldStr = it.next();
    if (newStr.equals(oldStr)) {
        isExists = true;
    }
}

HashMap

首先看看Map类是个什么鬼东西，简单地说，Map就是一个键值对集合，相比于List而言它的元素不再是单一的元素，而是一个二元组–>键值对，每一个键都对应一个特定的值，可以把List看作键省略的Map，其键即为数组索引下标。
在这里插入图片描述

Map接口自定义
public interface Map<K,V> {
	
	public void put(K key,V value);
	public V get(K key);
	int size();

}

Map 是一个键值对(key-value)映射接口。Map映射中不能包含重复的键；每个键最多只能映射到一个值.
AbstractMap 是继承于Map的抽象类，它实现了Map中的大部分API。其它Map的实现类可以通过继承AbstractMap来减少重复编码.
SortedMap 是继承于Map的接口。SortedMap中的内容是排序的键值对，排序的方法是通过比较器(Comparator).
TreeMap 继承于AbstractMap，且实现了NavigableMap接口；因此，TreeMap中的内容是“有序的键值对”.
HashMap 继承于AbstractMap，但没实现NavigableMap接口；因此，HashMap的内容是“键值对，但不保证次序”.
WeakHashMap 继承于AbstractMap。它和HashMap的键类型不同，WeakHashMap的键是“弱键”.
Hashtable 虽然不是继承于AbstractMap，但它继承于Dictionary(Dictionary也是键值对的接口)，而且也实现Map接口；因此，Hashtable的内容也是“键值对，也不保证次序”。但和HashMap相比，Hashtable是线程安全的，而且它支持通过Enumeration去遍历.

注意：

出于哈希冲突和数据分布的考虑，引入了负载因子：当容器中元素的数量达到了负载量（负载因子*容量），则Map将会进行扩容操作，调整大小需要将所有元素重新插入到新数组中，这是因为不同的数组大小意味着对象现在映射到不同的索引值。先前冲突的键可能不再冲突，而先前不冲突的其他键现在可能冲突。

哈希映射：简单地说，计算出存放数据的哈希值并结合数组长度决定把数据存放在数组哪个位置（int hashValue = Maths.abs(obj.hashCode()) % size），例如哈希值27，数组长度为10，则本次数据存放在第7个位置。如果数组第7个位置存在数据则发生哈希冲突，此时把本次数据放在数组对应位置链表的首部。

现在来看看HashMap是什么吧，HashMap实现提供所有可选的映射操作，并允许使用 null 值和 null 键，此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap不是同步的，不是线程安全的，但是可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap,其实ArrayList也是可以通过这种方法实现线程安全。

Map map = Collections.synchronizedMap(new HashMap());

两个重要参数：

initialCapacity：初始容量，也就是HashMap初始哈希表的容量。
loadFactor:负载因子，用来衡量散列表空间的使用程度，越大说明空间利用越好，但是冲突增大，查询效率降低；越小说明元素分布越稀疏，但是冲突减少，查找效率较高，默认的负载因子为0.75。

public class HashMap<K,V> implements Map<K, V> {

	private Object[] objects= new Object[11];
	private int size=0;
	@Override
	public void put(K key, V value) {
		Node newNode= new Node(new Entry(key, value), null);
		int index=key.hashCode()%objects.length;
		if(objects[index]==null) {
			objects[index]=newNode;
			size++;
		}else {
			@SuppressWarnings("unchecked")
			Node head =(HashMap<K, V>.Node) objects[index];
			boolean flag=true;//查看是否放入具有相同key的Node节点
			//这里把新的数据放在链表末尾了，其实应该放在链表开头.
			//我理解之所以放在链表开头可能是跟程序局部性原理有一定关系，放在链表首部等下次程序再次访问到改数据时不用再辛苦			地把链表再遍历一遍了，开头就拿到了。当然可能是我想多了或者想多了，欢迎指正。
			while(head.next!=null) {
				if(head.element.keyK.equals(key)) {
					flag=false;
				}
				head=head.next;
			}
			if(flag&&!(head.element.keyK.equals(key))) {
				head.next=newNode;
				size++;
			}else {
				throw new RuntimeException("重复的key");
			}
		}
		
	}

	@Override
	public V get(K key) {
		int index=key.hashCode()%objects.length;
		if(objects[index]==null) {
			throw new RuntimeException("没有该元素");
		}else {
			@SuppressWarnings("unchecked")
			Node head = (HashMap<K, V>.Node) objects[index];
			while(head!=null) {
				if(head.element.keyK.equals(key)) {
					return head.element.valueV;
				}
			}
			throw new RuntimeException("没有该元素");
		}
		
	}
	
	public int size() {
		return this.size;
	}
	
	class Node{
		Entry element;
		Node next;
		public Node(Entry element,Node next) {
			this.element=element;
			this.next=next;
		}
	}
	
	class Entry{
		K keyK;
		V valueV;
		public Entry(K keyK,V valueV) {
			this.keyK=keyK;
			this.valueV=valueV;
		}
	}
	
	public static void main(String[]args) {
		HashMap<Integer, Integer> hashMap=new HashMap<>();
		hashMap.put(0, 10);
		hashMap.put(1, 11);
		//hashMap.put(1, 12);
		hashMap.put(2, 12);
		hashMap.put(3, 13);
		hashMap.put(4, 14);
		hashMap.put(5, 15);
		hashMap.put(6, 16);
		hashMap.put(7, 17);
		System.out.println(hashMap.size);
		System.out.println(hashMap.get(0));
		System.out.println(hashMap.get(5));
		System.out.println(hashMap.get(7));
		//System.out.println(hashMap.get(Integer.valueOf(10)));
	}

}

注意：

HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。

Stack

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。

常见方法：

boolean empty() 测试堆栈是否为空
Object peek() 查看堆栈顶部的对象，但不从堆栈中移除它
Object pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象
Object push(Object element) 把项压入堆栈顶部
int search(Object element) 返回对象在堆栈中的位置，以 1 为基数

数组实现：

import java.util.Arrays;

public class MyStack<T> {
	Object [] elements;
	int size=0;
	public MyStack(){
	elements=new Object[10];
	}
	
	public T push(T data) {
		if(size>=elements.length) {
			int newLength=elements.length<<1;
			Object[] ne =Arrays.copyOf(elements, newLength);
			elements=null;
			elements=ne;
		}
		elements[size++]=data;
		return data;
	}
	
	@SuppressWarnings("unchecked")
	public T pop() {
		if(size<=elements.length>>1) {
			int newLength=elements.length>>1;
			Object[] ne =Arrays.copyOf(elements, newLength);
			elements=null;
			elements=ne;
		}
		return (T) elements[--size];
	}
	
	public int size() {
		return this.size;
	}
	
	public void print() {
		for(int i=0;i<size;i++) {
			System.out.println(elements[i]);
		}
	}
	
	public static void main(String[] args) {
		MyStack<Integer> myStack=new MyStack<>();
		myStack.push(1);
		myStack.push(2);
		myStack.push(3);
		myStack.push(4);
		myStack.push(5);
		myStack.push(6);
		myStack.push(7);
		myStack.push(8);
		myStack.push(9);
		myStack.push(10);
		myStack.push(11);
		myStack.push(12);
		myStack.push(13);
		myStack.pop();
		myStack.pop();
		myStack.pop();
		//myStack.pop();
		//myStack.pop();
		//myStack.pop();
		//myStack.pop();
		myStack.print();	
	}
}

链表实现：

package edu.nwpu.stack;

public class LinkStack<T> {
	Node head;
	Node tail;
	int size=0;
	
	public static void main(String[] args) {
		LinkStack<Integer> stack=new LinkStack<>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);
		stack.push(6);
		stack.push(7);
		stack.push(8);
		stack.push(9);
		stack.push(10);
		stack.pop();
		stack.pop();
		stack.print();
	}
	
	public T push(T data) {
		if(size==0) {
			head=new Node(data, null, null);
			tail=head;
		}else {
			Node newNode=new Node(data, null, tail);
			tail.next=newNode;
			tail=newNode;
		}
		size++;
		return data;
	}
	
	public T pop() {
		if(size==0) {
			throw new RuntimeException("空栈");
		}
		else if(size==1){
			Node oldtail=tail;
			head=tail=null;
			size--;
			return oldtail.data;
		}
		else {
			Node oldtail=tail;
			tail.pre.next=null;
			tail=tail.pre;
			size--;
			return oldtail.data;
		}
	}
	
	public int size() {
		return this.size;
	}
	
	public void print() {
		Node temp = head;
		while(temp!=null) {
			System.out.println(temp.data);
			temp=temp.next;
		}
	}
	class Node{
		T data;
		Node next;
		Node pre;
		public Node(T data,Node next,Node pre) {
			this.data=data;
			this.next=next;
			this.pre=pre;
		}
	}
}

参考文章：
javaschool