arrayList和linkedList
arrayList是数组，默认10个大小 然后满了之后1.5倍扩容。
linkedList是双向链表。
CopyOnWriteArrayList
改的时候加个r锁，然后new 新的数组->system.arraycopy复制到新的数组里，方法来扩容或者缩短。
stringbuffer，stringbuilder，也是system.arraycopy~但是这里没有创建新数组，而是修改了原数组。
https://www.jianshu.com/p/a0582f2c5ec8
hashMap
hashMap 数组+链表来实现 默认16 扩容 *2。
hashSet
hashMap包一层，添加就是把值当做key加到hashMap里，方法都是调用hashMap的。
为啥是 16
因为 确定key 数组下标的是 (n-1) & hash。
的算法 如果太大 浪费初始的空间 16 对应 n-1 的二进制是 1111。
为啥hash 不用hashcode?
因为hashcode是int 对应2进制32。hash的运算是h^(h>>>16)，32位右移16和原来的32取异或，等同前16位和后16位取异或。
就是要尽量和每一位数据都有关系，这样减少碰撞。
为啥0.75?
这就设计到 一个阈值的问题了 太小可能导致内存浪费 太大链表太长 影响查询效率。
位运算:
与（&） 非（~） 或（|） 异或( ^ 相同为0 否则为1)
线程安全问题
1.并发put，key丢失。并发到同一槽里。
2.扩容时，getkey为null。
- jdk7扩容+头插，形成环。
jdk1.8
hashmap
- 懒加载，
put才会初始化数组。 - 链表，86转换红黑。
-
hash算法变了。 - 之前头插，现在尾插。 头插在并发扩容的时候，会有形成环的bug。
concurrentHashMap
- segment+reentrantLock 16个分段 最多16个锁。
- node+cas+s锁。reentrantlock改为s锁 1.8s锁 性能和r锁不分上下，使用简单。扩容，锁数量会变得不固定。
- 链表
cas操作：从0到1。
s锁操作：从1到多。
大于8红黑树 小于6链表。
linkedHashMap
- 按照插入的时间进行遍历。
- 加一层双向链表。
treeHashMap
- 按照一定规则进行排序。
- 红黑树结构实现排序。
网友评论