JDK1.7:
底层数据结构:数组(sgement)、数组(HashEntry)、链表(HashEntry节点)
两个主要的内部类:
class Segment内部类,继承ReentrantLock,有一个HashEntry数组,用来存储链表头结点
class HashEntry 定义的节点,里面存储的数据和下一个节点
主要方法:
get()方法:
1、第一次哈希 找到 对应的Segment段,调用Segment中的get方法
2、再次哈希找到对应的链表,
3、最后在链表中查找。
put()方法:
1、首先确定段的位置,调用Segment中的put方法:
2、加锁
3、检查当前Segment数组中包含的HashEntry节点的个数,如果超过阈值就重新hash
4、然后再次hash确定放的链表。
5、在对应的链表中查找是否相同节点,如果有直接覆盖,如果没有将其放置链表尾部
重哈希方式 :重点:
重哈希的方式 :只是对 Segments对象中的Hashentry数组进行重哈希
线程安全:
分段锁 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。
JDK1.8:
底层数据结构:Synchronized、CAS、Node
Node数组使用来存放树或者链表的头结点,当一个链表中的数量到达一个数目时,会使查询速率降低,所以到达一定阈值时,会将一个链表转换为一个红黑二叉树,通告查询的速率。
线程安全方式:
使用的是优化的synchronized 关键字同步代码块 和 cas操作了维护并发。 通过使用Synchroized关键字来同步代码块,而且只是在put方法中加锁,在get方法中没有加锁 在加锁时是使用头结点作为同步锁对象。
**效率:**简化结构,put和get不用二次哈希,一把锁只锁住一个链表或者一棵树,并发效率更加提升。
主要属性:
主要方法:
1、构造方法:
构造方法并没有直接new出来一个Node的数组,只是检查数值之后确定了容量大小。
2、put方法:
步骤:
检查Key或者Value是否为null,
得到Kye的hash值
如果Node数组是空的,此时才初始化 initTable(),
如果找的对应的下标的位置为空,直接new一个Node节点并放入, break;
如果对应头结点不为空, 进入同步代码块
判断此头结点的hash值,是否大于零,大于零则说明是链表的头结点在链表中寻找,如果有相同hash值并且key相同,就直接覆盖,返回旧值 结束如果没有则就直接放置在链表的尾部
此头节点的Hash值小于零,则说明此节点是红黑二叉树的根节点
调用树的添加元素方法,判断当前数组是否要转变为红黑树
3、get 方法
首先获取到Key的hash值,
然后找到对应的数组下标处的元素
如果次元素是我们要找的,直接返回,
如果次元素是null 返回null
如果Key的值< 0 ,说明是红黑树,
4、扩容:tryPresize()
容后数组容量为原来的 2 倍。
扩容是的线程安全
- 复制槽节点时,会把原数组的当前槽节点锁住,避免并发产生的线程安全问题;
- 拷贝成功之后,会把原数组的槽点设置成转移节点,这样如果有数据需要 put 到该节点时,发现该槽点是转移节点,帮助扩容,直到扩容成功之后,才会重新 put,可以参考 put 方法中的 helpTransfer 方法;
- 等扩容拷贝都完成之后,直接把新数组的值赋值给数组容器