1. 手写ArrayList

1.1. ArrayList底层原理细节

• 底层结构是一个长度可以动态增长的数组（顺序表）transient Object[] elementData;
  
• 特点：在内存中分配连续的空间，只存储数据，不存储地址信息。位置就隐含着地址。
• 优点
  1. 节省存储空间，因为分配给数据的存储单元全用于存放节点的数据（不考虑c/c++中数组需指定大小的情况），节点之间的逻辑关系没有占有额外的存储空间
  2. 索引查找效率高，即每一个节点对应一个序号，由该序号可以直接计算出来节点的存储地址。
• 缺点
  1. 插入和删除操作需要移动元素，效率较低
  2. 必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费
  3. 按照内容查询效率低，因为需要逐个比较判断
• 通过无参构造方法创建对象时，JDK1.7初始长度时10；JDK1.8初始长度是0，在第一次添加元素时就进行扩容
• 容量不足时，每次扩容增加50%，int newCapacity = oldCapacity + (oldCapacity >> 1);
  
• 提供一个内部类ltr，实现了Iterator接口。用来对ArrayList进行遍历

java">public Iterator<E> iterator() {return new itr();
}
private class itr implements Iterator<E> {
}

1.2. 定义List接口和Iterator接口

java">public interface Iterator<T> {boolean hasNext();T next();
}
public interface List {// 返回线性表的大小，即数据元素的个数public int size();// 返回线性表中序号为i的数据元素public Object get(int i);// 如果线性表为空返回true，否则返回falsepublic boolean isEmpty();// 判断线性表是否包含数据元素epublic boolean contains(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);// 将数据元素e插入到元素obj之后public boolean addAfter(Object obj, Object e);// 删除线性表中序号为i的元素并返回public Object remove(int i);// 删除线性表中第一个与e相同的元素public boolean remove(Object e);// 替换线性表中序号为i的数据元素为e，返回原数据元素public Object replace(int i, Object e);// 迭代Listpublic Iterator iterator();
}

1.3. 手写ArrayList

java">/*
* 自定义数组越界异常
* */
public class IndexOutOfBoundsException extends RuntimeException {public IndexOutOfBoundsException() {}public IndexOutOfBoundsException(String message) {super(message);}
}
public class ArrayList implements List {// 底层数组来存储多个元素private Object[] elementData;// 存储元素的个数，线性表的长度，不是数组长度private int size;public ArrayList() {// 查看真实的ArrayList无参数构造方法是怎么实现的this(10);// this.elementData = new Object[]();// this.elementData = new Object[0];}public ArrayList(int initialCapacity) {// 如果initialCapacity<0，抛出异常if(initialCapacity < 0) {throw new IndexOutOfBoundsException("初始长度要大于0: " + initialCapacity);}// 按照初始长度给数组分配空间elementData = new Object[initialCapacity];// 指定线性表初始元素个数，可以省略，int成员变量默认值0// this.size = 0;}@Overridepublic int size() {return size;}@Overridepublic Object get(int i) {// 对i值进行判断if(i >= size) {throw new IndexOutOfBoundsException("数组指针越界异常：" + i);}return elementData[i];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean contains(Object e) {// 逐个判断各元素是否与要查询元素内容相同，效率低下// 注意不是elementData.length，而是size/*for (int i = 0; i < size; i++) {if(e.equals(elementData[i])) return true;}return false;*/return this.indexOf(e) >= 0;}@Overridepublic int indexOf(Object e) {// 逐个判断各个元素是否与要查询元素内容相同，效率低下// 有漏洞，如果e为null，使用if分别处理for (int i = 0; i < size; i++) {if(e.equals(elementData[i])) {return i;}}return -1;}@Overridepublic void add(int i, Object e) {// 如果i超过了size，抛出异常if(i > size || i < 0) {throw new IndexOutOfBoundsException("数组指针越界异常：" + i);}// 需要先判断length是否足够，如果已经满了，需要扩容if(size == this.elementData.length) {grow();}// 添加元素// 从后向前移后面元素一个位置for (int j = size; j > i; j--) {this.elementData[i] = this.elementData[j-1];}// 添加元素到指定位置this.elementData[i] = e;// 元素个数+1this.size++;}@Overridepublic void add(Object e) {// 需要先判断length是否足够，如果已经满了，需要扩容if(size == this.elementData.length) {grow();}// 增加元素this.elementData[size] = e;// 元素长度+1size++;// 可以合并成一条语句// this.elementData[size++] = e;}private void grow() {// 创建一个新的更长数组/*Object[] newArr = new Object[this.elementData.length * 2];// 将旧数组数据放入到新数组for (int i = 0; i < this.elementData.length; i++) {newArr[i] = this.elementData[i];}// 旧数组引用指向新数组this.elementData = newArr;*/elementData = Arrays.copyOf(elementData, this.elementData.length * 2);}@Overridepublic String toString() {if(this.size == 0) return "[]";StringBuilder builder = new StringBuilder();builder.append("[");for (int i = 0; i < size; i++) {if(i != size - 1) {builder.append(this.get(i) + ",");}else {builder.append(this.get(i));}}builder.append("]");return builder.toString();}public Iterator iterator() {return new Itr();}private class Itr<T> implements Iterator<T> {// 指向当前元素，默认第一个（索引是0）int cursor = 0;// 指定当前元素的前一个元素用途在于remove使用int lastRet = -1;@Overridepublic boolean hasNext() {return cursor != size;}@Overridepublic T next() {int i = cursor;cursor++;// 如果不进行hasNext()判断，就可能越界if(i > size) {throw new RuntimeException("没有这个元素了");}return (T)elementData[i];}}
}

