特点： 在内存中分配连续的空间，只存储数据，不需要存储地址信息，位置就隐含着地址。 优点： 1.节省存储空间，因为分配给数据的存储单元全用于存放节点的数据（不考虑C/C++语言中数组需指定大小的情况）,节点之间的逻辑关系没有占用额外的存储空间。 素。 2.索引查找效率高，即每一个节点对应一个序号，由该序号可以直接计算出来节点的存储地址。 缺点： 1.增加和删除元素需要移动元素，效率较低。 2.必须提前分配固定数量的空间，如果存储元素少，可能导致空间浪费。 3.按照内容查询效率低，以为需要逐个比较判断。
1.底层使用动态增长的数组实现。 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
2.通过无参数构造方法创造对象时，JDK1.7初始长度是10。JDK1.8初始长度是0，在第一次添加元素时在给定长度10。
3.当容量不足时，扩容增加50%。 int newCapacity = oldCapacity + (oldCapacity >> 1);
4.提供了一个内部类Itr，实现了Iterator接口，用来对ArrayList进行遍历 public Iterator iterator() { return new Itr(); }
private class Itr implements Iterator {
}
手写List接口
/** * 手写List接口 */ public interface List { //返回线性表的大小，即数据元素的个数 public int size(); //返回现象表中序号为i的数据元素 public Object get(int i); //如果线性表为空返回true,否则返回false public boolean isEmpty(); //判断线性表是否包含数据元素e public boolean contain(Object e); //返回数据元素e在线性表中的序号 public int indexOf(Object e); //将线性元素e插入到线性表中序号i的位置 public void add(int i,Object e); //将数据元素e插入到线性表的末尾 public void add(Object e); //将数据元素e插入到元素obj之前 public boolean addBefore(Object obj,Object e); //删除线性表中序号为i的元素，并返回 public Object remove(int i); //删除线性表中第一个与e相同的元素 public boolean remove(Object e); //替换线性表中序号为i的数据元素为e，返回原数据元素 public Object replace(Object e); public Iterator iterator(); }手写Iterator接口
/** *手写Iterator接口 */ public interface Iterator<T> { boolean hasNext(); T next(); }自定义指针越界异常
/** *自定义指针越界异常 */ public class IndexOutOfBoundsException extends RuntimeException { public IndexOutOfBoundsException() { } public IndexOutOfBoundsException(String message) { super(message); } }手写ArrayList
import java.util.Arrays; import java.util.NoSuchElementException; /** * 手写ArrayList */ public class ArrayList implements List { private transient Object[] elementData;//ArrayList底层是一个长度可以动态增长的数组 private int size;//集合中元素的个数，不是数组分配了多少个空间 public ArrayList(){ this(10); } public ArrayList(int initialCapacity){ if(initialCapacity<0){ throw new IllegalArgumentException("初始化长度必须大于等于零"+initialCapacity); } elementData=new Object[initialCapacity]; } @Override public int size() { return size; } @Override public Object get(int i) { if (i>=size || i<0) { throw new IndexOutOfBoundsException("数组索引越界异常"+i); } return elementData[i]; } @Override public boolean isEmpty() { return size==0; } @Override public boolean contain(Object e) { return indexOf(e)!=-1; } @Override public int indexOf(Object e) { int index=-1; //表示不存在 for (int i = 0; i <size ; i++) { if(elementData[i].equals(e)){ index=i; break; } } return index; } @Override public void add(int i, Object e) { if(size==elementData.length){ //数组的扩容 elementData= Arrays.copyOf(elementData,size<<1);//一句话解决 } //后移后面的元素 for(int index=size-1;index>=i;index--){ elementData[index+1]=elementData[index]; } //添加元素 elementData[i]=e; //数量加1 size++; } @Override public void add(Object e) { if(size==elementData.length){ // System.out.println("扩容了"); // //创建一个新数组，长度是原来的2倍 // Object[] newArray=new Object[size<<1]; // //将就数组的内容都写入到新数组中 // for (int i = 0; i <size ; i++) { // newArray[i]=elementData[i]; // } // //数组引用指向新数组 // elementData=newArray; elementData=Arrays.copyOf(elementData,size<<1);//一句话解决 } //添加元素 elementData[size]=e; //数量加1 size++; } @Override public boolean addBefore(Object obj, Object e) { return false; } @Override public Object remove(int index) { Object oldValue = elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; } @Override public boolean remove(Object e) { return false; } @Override public Object replace(Object e) { return null; } @Override public Iterator iterator() { return new Itr(); } private class Itr<T> implements Iterator<T>{ int cursor=0; @Override public boolean hasNext() { return cursor<size; } @Override public T next() { int i=cursor; if(cursor>=size){ throw new NoSuchElementException("没有这个元素了，cusor:"+i); } cursor++; return (T)elementData[i]; //取出光标指向的元素 //return (T)elementData[cursor++];//注意两点：1.取完元素光标后移一位；2.类型的强制转换，因为elementData里面的元素是Object类型的 } } @Override public String toString() { StringBuilder builder=new StringBuilder("["); for (int i = 0; i < size; i++) { builder.append(elementData[i]+","); } if(size>0){ //为什么size>0呢？避免在没有元素的时候，把左侧的大括号砍掉 builder.deleteCharAt(builder.length()-1); } builder.append("]"); return builder.toString(); } }ArrayList测试
/** *ArrayList测试 */ public class TestArrayList { public static void main(String[] args) { java.util.ArrayList list2; //list2.toString(); //list2.iterator(); //创建线性顺序表 List list = new ArrayList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); //进行各种操作验证添加 System.out.println(list.get(30)); System.out.println(list.size()); System.out.println(list.isEmpty()); System.out.println(list.contains("11111")); System.out.println(list.indexOf("22222")); System.out.println(list.toString()); Iterator<String> it = list.iterator(); while(it.hasNext()){ String elem = it.next(); System.out.println(elem); } // it.next(); } }单链表特点: 1.数据元素的存储是不连续的存储空间，每个存储节点对应一个需要存储的数据元素 2.每个节点是由数据域和指针域组成。元素之间的逻辑关系通过存储节点之间的链接关系反应出来。逻辑上相邻的节点物理上不一定相邻。 3.数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。 4.每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻。 5.添加节点 6.删除节点
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。 一个带头结点的单链表实现线性表的结构图如图 所示: SingleLinkedList（带头节点实现的单链表）的优缺点： 缺点： 1.比顺序存储结构的存储密度小，（每个节点都有数据域和指针域组成，所以相同空间内假设全存满的话，顺序比链式存储的更多）。 2.查找节点时链式存储要比顺序存储慢（每个节点地址不连续、无规律、导致按照索引查询效率低下） 优点： 1.插入、删除灵活（不必移动节点，只要改变节点中的指针，但是需要先定位到元素上） 2.有元素才会分配节点空间，不会有闲置的节点。
List的接口（见上面这里省略） 定义单链表节点
/** * 单链表的一个节点 */ public class Node { Object data;//存储数据 Node next;//指向下一个节点的引用变量 public Node(){ //super(); //这里不写也相当于有了，调用父类无参构造方法 } public Node(Object data) { this.data = data; } public Node(Object data, Node next) { this.data = data; this.next = next; } @Override public String toString() { return "Node{" + "data=" + data + ", next=" + next + '}'; } }实现单链表
/** *手写单向链表 */ public class SingleLinkedList implements List { private Node head=new Node();//头节点，不存储数据 初始创建 用来指向第一个初始节点 private int size;//节点的数量，元素的个数 @Override public int size() { return size; } @Override public Object get(int i) { //根据索引查找第i个元素 //按照索引添加元素，只能从头开始，顺藤摸瓜 Node p=head; //从头开始，以此指向下一个节点,最终定位在第i个节点 for (int index = 0; index <= i; index++) { //指向下一个节点 p=p.next; } return p; //return p.data; 这个是得到p节点上的数据 } @Override public boolean isEmpty() { return size==0; } @Override public boolean contain(Object e) { return false; } @Override public int indexOf(Object e) { return 0; } @Override public void add(int i, Object e) { //1.请先找到第i-1个节点 Node previousNode=head; if(i>0){ previousNode=(Node)get(i-1); } //2.添加节点 //新建一个节点 并指向下一个节点 Node newNode=new Node(e,previousNode.next); //前一个节点指向新的节点 previousNode.next=newNode; //3.数量加1 size++; } //添加链表最后一个元素，就是想索引为size的地方添加元素 @Override public void add(Object e) { this.add(size,e); } @Override public String toString() { StringBuilder builder=new StringBuilder("["); //指向索引是0的节点，第一个节点 Node p=head.next; //从第0个节点开始，以此指向下一个节点，最终定位在第i个节点 for (int index = 0; index < size ; index++) { if(index==size-1){ builder.append(p.data); }else{ //取出其值 builder.append(p.data+","); } //指向下一个节点 p=p.next; } builder.append("]"); return builder.toString(); } @Override public boolean addBefore(Object obj, Object e) { return false; } @Override public Object remove(int i) { Node previousNode=head; //1.先找到i-1个 if(i>0){ previousNode=(Node)get(i-1); } //2.删除第i个元素 //2.1指针指向第i个节点 //Node currentNode=previousNode.next; //2.2前一个节点指向后一个节点 previousNode.next=previousNode.next.next; //2.3当前节点不再指向后一个节点 previousNode.next.next.next=null; //数量减1 size--; return null; } @Override public boolean remove(Object e) { return false; } @Override public Object replace(Object e) { return null; } @Override public Iterator iterator() { return null; } }测试单链表
public class TestSingleLinkedList { public static void main(String[] args) { //创建线性顺序表 List list = new SingleLinkedList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); list.remove(4); //进行各种操作验证添加 //System.out.println(list.get(3)); //System.out.println(list.get(0)); System.out.println(list.size()); System.out.println(list.isEmpty()); // System.out.println(list.contains("11111")); // System.out.println(list.indexOf("22222")); System.out.println(list.toString()); //[11111,aaaaa,bbbbb,... 22222] } }1.LinkedList底层是一个双向链表；添加、删除元素效率高；按照索引查询效率低。可以两个方向查询。
2.每一个节点都包含一个对前一个和后一个元素的引用 3.LinkedList同时实现了List、Deque、Queue接口，所以可以当做线性表、队列，双端队列，栈使用。 4.LinkedList是非同步的（线程不安全的） 5.不存在LinedkList容量不足的问题 定义List接口（略） 定义LinkedList
/** *双向链表源代码阅读 */ public class LinkedList implements List{ transient int size=0; //一共有几个元素 transient Node first; //指向双向链表的第一个元素 transient Node last;//指向双向链表的最后一个元素 //双向链表的一个节点 private static class Node<E> { E item; //该节点存储的数据 Node<E> next; //指向下一个节点 Node<E> prev; //指向前一个节点 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } @Override public int size() { return size; } @Override public Object get(int i) { return node(i).item; } @Override public boolean isEmpty() { return size == 0; } @Override public void add(int index, Object element) { if (index == size) linkLast(element); else linkBefore(element, node(index)); } void linkBefore(Object e, Node succ) { // assert succ != null; final Node pred = succ.prev; final Node newNode = new Node(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; } @Override public void add(Object e) { linkLast(e);//添加到最后 } void linkLast(Object e) { final Node l = last; final Node newNode = new Node(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; } /** * 查询指定索引的节点 * @param index * @return 返回的是一个Node */ Node node(int index) { //20个元素 找第3个 和第16个 很大的区别 // assert isElementIndex(index); if (index < (size >> 1)) { //前一半从0开始向后找 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //后一半，从后向前找 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } }测试LinkedList
public class TestList { public static void main(String[] args) { //创建线性顺序表 LinkedList list = new LinkedList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); //进行各种操作验证添加 System.out.println(list.size()); System.out.println(list.isEmpty()); //System.out.println(list.toString()); System.out.println(list.get(0)); } }底层内存分析图：
1.底层结构是哈希表，采用了顺序表+链表结合结构；同一个链表的上所有元素的存储地址都是相同的，是发生冲突的元素。 2.链表上每个节点的就是一个Entry，字段包括四部分。 hash（哈希码） key（键） value（值） next（指向下一个Entry节点） 3.哈希表的优点：添加快、查询快（通过计算得到存储位置，不是通过比较）。无序、（key）唯一。 4.关键参数： 默认主数组长度16；默认装填因子0.75。每次主数组扩容为原来的2倍。JDK8，当链表长度大于8，链表变成红黑树。 5.第一步计算哈希码，不仅调用了hashCode()，有进行了多次散列。目的在于key不同，哈希码尽量不同，减少冲突。 6.细节：发生冲突，经过比较不存在相同key的元素，要添加一个新的节点。不是加到链表最后，而是添加到链表最前。 **说明：**第一步计算哈希码，不仅调用了HashCode(),又进行了多次散列，目的在于key不同，哈希码尽量不同，减少冲突。 定义HashMap接口
/** * 定义一个Map接口 */ public interface Map { //定义方法 public void put(Object key, Object value); public Object get(Object key); public int size(); public boolean isEmpty(); //定义内部接口 interface Entry { public Object getKey(); public Object getValue(); } }手写HashMap
/** *手写HashMap */ public class HashMap implements Map{ static final int DEFAULT_INITIAL_CAPACITY = 16; //默认的主数组的长度 transient Entry[] table; //这是一个数组的引用 用来指向一个数组 （即指向哈希表的主数组的） 数组的元素都是Entry transient int size;//键值对的数量 Entry的数量 /** * int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; 如果指定的初始长度不是2的幂，会转化成2的幂 */ public HashMap(){ table=new Entry[DEFAULT_INITIAL_CAPACITY]; //创建了一个长度为16的数组 } @Override public void put(Object key, Object value) { //1.计算哈希码 int hash=key.hashCode(); //计算存储位置 int index=hash%table.length; //源码里面用的位运算，位运算效率更高 //存储到指定的位置 if(table[index]==null){ table[index]=new Entry(key,value,null,hash); size++; }else{ //该位置已经存放了元素，要首先查询是否存在相同key的Entry Entry entry=table[index]; //指向链表的第一个元素 while(entry!=null){ if(entry.getKey().equals(key) && entry.hash==hash){ //找到了 //使用新的value覆盖就得value entry.value=value; //退出方法 return; } //指向下一个节点 entry=entry.next; } //如果没有相同的key,添加一个新的节点，到链表的第一个位置 Entry firstEntry=table[index]; table[index] = new Entry(key,value,firstEntry,hash); size++; } } @Override public Object get(Object key) { //1.计算哈希值 int hash=key.hashCode(); //2.计算存储位置 int index=hash%table.length; //3.去指定的位置查找 Entry e=null; //默认不存在 if(e!=null){ //该位置有元素 Entry entry=table[index]; //链表指向第一个元素 while(entry!=null){ //比较 if(entry.hash==hash && entry.getKey().equals(key)){ e=entry; break; } //指向下一个节点 entry=entry.next; } } return e==null?null:e.getValue(); } @Override public String toString() { StringBuilder builder=new StringBuilder("{"); for (int i = 0; i < table.length ; i++) { if(table[i]!=null){ Entry entry=table[i]; while(entry!=null){ builder.append(entry.key+"="+entry.value+","); //指向下一个节点 entry=entry.next; } } } if(size!=0){ builder.deleteCharAt(builder.length()-1); } builder.append("}"); return builder.toString(); } @Override public int size() { return size; } @Override public boolean isEmpty() { return size==0; } class Entry implements Map.Entry{ final Object key; //key 这个用final修饰，必须得给赋一次值，我们这里在构造方法里面给它赋值 Object value; Entry next; int hash; public Entry(Object key, Object value, Entry next, int hash) { this.key = key; this.value = value; this.next = next; this.hash = hash; } @Override public Object getKey() { return key; } @Override public Object getValue() { return value; } @Override public String toString() { return "Entry{" + "key=" + key + ", value=" + value + ", next=" + next + ", hash=" + hash + '}'; } } }测试HashMap
public class TestHashMap { public static void main(String[] args) { HashMap map = new HashMap(); map.put(23,"Italian"); map.put(47,"England"); map.put(23,"China"); map.put(36,"Japan"); map.put(48,"America"); map.put(86,"the United States"); map.put(67,"France"); System.out.println(map.size()); System.out.println(map.get(23));//Entry ---China System.out.println(Arrays.toString(map.table)); System.out.println(map.toString()); } }1.底层就是HashMap，哈希表的每个Entry的key是每个元素，value统一都是new Object()。
定义Set接口
public interface Set { public int size(); public void add(Object obj); public boolean isEmpty(); public boolean contains(Object obj); }手写HashSet
public class HashSet implements Set { private transient HashMap map;//底层有一个HashMap的引用，指向一个哈希表 private static final Object PRESENT = new Object();//Set中向map中存放键值对，value统一的是PRESENT public HashSet() { map = new HashMap(); } public void add(Object obj){ // map.put(obj,new Object());//每次创建一个新的Object对象 map.put(obj,PRESENT);//每次指向同一个Object对象 } @Override public int size() { return map.size(); } @Override public boolean isEmpty() { return map.size()==0; } @Override public boolean contains(Object obj) { return map.get(obj) != null; } }第一代 线程安全集合类 Vector、Hashtable 是怎么保证线程安排的： 使用synchronized修饰方法 缺点：效率低下 第二代 线程非安全集合类（主流） ArrayList、HashMap 线程不安全，但是性能好，用来替代Vector、Hashtable 使用ArrayList、HashMap，需要线程安全怎么办呢？ 使用 Collections.synchronizedList(list); Collections.synchronizedMap(m); 底层使用synchronized代码块锁 虽然也是锁住了所有的代码，但是锁在方法里边，并所在方法外边性能可以理解为稍有提高吧。毕竟进方法本身就要分配资源的 。 第三代 线程安全集合类（波浪式前进，螺旋式上升） 在大量并发情况下如何提高集合的效率和安全呢？ java.util.concurrent.* ConcurrentHashMap： CopyOnWriteArrayList ： CopyOnWriteArraySet：注意 不是CopyOnWriteHashSet 底层均采用Lock锁，保证安全的同时，性能也很高。 1.ConcurrentHashMap: 分段（segment）锁定+Lock锁 HashMap的线程安全班，并且性能比Hashtable、Collections.synchronizedMap(m);都有提高。使用的不是synchronized代码块锁，也不是synchronzied方法锁。并且使用了锁分离技术，使用多个锁来控制对hash表的不同部分（段segment）进行的修改，采用ReentrantLock锁来实现。如果多个修改操作发生在不同的段上，他们就可以并发进行，从而提高了效率。JDK1.7和JDK1.8的关于ConcurrentHashMap的实现差异较大，以上理论属于JDK1.7; ConcurrentHashMap在JDK8中进行了巨大改动。它摒弃了Segment（锁段）的概念，而是启用了一种全新的方式实现,利用CAS算法。 它底层由"数组"+链表+红黑树的方式思想(JDK8中HashMap的实现)， 为了做到并发，又增加了很多辅助的类，例如TreeBin，Traverser等对象内部类。 2.CopyOnWriteArrayList ：CopyOnWrite+Lock锁 。 对于set()、add()、remove()等方法使用ReentrantLock的lock和unlock来加锁和解锁 ，读操作不需要加锁（之前集合安全类，即使读操作也要加锁，保证数据的实时一致） CopyOnWrite原理：写时复制。 通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。对于读操作远远多于写操作的应用非常适合，特别在并发情况下，可以提供高性能的并发读取。 CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。 注意：读的时候不需要加锁，如果读的时候有多个线程正在向ArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的ArrayList。 3.CopyOnWriteArraySet：CopyOnWrite+Lock锁 它是线程安全的无序的集合，可以将它理解成线程安全的HashSet。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet；但是，HashSet是通过"散列表(HashMap)"实现的，而CopyOnWriteArraySet则是通过"动态数组(CopyOnWriteArrayList)“实现的，并不是散列表。 CopyOnWriteArraySet在CopyOnWriteArrayList 的基础上使用了Java的装饰模式，所以底层是相同的。 而CopyOnWriteArrayList本质是个动态数组队列，所以CopyOnWriteArraySet相当于通过通过动态数组实现的"集合”！ CopyOnWriteArrayList中允许有重复的元素；但是，CopyOnWriteArraySet是一个集合，所以它不能有重复集合。 因此，CopyOnWriteArrayList额外提供了addIfAbsent()和addAllAbsent()这两个添加元素的API， 通过这些API来添加元素时，只有当元素不存在时才执行添加操作！
