1、java集合分类
- 线程安全的集合对象：
Vector ：是ArrayList的线程安全的实现
HashTable
StringBuffer - 线程不安全的集合对象
ArrayList 、LinkedList、HashMap、HashSet、TreeMap、TreeSet、StringBulider；
image.png
image.png
2、ArrayList 和LinkedList 区别
https://www.cnblogs.com/sierrajuan/p/3639353.html
ArrayList 实际上是封装了对数组的操作，而LinkedList是采用链表的数据结构，两者截然不同的实现方式
ArrayList属性：元素数组，数组容量； LinkedList属性：头节点，尾节点，链表长度（节点包含属性：前驱节点，后去节点，元素内容）；
由于ArrayList实际上就是一个数组（一块连续的内存空间，如果在数组的任意位置插入元素，必然导致在该位置后的所有元素需要重新排列），当添加元素的都会判断是否需要扩容，所以添加性能低，但是读取性能高；
而LinkedList采用链表，添加的直接往最后一个元素添加即可，所 以添加性能高，但是读取的时候要根据序号遍历到对应的节点获取，所以读取性能低；
3、HashMap的实现原理
entry数组+链表 的实现方式；根据一定的算法，将数据散列的分配到数组里，数组中的节点采用链表的方式存储多条数据；
image.png
/* ---------------- Fields -------------- */
transient Node<K,V>[] table;
transient int size; // put进去多少数据 ；size <= table.length
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
怎么根据hash值找到对应的entry
将对象的key的哈希值与entry数组的长度-1 进行逻辑与&运算，得到一个小于等于entry数组的长度-1的数字
注意这里数组的长度一定是一个2的整数次幂的数，在初始化时传入一个非2的幂的数，jdk会转化为大于输入参数且最近的2的整数次幂的数，以保证在进行与运算时，得到的数均匀分布
put插入数据的过程
首先获取key的hashcode，找到对应的entry，如果entry为空，则直接给entry赋值，如果entry不为空，那么遍历链表，如果对应的key已经存在于链表上，则直接覆盖，否则在链表最末端加上新的值；
在这之后会有个扩容判断，如果当前size已经超过了阈值（默认entry数组的长度的0.75），则进行double扩容；
扩容的过程
新建一个容量是原来两倍的entry数组，然后对原来的entry数组中的元素进行遍历，重新根据hash值计算它应该在新数组的哪个位置上，然后进行放置；
然后将原来数组的数据逐个设置为null，使引用失效；
get获取数据的过程
根据key的hashcode找到对应的entry，然后判断entry链表的第一个节点的key是不是相同，否则循环遍历整个链表直到找到为止！
为什么要用hash分组的方式
分组是为了利用数组的线性查找提高数据的查找效率（数组是连续的一块内存空间），根据key值的hascode可以快速定位到在哪个entry里，不然的话全部遍历时间复杂度为O(n)
为什么entry里的数据要用链表的方式
链表的好处就是利用链表的寻址修改，增删快
为什么hashmap线程不安全
- put的时候，A线程已经定位到了要插入的链表位置，这个时候B在同样的位置先执行了插入操作，但是A是不知道的，A继续执行插入就会覆盖调B的数据；
- 多线程resize时可能出现死循环，在链表从老的数组拷贝到新数组时，可能出现链表循环引用的问题，导致死循环；
jdk1.8修复了此问题：用 head 和 tail 来保证链表的顺序和之前一样，这样就不会产生循环引用
引用
JDK 1.8对hashMap的改动
链表引入红黑树，修复多线程resize死循环问题
在给链表追加数据的时候，如果量表长度超过阈值（8），则就把链表转换为红黑树
4、ConcurrentHashMap原理：
对value 加上 volatile、读取不加锁、
1.7：分段锁，segment 继承自ReentrantLock，segment结构和hashmap类似；获取锁会从自旋锁升级为阻塞锁
1.8：和1.8的hashmap基本一样
不同点：数据结构变化、ReentrantLock 改为了 synchronized、红黑树
put时，根据key定位到node，如果node为空，则cas自旋插入；否则synchronized在链表末尾插入，链表长度超过8转换为红黑树
5、HashSet和HashMap
HashSet其实就是HashMap实现的，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
6、LinkedHashMap 和 HashMap
- LinkedHashMap extends HashMap
- LinkedHashMap采用双向链表+散列表的结构来保存数据，保证节点的有序性（hashmap只是用链表来解决哈希冲突）；
网友评论