1.4. 测试ArrayList

java">public class TestArrayList {public static void main(String[] args) {// 创建线性顺序表List list = new ArrayList();// 向末尾添加元素list.add("111");list.add("222");list.add(2, "AAAA");// 进行各种操作验证添加System.out.println(list.size()); // 3System.out.println(list.isEmpty()); // falseSystem.out.println(list.get(2)); // AAAASystem.out.println(list.contains("2")); // falseSystem.out.println(list.indexOf("222")); // 1System.out.println(list.toString()); // [111,222,AAAA]Iterator<String> it = list.iterator();while (it.hasNext()) {String elem = it.next();System.out.println(elem);}}
}

2. 手写单链表和LinkedList

2.1. 单链表技能点

• 认识单链表
  * 特点
  • 数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素
  • 每个节点是由数据域和指针域组成。元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻。
• 缺点
  1. 比顺序存储结构的存储密度小（每个节点都由数据域和指针域组成，所以相同空间内假设全存满，顺序比链式存储的更多）
  2. 按照索引查找节点时，链式存储比顺序存储满（每个节点地址不连续、无规律，导致按照索引查询效率低下）
• 优点
  1. 插入、删除灵活（不必移动节点，只要改变节点中的指针，但是需要先定位到元素上）
  2. 有元素才会分配节点空间，不会有闲置的节点
• 添加节点
  
• 删除节点
  
• 带头节点的单链表
  在使用单链表实现线性表时，为了使程序更加简洁，通常在单链表最前面添加一个哑元节点，也称头节点。
  在头节点中不存储任何实质的数据对象，其next域指向线性表中0号元素所在的节点
  可以对空表、非空表的情况以及对首元节点进行统一管理，编程更方便，常用头节点。
  一个不带头节点和带头节点的单链表实现线性表的结构如图所示
  
  

2.2. 手写单链表

• 定义单链表节点
  

java">public class Node {// 存储数据Object data;// 指向下一个节点的指针Node next;public Node() {super();}public Node(Object data) {super();this.data = data;}public Node(Object data, Node next) {super();this.data = data;this.next = next;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}@Overridepublic String toString() {return "Node{" +"data=" + data +", next=" + next +'}';}
}

• 手写单链表

