最近一直在整理数据结构的知识，系统地看了下Java中常用的数据结构，突然想到用动画来画数据流转过程。主要基于jdk8，部分特性可能与jdk7之前有所不同，例如LinkedListLinkedHashMap中的双向链表不再回环。HashMap中的单链表是插在末尾，而不是插在头部等，这些区别后面不再详述。本文目录结构如下：1、LinkedListLinkedList经典的双链表结构，适合随机插入和删除。指定序列操作的性能不如ArrayList，这也是由它的数据结构决定的。add(E)/addLast(E)add(index,E)这里有个小优化，会先判断index是靠近队头还是队尾来决定从哪个方向遍历链接。if(index<(size>>1)){Nodex=first;for(inti=0;ix=last;for(inti=size-1;i>index;i--)x=x.prev;returnx;}依赖队尾的get(index)也会先判断索引，但是性能还是不好，这也是为什么不推荐使用for(inti=0;i8的链表，这个我们在另一个空间讲。put(K,V)put(K,V)相同的哈希值resize动态扩容当map中的元素超过设定的阈值时，会进行resize(length*2)操作。在扩展过程中，元素将被操作一次并放置在新的位置。具体操作如下：在jdk7中，直接rehash所有元素，放到新的位置。在jdk8中，判断元素原哈希值新增的位是0还是1，如果为0则索引不变，如果为1则索引变为“原索引+oldTable.length”//两条链的定义//原来的hash值加了一个bit为0的链，头尾NodeloHead=null,loTail=null;//原来新的hash值是一个bit为0的链of1,头尾NodehiHead=null,hiTail=null;Nodenext;//遍历链chaindo{next=e.next;if((e.hash&oldCap)==0){if(loTail==null)loHead=e;elseloTail.next=e;loTail=e;}else{if(hiTail==null)hiHead=e;elsehiTail.next=e;hiTail=e;}}while((e=next)!=null);//扩容前后位置相同的链if(loTail!=null){loTail.next=null;newTab[j]=loHead;}??//展开的位置加上原数组长度的chainif(hiTail!=null){32hiTail.next=null;33newTab[j+oldCap]=hiHead;34}7.LinkedHashMap继承来自HashMap，底层维护了一个双向链表，保持数据有序。FIFO（有序插入）或LRU（有序访问）缓存可以通过设置accessOrder来实现。当put(K,V)get(K)accessOrder为false时，直接返回元素，不调整位置。当accessOrder为真时，最近访问的元素需要放在队列的末尾。removeEldestEntry删除最旧的元素
