JAVA容器
容器家族：
容器主要包括 Collection 和 Map 两种，
Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。
List,Set,Map 三者的区别
List(对付顺序的好帮手)： 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
Map(用 Key 来搜索的专家): 使用键值对（kye-value）存储，类似于数学上的函数 y=f(x)，“x”代表 key，"y"代表 value，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
set
Set是最简单的一种集合。集合中的对象不按特定的方式排序，并且没有重复对象。
Set是一个继承于Collection的接口，Set是一种不包括重复元素的Collection。
Set接口主要实现了两个实现类：
HashSet： HashSet类按照哈希算法来存取集合中的对象，存取速度比较快
TreeSet ：TreeSet类实现了SortedSet接口，能够对集合中的对象进行排序。
Set<Integer> set=new HashSet<> ();
set.add(s1);
set.contains(xxx)
list
List的特征是其元素以线性方式存储，集合中可以存放重复对象。
List是一个继承于Collection的接口，即List是集合中的一种。List是有序的队列，List中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次+1。和Set不同，List中允许有重复的元素。
List接口主要实现类包括：
ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。
LinkedList(): 在实现中采用链表数据结构。插入和删除速度快，访问速度慢。
List<Integer> aList=new ArrayList<>();
list.add(value); // list.add(index,value);
list.get(index)
map
Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。
Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。
Map<Integer, Integer> num = new HashMap<>();
num.put(key, value);
num.containsKey(key);
num.get(key); 得到value
String
StringBuilder sb = new StringBuilder();
char c = str.charAt(i);
sb.append(c);
return sb.toString();
StringBuffer str;
return str.toString().replace(" ", "%20");
几个常用类的区别
1．ArrayList: 元素单个，效率高，多用于查询
2．Vector: 元素单个，线程安全，多用于查询
3．LinkedList:元素单个，多用于插入和删除
4．HashMap: 元素成对，元素可为空
5．HashTable: 元素成对，线程安全，元素不可为空
二、Vector、ArrayList和LinkedList
大多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现，但是它们三个性能都比不上数组，另外Vector是线程同步的。所以：
如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List；
如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList；
如果在多线程条件下使用，可以考虑Vector；
如果需要频繁地删除插入，LinkedList就有了用武之地；
如果你什么都不知道，用ArrayList没错。
三、Collections和Arrays
在 Java集合类框架里有两个类叫做Collections（注意，不是Collection！）和Arrays，这是JCF里面功能强大的工具，但初学者往往会忽视。按JCF文档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应用。
想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧，Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作：
binarySearch：折半查找。
sort：排序，这里是一种类似于快速排序的方法，效率仍然是O(n * log n)，但却是一种稳定的排序方法。
reverse：将线性表进行逆序操作，这个可是从前数据结构的经典考题哦！
rotate：以某个元素为轴心将线性表“旋转”。
swap：交换一个线性表中两个元素的位置。
……
Collections还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合，如下：
unmodifiableXXX：转换成只读集合，这里XXX代表六种基本集合接口：Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作，将会抛出UnsupportedOperationException异常。
synchronizedXXX：转换成同步集合。
singleton：创建一个仅有一个元素的集合，这里singleton生成的是单元素Set，
singletonList和singletonMap分别生成单元素的List和Map。
空集：由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。
set
Set是最简单的一种集合。集合中的对象不按特定的方式排序，并且没有重复对象。
Set是一个继承于Collection的接口，Set是一种不包括重复元素的Collection。
HashSet： HashSet类按照哈希算法来存取集合中的对象，存取速度比较快
TreeSet ：TreeSet类实现了SortedSet接口，能够对集合中的对象进行排序。
HashSet和TreeSet的区别
1、TreeSet 是二差树实现的,Treeset中的数据是自动排好序的，不允许放入null值。
2、HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。
3、HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。
HashSet：
内部的数据结构是哈希表，是线程不安全的。
HashSet中保证集合中元素是唯一的方法：通过对象的hashCode和equals方法来完成对象唯一性的判断。如果对象的hashCode值不同，则不用判断equals方法，就直接存到HashSet中。
TreeSet：
是SortedSet接口的唯一实现类，TreeSet可以保证集合元素处于排序状态。
是线程不安全的。
TreeSet存放对象时，是根据对象的compareTo方法比较两个对象是否相等，并进行比较。
提供一个使用树结构存储set接口的实现（红黑树算法）。对象以升序顺序存储，访问和遍历的时间很快。
HashSet的实现：
对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，更确切的说，HashSet中的元素，只是存放在了底层HashMap的key上， 而value使用一个static final的Object对象标识。因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成。
Set的实现类的集合对象中不能够有重复元素，HashSet也一样他是使用了一种标识来确定元素的不重复，HashSet用一种算法来保证HashSet中的元素是不重复的，HashSet采用哈希算法，底层用数组存储数据。默认初始化容量16，加载因子0.75。
list
List的特征是其元素以线性方式存储，集合中可以存放重复对象。
List是一个继承于Collection的接口，即List是集合中的一种。List是有序的队列，List中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次+1。和Set不同，List中允许有重复的元素。
ArrayList() :
代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。
线程不同步，线程不安全，但是高效。
LinkedList():
在实现中采用链表数据结构。插入和删除速度快，访问速度慢。
线程不同步，线程不安全，但是高效。
vector
与ArrayList实现原理相同，都是通过数组形式实现的。
只不过vector线程安全（方法加synchronized修饰）。
ArrayList和LinkedList和vector区别
对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
ArrayList和Vector中，从指定的位置检索一个对象，或在集合的末尾插入、删除一个元素的时间是一样的，时间复杂度都是O（1）。但是如果在其他位置增加或者删除元素花费的时间是O（n）
LinkedList中，在插入、删除任何位置的元素所花费的时间都是一样的，时间复杂度都为O（1），但是他在检索一个元素的时间复杂度为O（n）.
所以如果只是查找特定位置的元素或只在集合的末端增加移动元素，那么使用ArrayList或Vector都是一样的。如果是在指定位置的插入、删除元素，最好选择LinkedList
三者都属于List的子类，方法基本相同。比如都可以实现数据的添加、删除、定位以及都有迭代器进行数据的查找，但是每个类在安全，性能，行为上有着不同的表现。
Vector是Java中线程安全的集合类，如果不是非要线程安全，不必选择使用，毕竟同步需要额外的性能开销，底部实现也是数组来操作，再添加数据时，会自动根据需要创建新数组增加长度来保存数据，并拷贝原有数组数据
ArrayList是应用广泛的动态数组实现的集合类，不过线程不安全，所以性能要好的多。扩容上：也可以根据需要增加数组容量，不过与Vector的调整逻辑不同，ArrayList增加50%，而Vector会扩容1倍。这样,ArrayList就有利于节约内存空间。
ArrayList扩容：
扩容时机当数组的大小大于初始容量的时候(比如初始为10,当添加第11个元素的时候),就会进行扩容。
1、扩容
确定新数组的长度，确定之后就是把老数组copy到新数组中（Arrays.copy()），这样数组的扩容就结束了。
2、添加元素
把新元素添加到扩容以后的数组中。
LinkedList是基于双向链表实现，不需要增加长度，也不是线程安全的
Vector与ArrayList在使用的时候，应保证对数据的删除、插入操作的减少，因为每次对改集合类进行这些操作时，都会使原有数据
进行移动除了对尾部数据的操作，所以非常适合随机访问的场合。
LinkedList进行节点的插入、删除却要高效的多，但是随机访问对于该集合类要慢的多。
map
Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。
Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。
传统集合中只有Hash Table 和 Vector 两个线程安全。
map是键值对的集合接口，它的实现类主要包括：HashMap,TreeMap,Hashtable以及LinkedHashMap等。其中这四者的区别如下（简单介绍）：
HashMap：我们最常用的Map，它根据key的HashCode 值来存储数据,根据key可以直接获取它的Value，同时它具有很快的访问速度。HashMap最多只允许一条记录的key值为Null(多条会覆盖);允许多条记录的Value为 Null。非同步的。HashMap是无序的。
TreeMap: 能够把它保存的记录根据key排序,默认是按升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。（底层红黑树）是有序的，按照key值排列，默认是升序。二叉树的中序遍历保证了数据的有序性。
Hashtable: 与 HashMap类似,不同的是:key和value的值均不允许为null;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢。
LinkedHashMap: 保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.在遍历的时候会比HashMap慢。key和value均允许为空，非同步的。底层存储结构是哈希表+双向链表，链表记录了添加数据的顺序。是有序的。（按照插入元素顺序进行排序的；也可以按照访问顺序进行有序排列的）
HashMap
1.7中：数组+链表
java7中先hash位运算（不是取模），然后存入数组，冲突的话用链表继续存（头插法，新数据插入这一格的链表的头部！）
put：
判断当前数组是否需要初始化。
如果 key 为空，则 put 一个空值进去。
根据 key 计算出 hashcode。
根据计算出的 hashcode 定位出所在桶。
如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等，如果相等则进行覆盖，并返回原来的值。
如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置。
get：
首先也是根据 key 计算出 hashcode，然后定位到具体的桶中。
判断该位置是否为链表。
不是链表就根据 key、key 的 hashcode 是否相等来返回值。
为链表则需要遍历直到 key 及 hashcode 相等时候就返回值。
啥都没取到就直接返回 null 。
哈希冲突解决：
HashMap即是采用了链地址法，也就是数组+链表的方式。
容量：
HashMap要求容量必须是2的幂：
因为hash计算的时候用的与运算，不是2的指数次幂会数组越界！
参数：
size：实际存储的key-value键值对的个数
threshold：阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold=capacity*loadFactory。
loadFactor：负载因子，代表了table的填充度有多少，默认是0.75。为了减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
负载因子值的大小，对HashMap有什么影响？
负载因子的大小决定了HashMap的数据密度。
负载因子越大，密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。
负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。
HashMap的扩容机制
当前存放新值（注意不是替换已有元素位置时）的时候当前已有元素的个数必须大于等于阈值（容量*负载因子）
（已有元素等于阈值，下一个存放后必然触发扩容机制）
扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。
当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
扩容。
这个过程也叫作rehashing，因为它重建内部数据结构，并调用hash方法找到新的bucket位置。
大致分两步：
1.扩容：容量扩充为原来的两倍（2 * table.length）；
2.移动：对每个节点重新计算哈希值，重新计算每个元素在数组中的位置，将原来的元素移动到新的哈希表中。在前面提到，HashMap 使用 hash%capacity 来确定桶下标。HashMap capacity 为 2 的 n 次方这一特点能够极大降低重新计算桶下标操作的复杂度。
先按照数组的顺序依次遍历，在对每个数组中的链表/红黑树进行rehash，从链表的尾结点起。
1.8中：数组+链表+红黑树
put：
1）判断table是否为空，为空表明这是第一个元素插入，则初始化，使用resize()进行扩容，初始大小默认16
2）根据当前 key执行hash(Object key)得到一个int类型的hash值，然后根据这个hash值就可以找到Node节点的位置了，确定元素存放在哪个桶中
3）如果当前桶为空，表明没有 Hash 冲突
新生成结点放入桶中(放在数组中)，跳到第6步
4）如果当前桶有值（Hash 冲突），用一个节点e作为返回来记录当前操作后的节点。
桶中第一个元素(数组中的结点)的hash值相等，key相等，赋值给node节点e; （新值覆盖旧值）
hash值不相等，说明key不相等：
如果当前桶为红黑树，
那就要按照红黑树的方式写入数据，赋值给node节点e;
如果为链表，则遍历链表：
过程中，如果有key满足相等条件，替换旧值，返回node节点e；
否则插入key-value到链表最后（尾插法）并返回node节点e；
插入之后如果当前链表长度大于TREEIFY_THRESHOLD（8），转换成红黑树结构。
5）如果 返回的 e != null 就相当于存在相同的 key，还要判断一个参数onlyIfAbsent（决定要不要新值替换旧值），如果要替换旧值，就将旧值记录并返回，随后这里直接将旧值覆盖。如果是有值的话，在上面就已经插入了，所以现在也不再需要插入的操作了。
6）最后判断是否需要进行扩容。实际大小大于阈值则扩容。
get：
首先将 key hash 之后取得所定位的桶。
如果桶为空则直接返回 null 。
否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
如果第一个不匹配，则判断它的下一个是红黑树还是链表。
红黑树就按照树的查找方式返回值。
不然就按照链表的方式遍历匹配返回值。
链表和红黑树：
为什么链表是8次以后就转换为红黑树？红黑树什么时候转回链表？
当链表已经有8个元素了，此时put进第9个元素，先完成第9个元素的put，然后立刻做链表转红黑树。
表示若桶中链表元素超过8时，会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。
原因：
红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
还有选择6和8的原因是：
中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
问题1：为什么不使用二叉查找树？
问题主要出现在二叉排序树在添加元素的时候极端情况下会出现线性结构。
举例说明：由于二叉排序树左子树所有节点的值均小于根节点的特点，如果我们添加的元素都比根节点小，会导致左子树线性增长，这样就失去了用树型结构替换链表的初衷，导致查询时间增长。所以这是不用二叉查找树的原因。
问题2：为什么不使用平衡二叉树呢？
①红黑树不追求"完全平衡"，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。
就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)
但是，删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！
AVL的结构相较于RB-Tree更为平衡，插入和删除引起失衡，如2所述，RB-Tree复衡效率更高；当然，由于AVL高度平衡，因此AVL的Search效率更高，红黑树查找效率低。
针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较"便宜"的解决方案，降低开销，是对search，insert ，以及delete效率的折中，总体来说，RB-Tree的统计性能高于AVL.
故引入RB-Tree是功能、性能、空间开销的折中结果。
② AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。
③ 红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。
基本上主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。
hashmap的key是否可以为null？
可以的，hashtable不可以。
计算哈希的方法见下方，自动转为0。
存储时存在0的桶里。
hash的计算方法：
//重新计算哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//key如果是null 新hashcode是0 ；否则 计算新的hashcode
}
通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标：
static int indexFor(int h, int length) {
return h & (length-1);
}
为什么要无符号右移16位后做异或运算？
将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算，可以将高低位二进制特征混合起来。
从上文可知高区的16位与原hashcode相比没有发生变化，低区的16位发生了变化。
原因：
我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位（桶）的计算，计算公式：(n - 1) & hash，【这里n是总长度，2的倍数】假如这时数组槽位有16个，则槽位计算如下：
仔细观察上文不难发现，高区的16位很有可能会被数组槽位数的二进制码锁屏蔽（相当于没用上高16位的那些数），如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征。
也许你可能会说，即使丢失了高区特征不同hashcode也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现。
使用异或运算的原因：
^ : 位异或 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0
0^0=0， 1^0=1， 0^1=1， 1^1=0
& : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0
0&0=0， 0&1=0， 1&0=0， 1&1=1 eg:用if ((a & 1) == 0) 代替 if (a % 2 == 0)来判断a是不是偶数。
| : 或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0
0|0=0， 0|1=1， 1|0=1， 1|1=1
异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向0靠拢，采用|运算计算出来的值会向1靠拢
为什么槽位数必须使用2^n？
为了让哈希后的结果更加均匀
假如槽位数不是16，而是17，则槽位计算公式变成：(17 - 1) & hash
从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难
上面提到的所有问题，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率
hashmap为什么线程不安全？
resize扩容死循环：（这个问题只针对1.7版本以前的，因为当时是头插法）
我们都知道HashMap初始容量大小为16。1.7版本头插法。
while(null != e) {
Entry<K,V> next = e.next; //线程1执行到这里被调度挂起了
e.next = newTable[i];
newTable[i] = e;
e = next;
}
假设这里有两个线程同时执行了put()操作，并进入了transfer()环节：
Entry<K,V> next = e.next; //线程1执行到这里被调度挂起了
这时候2搞完是这样的：
然后线程1被唤醒了：
1）执行e.next = newTable[i]，于是 key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以e.next = null，
2）执行newTable[i] = e，所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了，e 处理完毕。
3）执行e = next，将 e 指向 next，所以新的 e 是 key(7)
然后该执行 key(3)的 next 节点 key(7)了：
1）现在的 e 节点是 key(7)，首先执行Entry<K,V> next = e.next,那么 next 就是 key(3)了
2）执行e.next = newTable[i]，于是key(7) 的 next 就成了 key(3)
3）执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(7)
4）执行e = next，将 e 指向 next，所以新的 e 是 key(3)
然后又该执行 key(7)的 next 节点 key(3)了：
1）现在的 e 节点是 key(3)，首先执行Entry<K,V> next = e.next,那么 next 就是 null
2）执行e.next = newTable[i]，于是key(3) 的 next 就成了 key(7)
3）执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(3)
4）执行e = next，将 e 指向 next，所以新的 e 是 key(7)
很明显，环形链表出现了！！当然，现在还没有事情，因为下一个节点是 null，所以transfer()就完成了，等put()的其余过程搞定后，HashMap 的底层实现就是线程1的新 Hash 表了。
HashMap是头插法还是尾插法？
JDK8以前是头插法，JDK8开始是尾插法
头插法的原因：
认为后来的值被查找的可能性更大一点，提升查找的效率。
为什么要从头插法改成尾插法？
A. 因为头插法会造成死链，为了安全,防止环化。扩容的时候会有循坏链。
假如扩容时使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。
B.JDK7用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题,因为JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插) 所以最后的结果 还是打乱了插入的顺序 所以总的来看支撑JDK7使用头插的这点原因也不足以支撑下去了 所以就干脆换成尾插 一举多得
但是，JDK1.8仍然存在多线程不安全的情况（put操作）：
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
tab[i] = newNode(hash, key, value, null);
如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
总结
首先HashMap是线程不安全的，其主要体现：
#1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
#2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
HashMap的时间复杂度问题：
put操作的流程：
第一步：key.hashcode()，时间复杂度O(1)。
第二步：找到桶以后，判断桶里是否有元素，如果没有，直接new一个entey节点插入到数组中。时间复杂度O(1)。
第三步：如果桶里有元素，并且元素个数小于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(n)=O(n)。
第四步：如果桶里有元素，并且元素个数大于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。
通过上面的分析，我们可以得出结论，HashMap新增元素的时间复杂度是不固定的，可能的值有O(1)、O(logn)、O(n)。
jdk1.7的concurrentHashmap
数组+链表：
唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。
容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。
原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
put要加分段锁。
当执行put方法插入数据时，根据key的hash值，在Segment数组中找到相应的位置，如果相应位置的Segment还未初始化，则通过CAS进行赋值，接着执行Segment对象的put方法通过加锁机制插入数据，实现如下：
场景：线程A和线程B同时执行相同Segment对象的put方法
1、线程A执行tryLock()方法成功获取锁，则把HashEntry对象插入到相应的位置；
2、线程B获取锁失败，则执行scanAndLockForPut()方法，在scanAndLockForPut方法中，会通过重复执行tryLock()方法尝试获取锁，在多处理器环境下，重复次数为64，单处理器重复次数为1，当执行tryLock()方法的次数超过上限时，则执行lock()方法挂起线程B；
3、当线程A执行完插入操作时，会通过unlock()方法释放锁，接着唤醒线程B继续执行。
get 方法是非常高效的，因为整个过程都不需要加锁（由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值）。
如上图所示，ConcurrentHashMap默认分成了16个segment，每个Segment都对应一个Hash表，且都有独立的锁。所以这样就可以每个线程访问一个Segment，就可以并行访问了，从而提高了效率。这就是锁分段。
jdk1.8的concurrentHashmap
1.8仍然考虑到链表查询效率太低，数组+链表+红黑树
抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
hash算法：
int hash = spread(key.hashCode());
static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;}
与HashMap类似这里计算hash的方式和hashmap基本相同，都是右移16位后异或，只不过不允许key为null。
（key和value都不允许为null）
定位索引：
int index = (n - 1) & hash // n为bucket的个数
put：
检查传入的参数, ConcurrentHashmap不允许null值作key，但是value可以。
判断是否需要进行初始化。
f 即为当前 key 定位出的 Node，
1）如果为空：-- 没有发生hash冲突
表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
2）如果当前map正在扩容，
当前位置的f.hash == MOVED， 则跟其他线程一起协助他们进行扩容。
3）如果都不满足（不为空，出现hash冲突）：
则利用 synchronized 锁只锁住当前节点（桶）写入数据。
链表的话插入到尾巴，红黑树的话加入红黑树再平衡。
如果是链表的话，数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
4）统计节点个数，检查是否需要resize扩容，扩容两倍
get：
（检索操作不用加锁，get方法是非阻塞的）
根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
如果是红黑树那就按照树的方式获取值。
就不满足那就按照链表的方式遍历获取值。
equals()方法
Object类中的equals方法和“==”是一样的，没有区别，即俩个对象的比较是比较他们的栈内存中存储的内存地址。而String类，Integer类等等一些类，是重写了equals方法，才使得equals和“==不同”，他们比较的是值是不是相等。所以，当自己创建类时，自动继承了Object的equals方法，要想实现不同的等于比较，必须重写equals方法。
当我们new一个对象时，将在内存里加载一份它自己的内存，而不是共用！对于static修饰的变量和方法则保存在方法区中，只加载一次，不会再多copy一份内存。所以我们在判断俩个对象逻辑上是否相等，即对象的内容是否相等不能直接使用继承于Object类的equals()方法，我们必须得重写equals()方法，改变这个方法默认的实现。
重写equals方法：先判断比较对象是否为null—>判断比较对象是否为要比较类的实例—–>比较俩个成员变量是否完全相等。
hashcode()方法：
当Set接收一个元素时根据该对象的内存地址算出hashCode，看它属于哪一个区间，再这个区间里调用equeals方法。这里需要注意的是：当俩个对象的hashCode值相同的时候，Hashset会将对象保存在同一个位置，但是他们equals返回false，所以实际上这个位置采用链式结构来保存多个对象。
当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会再调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
但一个面临问题：若两个对象equals相等，但不在一个区间，因为hashCode的值在重写之前是对内存地址计算得出，所以根本没有机会进行比较，会被认为是不同的对象。所以Java对于eqauls方法和hashCode方法是这样规定的：
1. 如果两个对象相同，那么它们的hashCode值一定要相同。也告诉我们重写equals方法，一定要重写hashCode方法，也就是说hashCode值要和类中的成员变量挂上钩，对象相同–>成员变量相同—->hashCode值一定相同。
2. 如果两个对象的hashCode相同，它们并不一定相同，这里的对象相同指的是用eqauls方法比较。
注：如果我们将对象的属性值参与了hashCode的运算中，在进行删除的时候，就不能对其属性值进行修改，否则会出现严重的问题。
为什么在重写equals（）方法时，一般都会重写HashCode（）方法？
重写equals（）方法主要是为了方便比较两个对象内容是否相等。
hashCode（）方法用于返回调用该方法的对象的散列码值，此方法将返回整数形式的散列码值。
在JAVA的集合中，每次要对全部元素进行equal的比较，挨个比较太麻烦了。因此采用hashcode先进行比较，相同的情况下，在对里面所有元素进行比较。
是为了提高效率，采取重写hashcode方法，先进行hashcode比较，如果不同，那么就没必要在进行equals的比较了，这样就大大减少了equals比较的次数，这对比需要比较的数量很大的效率提高是很明显的，一个很好的例子就是在集合中的使用。set集合是不能重复的，那么怎么能保证不能被放入重复的元素呢，但靠equals方法一样比较的话，太麻烦， java就采用了hash表，利用哈希算法（也叫散列算法），只要看对应的hashcode地址上是否有值，有的话就用equals比较，如果没有则直接插入，只要就大大减少了equals的使用次数，执行效率就大大提高了。
总结：
1.使用hashcode方法提前校验，可以避免每一次比对都调用equals方法，提高效率
2.保证是同一个对象，如果重写了equals方法，而没有重写hashcode方法，会出现equals相等的对象，hashcode不相等的情况，重写hashcode方法就是为了避免这种情况的出现。
hashtable与hashmap区别：
0底层数据结构不同
Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
HashMap采用哈希表+链表+红黑树。
1 线程安全性不同
Hashtable是线程安全的，它的每个方法中都加入了Synchronize方法。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步HashMap不是线程安全的，在多线程并发的环境下，可能会产生死锁等问题。具体的原因在下一篇文章中会详细进行分析。使用HashMap时就必须要自己增加同步处理，虽然HashMap不是线程安全的，但是它的效率会比Hashtable要好很多。这样设计是合理的。在我们的日常使用当中，大部分时间是单线程操作的。HashMap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。
2. 计算hash值的方法不同
为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。
Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高，而计算位运算为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2 的幂次方带来的效率提升给抵消掉。
3、HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。
4、key和value是否允许null值
其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。
Hashtable中，key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。
源码：
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
}
可以看出，当时不允许是因为希望每个 key 都会实现 hashCode 和 equals 方法。而 null 显然没有。后来，大家都意识到 null 值的重要性，所以 HashMap 允许 null 值的 key 和 value。当 key 为 null 时，HashMap 将会把 key-value pair 存放在一个特殊的位置，比如 第一个槽位 里。
HashMap中，key和value都可以为null值，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
5 内部实现使用的数组初始化和扩容方式不同
HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。
HashMap和HashTable和concurrentHashMap异同点：
相同点：
1.底层数据结构相同，都为数组+链表（ ConcurrentHashMap为数组+链表）
2.key都不能重复
3.插入元素不能保证有序
4.都是通过key进行哈希
不同点：
1.安全性问题
HashMap是非线程安全的集合，若想让其在多线程下具有安全性：使用集合工具类collection.SyncnizedMap;
HashTable中的方法都有Synchronized修饰，多线程访问时线程安全；
ConcurrentHashMap中通过分段锁机制保证线程安全
2.继承关系：
hashMap和ConcurrentHashMap继承AbstractMap
hashTable继承Dictionary
3.扩容方式：
HashMap和 ConcurrentHashMap为2倍（2table.length）
HashTable为2的倍数+1 [（2table.length）+1]
4.null值：
HashTable的键值不能为null
hashMap键值可以为null
ConcurrentHashMap键可以为null，值不能为null。
5.默认值：
hashTable数组默认大小11
hashMap数组默认大小16
ConcurrentHashMap数组默认大小16
6.hash算法不同:
7.效率不同：
hashMap在单线程下效率高
hashTable和ConcurrentHashMap在多线程下效率高（ConcurrentHashMap更高）
LinkedHashMap：
LinkedHashMap是继承于HashMap，是基于HashMap和双向链表来实现的。
HashMap无序；LinkedHashMap有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)。
LinkedHashMap存取数据，还是跟HashMap一样使用的Entry[]的方式，双向链表只是为了保证顺序。
LinkedHashMap是线程不安全的。
1.LinkedHashMap 继承自 HashMap，是基于HashMap和双向链表来实现的。该结构由数组和链表+红黑树 在此基础上LinkedHashMap 增加了一条双向链表，保持遍历顺序和插入顺序一致的问题。
2.在实现上，LinkedHashMap 很多方法直接继承自 HashMap（比如put remove方法就是直接用的父类的），仅为维护双向链表覆写了部分方法（get（）方法是重写的）。
3.LinkedHashMap使用的键值对节点是Entity 他继承了hashMap 的Node,并新增了两个引用，分别是 before 和 after。这两个引用的用途不难理解，也就是用于维护双向链表.
4.链表的建立过程是在插入键值对节点时开始的，初始情况下，让 LinkedHashMap 的 head 和 tail 引用同时指向新节点，链表就算建立起来了。随后不断有新节点插入，通过将新节点接在 tail 引用指向节点的后面，即可实现链表的更新
5.LinkedHashMap 允许使用null值和null键， 线程是不安全的，虽然底层使用了双线链表，但是增删相快了。因为他底层的Entity 保留了hashMap node 的next 属性。
6.如何实现迭代有序？
重新定义了数组中保存的元素Entry（继承于HashMap.node)，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。仍然保留next属性，所以既可像HashMap一样快速查找，
用next获取该链表下一个Entry，也可以通过双向链接，通过after完成所有数据的有序迭代.
7.竟然inkHashMap 的put 方法是直接调用父类hashMap的，但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么，LinkedHashMap 是怎样建立链表的呢？
虽然linkHashMap 调用的是hashMap中的put 方法，但是linkHashMap 重写了，了一部分方法，其中就有 newNode(int hash, K key, V value, Node<K,V> e)linkNodeLast(LinkedHashMap.Entry<K,V> p)
这两个方法就是 第一个方法就是新建一个 linkHasnMap 的Entity 方法，而 linkNodeLast 方法就是为了把Entity 接在链表的尾部。
8.链表节点的删除过程
与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现，但是LinkHashMap 重写了removeNode()方法 afterNodeRemoval（）方法，该removeNode方法在hashMap 删除的基础上有调用了afterNodeRemoval 回调方法。完成删除。
删除的过程并不复杂，上面这么多代码其实就做了三件事：
根据 hash 定位到桶位置
遍历链表或调用红黑树相关的删除方法
从 LinkedHashMap 维护的双链表中移除要删除的节点
TreeMap
1.TreeMap实现了SortedMap接口，保证了有序性。默认的排序是根据key值进行升序排序，也可以重写comparator方法来根据value进行排序具体取决于使用的构造方法。不允许有null值null键。TreeMap是线程不安全的。
2.TreeMap基于红黑树（Red-Black tree）实现。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
扫一扫
5519
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