java">public class SingleLinkedList implements List{// 头节点，哑巴节点，不存储数据，为了方便编程private Node head = new Node();// 节点的个数private int size = 0;@Overridepublic int size() {return size;}@Overridepublic Object get(int i) {// i从0开始// 判断i值是否合理if(i < 0 || i >= size) {throw new IndexOutOfBoundsException("索引越界：" + i);}// 从第一个节点开始查找Node p = head.next; // p初始指向第一个节点（不是头节点）for (int j = 0; j < i; j++) {// p指向下个节点p = p.next;}// 返回第i个节点，而不是第i个节点的datareturn p;}@Overridepublic void add(int i, Object e) {// i值合理性判断if(i < 0 || i > size) {throw new IndexOutOfBoundsException("索引越界：" + i);}// 先找到前一个（如果当前索引是0，前一个就是head）Node p = head;if(i != 0) {p = (Node)this.get(i - 1);}// 创建一个新节点，给data复制Node newNode = new Node(e);// 指定新节点的下一个节点newNode.next = p.next;// 指定前一个节点的下一个节点是当前新节点p.next = newNode;// 数量+1size++;}@Overridepublic Object remove(int i) {if(i < 0 || i>= size) {throw new IndexOutOfBoundsException("索引越界：" + i);}// 先找到前一个（如果当前索引是0，前一个就是head）Node p = head;if(i != 0) {p = (Node)this.get(i - 1);}// 指向要删除的节点Node currentNode = p.next;// 完成删除操作p.next = currentNode.next;currentNode.next = null;// 提示将要删除的节点变成垃圾currentNode = null;// 数量-1size--;return null;}@Overridepublic String toString() {StringBuilder builder = new StringBuilder("[");// p初始指向第一个节点（不是头节点）Node p = head.next;for (int j = 0; j < size; j++) {builder.append(p.data + "   ");// p指向下一个节点p = p.next;}builder.append("]");return builder.toString();}@Overridepublic boolean isEmpty() {return size == 0;}
}

• 单链表添加、删除、查询原理
  

• 测试单链表

java">public class TestList {public static void main(String[] args) {java.util.ArrayList list2;// 创建线性顺序表List list = new SingleLinkedList();// 向末尾添加元素list.add("1");list.add("2");list.add("3");list.add(3, "4");list.remove(2);// 进行各种操作验证添加System.out.println(list.size()); // 3System.out.println(list.isEmpty()); // falseSystem.out.println(list.contains("4")); // trueSystem.out.println(list.indexOf("2")); // 1System.out.println(list.toString()); // [1 2 4]}
}

2.3. 手写LinkedList

• LinkedList底层原理
  • LinkedList底层是一个双向链表；添加、删除元素效率高；按照索引查找效率低。可以两个方向查询
    
  • 每个节点都包含了对前一个和后一个元素的引用
    
  • LinkedList同时实现了List、Deque、Queue接口，所以可以当作线性表、队列、双端队列、栈使用
    
  • LinkedList是非同步的（线程不安全）
  • 不存在LinkedList容量不足的问题
• 定义LinkedList节点

java">public class LinkedList implements List{/** 静态内部类，代表LinkedList的每个节点* */public 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;}@Overridepublic String toString() {return "Node{" +"item=" + item +", next=" + next +", prev=" + prev +'}';}}
}

java">public class LinkedList implements List{transient int size = 0;transient Node first;transient Node last;@Overridepublic int size() {return size;}@Overridepublic Object get(int i) {return node(i).item;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean contains(Object e) {return false;}@Overridepublic int indexOf(Object e) {return 0;}@Overridepublic void add(int index, Object element) {if(index == size) {linkLast(element);}else {linkBefore(element, node(index));}}Node node(int index) {if(index < (size >> 1)) {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;}}void linkBefore(Object e, Node succ) {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++;}@Overridepublic void add(Object e) {linkLast(e);}public 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++;}public String toString() {return first.toString();}
}

• LinkedList的add(Object)方法的实现过程
  
• 测试LinkedList

java">public class TestList1 {public static void main(String[] args) {// 创建线性顺序表List list = new LinkedList();// 向末尾添加元素list.add(1);list.add(2);list.add(3);list.add(3, 4);// 进行各种操作验证添加System.out.println(list.size()); // 4System.out.println(list.isEmpty()); // falseSystem.out.println(list.get(0)); // 1}
}

3. 手写HashMap

3.1. HashMap的原理

