数据结构整理知识点笔记1.单线程集合1.1 ArrayListl ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。l 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。l ArrayList的克隆函数，即是将全部元素克隆到一个数组中。l ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。l ArrayList中的操作不是线程安全的。1.2 LinkedListl LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。l LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。l LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。l LinkedList中的操作不是线程安全的。1.3 HashMapHashMap的主体是一个数组，数组中的每个元素是一个单向链表，链表的一个节点是嵌套类Entry的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。 capacity：当前数组容量，始终保持 2n，可以扩容，扩容后数组大小为当前的 2 倍。默认的初始容量为16。 loadFactor：负载因子，默认为 0.75。 threshold：扩容的阈值，等于 capacity * loadFactor。当HashMap的大小=阈值，并且新值要插入的数组位置已经有元素了，则进行扩容。Put方法：HashMap会对null值key进行特殊处理，总是放到table0位置。put过程是先计算key的hash然后通过hash与table.length取模计算index值，然后将键值对放到tableindex位置，当tableindex已存在其它元素时，会在tableindex位置形成一个单向链表，将新添加的元素放在tableindex所对应链表的头部，原来的元素通过Entry的next进行链接，这样以链表形式解决hash冲突问题，当元素数量达到临界值(capactiy*factor)时，则进行扩容，是table数组长度变为table.length*2get方法：同样当key为null时会进行特殊处理，在table0的链表上查找key为null的元素。get的过程是先计算key的hash然后通过hash与table.length取摸计算index值，然后遍历tableindex上的链表，直到找到目标值，然后返回。resize方法：这个方法实现了非常重要的hashmap扩容，具体过程为：先创建一个容量为table.length*2的新数组，修改临界值，然后把table里面元素计算hash值并使用hash与table.length*2重新计算index放入到新的table里面。这里需要注意下是用每个元素的hash全部重新计算index，而不是简单的把原table对应index位置元素简单的移动到新table对应位置。clear方法：遍历table然后把每个位置置为null，同时修改元素个数为0。需要注意的是clear方法只会清除里面的元素，并不会重置capactiy。containsKey和containsValue:containsKey方法是先计算hash然后使用hash和table.length取模得到index值，遍历tableindex元素查找是否包含key相同的值。containsValue方法就比较粗暴了，就是直接遍历所有元素直到找到value。Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。1.4 HashSetHashSet实现Set接口，不能有重复的元素，不保证Set的迭代顺序，特别是它不保证该顺序恒久不变。HashSet允许使用null元素。HashSet是基于HashMap实现的，在HashSet中，元素都存到HashMap键值对的Key上面，而Value都是一个统一的值private static final Object PRESENT = new Object();。1. 多线程集合2.1 Vectorl vector是矢量队列，支持相关的添加、删除、修改、遍历等功能。l vector继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。l Vector中的操作是线程安全的。数据结构：1) elementData 是Object类型的数组，它保存了添加到Vector中的元素。elementData是个动态数组，如果初始化Vector时，没指定动态数组的大小，则使用默认大小10，当Vector容量不足以容纳全部元素时，Vector的容量会增加。2) elementCount 是动态数组的实际大小。3) capacityIncrement 是动态数组的增长系数。如果在创建Vector时，指定了capacityIncrement的大小，则每次当Vector中动态数组容量增加时，增加的大小都是capacityIncrement；否则将容量大小增加一倍。2.2 HashTableHashTable已经被淘汰了，如果不需要线程安全，使用HashMap；如果需要线程安全，使用ConcurrentHashMap。HashTable的key和value都不能为空。HashTable会尽量使用素数、奇数，而HashMap则总是使用2的幂作为哈希表的大小。我们知道当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀，所以单从这一点上看，HashTable的哈希表大小选择，似乎更高明些。但另一方面我们又知道，在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。所以从hash计算的效率上，又是HashMap更胜一筹。2.3 ConcurrentHashMapHashMap在并发环境下使用中最为典型的一个问题，就是在HashMap进行扩容重哈希时导致Entry链形成环。一旦Entry链中有环，势必会导致在同一个桶中进行插入、查询、删除等操作时陷入死循环。ConcurrentHashMap允许多个修改(写)操作并发进行，其关键在于使用了锁分段技术，它使用了不同的锁来控制对哈希表的不同部分进行的修改(写)，而 ConcurrentHashMap 内部使用段(Segment)来表示这些不同的部分。实际上，每个段就是一个小的哈希表，每个段都有自己的锁(Segment 类继承了 ReentrantLock 类)。这样，只要多个修改(写)操作发生在不同的段上，它们就可以并发进行。ConcurrentHashMap实现线程安全的关键点： Segment类继承了ReentrantLock类，对每个段进行写操作时都会加锁。 在HashEntry类中，key，hash和next域都被声明为final的，value域被volatile所修饰，因此HashEntry对象几乎是不可变的，这是ConcurrentHashmap读操作并不需要加锁的一个重要原因。 ConcurrentHashMap中key和value都不允许为空，但在读操作时有可能会出现键值对存在但读出来的value值为空的情形。这种情形发生的场景是：初始化HashEntry时发生的指令重排序导致的，也就是在HashEntry初始化完成之前便返回了它的引用。这时，JDK给出的解决之道就是加锁重读。 size方法主要思路是先在没有锁的情况下对所有段大小求和，这种求和策略最多执行RETRIES_BEFORE_LOCK次(默认是两次)；在超过RETRIES_BEFORE_LOCK之后，如果还不成功就在持有所有段锁的情况下再对所有段大小求和。相较于JDK1.7，在JDK1.8中，对ConcurrentHashMap做了较大的改动，主要有两方面： 取消segments字段，直接采用transient volatile HashEntry table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。 将原先table数组单向链表的数据结构，变更为table数组单向链表红黑树的结构。2.4 CopyOnWriteArrayListCopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。CopyOnWriteArrayList在添加的时候是需要加锁的，否则多线程写的时候会Copy出N个副本出来。读的时候不需要加锁，如果读的时候有多个线程正在向CopyOnWriteArrayList添加数据，读还是会读到旧的数据，因此CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。2. 树3.1 二叉查找树二叉查找树(没有重复元素)的特征是:对于树中的每一个结点，它的左子树中结点的值都小于该结点的值，而它的右子树中结点的值都大于该结点的值。可以采用前序插入元素的方法重构一棵二叉查找树，重构的树为原始的二叉查找树保留了父结点和子结点的关系。二叉查找树的中序遍历是一个排好序的线性表。删除BST中的一个元素：l 情况1：当前节点没有左子节点。只需要将当前节点的父节点和当前节点的右子节点相连。l 情况2：当前节点有左子节点。假设rightMost 指向包含current 结点的左子树中最大元素的结点（rightMost 结点不能有右子结点，但是可能会有左子结点），而parentOfRightMost 指向rightMost 结点的父结点。使用rightMost 结点中的元素值替换current 结点中的元素值，将parentOfRightMost 结点和rightMost 结点的左子结点相连，然后删除rightMost 结点。霍夫曼编码树霍夫曼编码通过使用更少的比特对经常出现的字符编码来压缩数据。字符的编码是基于字符在文本中出现的次数使用二又树来构建的.该树称为霍夫曼编码树。例如，假设文本为Mississippi，则它的霍夫曼树如下图：对应的编码方案为：为了构建一棵霍夫曼编码树，使用如下算法:1) 从由树构成的森林开始。每棵树都包含一个字符结点。每个结点的权重就是文本中字符的出现次数。2) 重复以下步骤来合并树，直到只有一棵树为止:选择两棵有最小权重的树，创建一个新结点作为它们的父结点。这棵新树的权重是子树的权重和。3) 对于每个内部结点，给它的左边赋值0 ，而给它的右边赋值1 。所有的叶子结点都表示文本中的字符。没有编码是