• 底层结构是哈希表，采用了顺序表+链表结合的结构；同一个链表上所有元素的存储地址都是相同的，是发生冲突的元素
  
• 链表上每个节点的就是一个Entry，字段包括四部分
  
  同一个链表上节点的哈希码可能不相同，存储的地址是相同的
• 哈希表的优点
  • 添加块、查询块（通过计算得到存储位置，不是通过比较）
  • 无序
  • key唯一
• 关键参数
  • 默认主数组长度16
  • 默认装填因子0.75
  • 每次主数组扩容为原来的2倍
• JDK8中，当链表长度大于8时，链表变为红黑树
  
• 第一步计算哈希码，不仅调用了hashCode()，又进行了多次散列。目的在于key不同，哈希码尽量不同，减少冲突

java">final int hash(Object k) {int h = 0;h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

• 细节：发生冲突，经过比较不存在相同key的元素，要添加一个新的节点。不是加到链表最后，而是添加到链表最前。
  

3.2. 定义Map接口

java">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();}
}

3.3. 手写HashMap

java">public class HashMap implements Map{// 指向哈希表的数组引用public Entry[] table;// 键值对数量int size;public HashMap() {// 哈希表主数组默认长度16table = new Entry[11];}@Overridepublic void put(Object key, Object value) {// 计算哈希码int hash = key.hashCode();// 根据哈希码计算存储位置int index = hash % table.length;// 存入指定位置// 如果该位置没有元素，增加一个节点if(table[index] == null) {table[index] = new Entry(hash, key, value);size++;}else {// 如果有元素，进行逐个比较Entry entry = table[size];while (entry != null) {// 如果找到了相同的keyif(entry.getKey().equals(key)) {// 新的value替代旧的valueentry.value = value;return;}entry = entry.next;}// 循环结束，表明也没有相同的key，在链表最前添加一个节点Entry firstEntry = table[index];table[index] = new Entry(hash, key, value, firstEntry);size++;}}@Overridepublic Object get(Object key) {// 计算哈希码int hash = key.hashCode();// 根据哈希码计算存储位置int index = hash % table.length;// 查找对应的EntryEntry entry = null;if(table[index] != null) {Entry currentEntry = table[index];while (currentEntry != null) {if(currentEntry.getKey().equals(key)) {entry = currentEntry;break;}currentEntry = currentEntry.next;}}return entry == null ? null : entry.getValue();}@Overridepublic 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.getKey() + "=" + entry.getValue() + "," + entry = entry.next);}}}if(builder.length() != 1) {builder.deleteCharAt(builder.length() - 1);}builder.append("}");return builder.toString();}@Overridepublic int size() {return size;}@Overridepublic boolean isEmpty() {return size == 0;}
}
public class Entry implements Map.Entry{private int hash;private Object key;private Object value;// 指向下一个节点的指针private Entry next;public Entry() {}public Entry(int hash, Object key, Object value) {this.hash = hash;this.key = key;this.value = value;}public Entry(int hash, Object key, Object value, Entry next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}@Overridepublic Object getKey() {return key;}@Overridepublic Object getValue() {return value;}@Overridepublic String toString() {return "Entry{" +"hash=" + hash +", key=" + key +", value=" + value +", next=" + next +'}';}
}

3.4 测试HashMap

java">public class TestHashMap {public static void main(String[] args) {java.util.HashMap map1;HashMap map = new HashMap();map.put(23, "china");map.put(36, "Japan");System.out.println(map.size());System.out.println(Arrays.toString(map.table));System.out.println(map);}
}

4. 新一代并发集合类

4.1. 手写HashSet

• HashSet底层就是HashMap，哈希表的每个Entry的key是每个元素，value统一都是new Object()

java">public interface Set {public int size();public void add(Object obj);public boolean isEmpty();public boolean contains(Object obj);
}
public class HashSet implements Set {private transient HashMap map;private static final Object PRESENT = new Object();public HashSet() {this.map = new HashMap();}@Overridepublic int size() {return map.size();}@Overridepublic void add(Object key) {map.put(key, PRESENT);}@Overridepublic boolean isEmpty() {return map.isEmpty();}@Overridepublic boolean contains(Object obj) {return map.get(obj) != null;}
}

4.2. 三代集合类发展过程

• 第一代线程安全集合类
  • Vector、Hashtable：使用synchronized修饰方法来保证线程安全
  • 缺点：效率低下
• 第二代线程非安全集合类（主流）
  • ArrayList、HashMap：线程不安全，但性能好，用来替代Vector、Hashtable
  • 线程安全的：使用Collections.synchronizedList(list)和Collections.synchronizedMap(m)，底层使用synchronized代码块锁，虽然也是锁住了所有的代码，但是所在方法里面，比所在方法外性能稍有提高，毕竟进方法本身是要分配资源的
• 第三代线程安全集合类（波浪式前进，螺旋式上升）
  • 在有大量并发下，使用java.util.concurrent.*中的ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet来提高集合的效率和安全，底层大都采用Lock锁（1.8的ConcurrentHashMap不使用Lock锁），保证安全的同时，性能也很高

4.3. 新一代并发集合类

• ConcurrentHashMap：分段（segment）锁定+Lock锁
  • JDK1.7中
    • 比HashMap的线程安全，并且性能比Hashtable好，Collections.synchronizedMap(m)都有提高
    • 使用的不是synchronized代码块锁或方法锁，使用了锁分离技术，用多个锁来控制对hash表的不同部分（段segment）进行的修改，采用ReentrantLock锁来实现
    • 如果多个修改操作发生在不同的段上，就可以并发执行，从而提高效率
  • JDK1.8中
    • 摒弃了segment锁段的概念，而是采用了volatile+CAS实现无锁化操作。**底层由数组+链表+红黑树的方式（JDK1.8中HashMap的实现）。**为了做到并发，又增加了很多辅助的类，如TreeBin，Traverser等对象内部类
• CopyOnWriteArrayList：CopyOnWrite+Lock锁
  • 对于set()、add()、remove()等方法使用ReentrantLock的Lock和unlock来加锁和解锁，读操作不需要加锁（之前集合安全类，即使读操作也要加锁，保证数据的实时一致）
  • CopyOnWrite原理：写时复制
    • 当往一个容器中添加元素时，不直接添加，而是先将容器进行copy，然后往新容器中添加元素
    • 添加完元素之后，再将原容器的引用指向新容器。这样做的好处是可以对CopyOnWrite容器进行并发读，而不需要加锁，因为当前容器不会添加任何元素，所以CopyOnWrite容器也是一种读写分离的思想，读和写使用不同的容器。
    • 适合对于读操作远多于写操作的应用，特别在并发的情况下，可以提高性能的并发读取
    • CopyOnWrite容器只能保证数据的最终一致性，不能保证数据实时一致性。因此，如果希望写入数据马上能读到，就不要使用CopyOnWrite容器

java">	public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;// 复制出新数组Object[] newElements = Arrays.copyOf(elements, len + 1);// 把新元素添加到新数组中newElements[len] = e;// 把原数组引用指向新数组setArray(newElements);return true;}finally {lock.unlock();}}final void setArray(Object[] a) {array = a;}public E get(int index) {return get(getArray(), index);}

注意：读时不需要加锁，如果读时有多个线程正在向ArrayList添加数据，读还是会读到旧数据，因为写时不会锁住旧的ArrayList

• CopyOnWriteArraySet：CopyOnWrite+Lock锁
  • 线程安全的无序集合，CopyOnWriteArraySet和HashSet都继承于共同的父类AbstractSet；但是HashSet是通过散列表HashMap实现的，而CopyOnWriteArraySet是通过动态数组CopyOnWriteArrayList实现的
  • CopyOnWriteArraySet在CopyOnWriteArrayList基础上使用了Java的装饰模式，所以底层是相同的。 而CopyOnWriteArrayList本质是动态数组队列，所以CopyOnWriteArraySet相当于通过动态数组实现的集合
  • CopyOnWriteArrayList中允许有重复的元素；但CopyOnWriteArraySet不能有重复的元素。因此，CopyOnWriteArrayList额外提供了addIfAbsent()和addAllAbsent()这两个添加元素的API，通过API来添加元素，只有当元素不存在时才执行添加操作。