济南网站建设哪家便宜,徐州云网信息技术有限公司,做电商一件代发的网站,宁波妇科专家排名首先回答HashMap的底层原理?
HashMap是数组链表组成。数字组是HashMap的主体#xff0c;链表则是主要为了解决哈希冲突而存在的。要将key 存储到#xff08;put#xff09;HashMap中#xff0c;key类型实现必须计算hashcode方法#xff0c;默认这个方法是对象的地址。接…首先回答HashMap的底层原理?
HashMap是数组链表组成。数字组是HashMap的主体链表则是主要为了解决哈希冲突而存在的。要将key 存储到putHashMap中key类型实现必须计算hashcode方法默认这个方法是对象的地址。接着还必须要覆盖对应的equals方法。如果对于插入的操作的来说那么对于添加操作其时间复杂度依然为O(1)因为最新的Entry会插入链表头部。对于查找的来说话就需要遍历 链表然后key的equals方法去逐一对比查找。但是对应的key可以为空。所以HashMap对应的链表越少性能才越好。 如何解决冲突?
1链式寻址法这是一种常见的方法简单理解就是把存在Hash冲突的key以单向链表来进行存储。
2开放定址法也称线性探测法就是从发生冲突的那个位置开始按照一定次序从Hash表找到一个空闲位置然后把发生冲突的元素存入到这个位置而在java中ThreadLocal就用到了线性探测法来解决Hash冲突
3、再Hash法就是通过某个Hash函数计算的key存在冲突的时候再用另外一个Hash函数对这个可以进行Hash一直运算直到不再产生冲突为止这种方式会增加计算的一个时间,性能上呢会有一些影响
HashMap在JDK1.8版本中是通过链式寻址法以及红黑树来解决Hash冲突的问题其中红黑树是为了优化Hash表的链表过长导致时间复杂度增加的问题当链表长度大于等于8并且Hash表的容量大于64的时候再向链表添加元素就会触发链表向红黑树的一个转化。红黑树 是一种自平衡的二叉搜索树
hashCode方法的作用它返回的就是根据对象的内存地址换算出的一个值。这样一来当 集合要添加新的元素时先调用这个元素的hashCode方法就一下子能定位到它应该放置的物理 位置上。如果这个位置上没有元素它就可以直接存储在这个位置上不用再进行任何比较了如 果这个位置上已经有元素了就调用它的equals方法与新元素进行比较相同的话就不存了不相 同就散列其它的地址。这样一来实际调用equals方法的次数就大大降低了几乎只需要一两次。
HashTable的底层原理?
hashtable是通过数组与链表来储存数据但是它与hashmap不同的是它的key不能为空同时其为线程安全的。虽然hashmap是线程安全的不过其保证线程安全的手段低效它只是简单的对每个方法加上synchronized悲观锁相当于就是对底层的数组加上一把大锁。这种方式出现锁冲突的概率非常大因为不管是读还是写都需要去竞争同一把锁所以其效率低下。
再次回答CurrentHashMap的底层原理
ConcurrentHashMap与HashMap等的区别
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap相对而言ConcurrentHashMap只是增加了同步的操作来控制并发从JDK1.7版本的ReentrantLockSegmentHashEntry到JDK1.8版本中synchronizedCASHashEntry红黑树。
1.数据结构取消了Segment分段锁的数据结构取而代之的是数组链表红黑树的结构。 2.保证线程安全机制JDK1.7采用segment的分段锁机制实现线程安全其中segment继承自ReentrantLock。JDK1.8采用CASSynchronized保证线程安全。 3.锁的粒度原来是对需要进行数据操作的Segment加锁现调整为对每个数组元素加锁Node。 4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时会将链表转化为红黑树进行存储。 5.查询时间复杂度从原来的遍历链表O(n)变成遍历红黑树O(logN)。
CurrentHashMap是如何保证线程安全。 这里的链表长度 如果大于8 会自动 转换为 红黑树。这里的数据结构和jdk1.8的HashMap数据结构大致相同。只是在HashMap的基础上增加线程安全的操作。
final V putVal(K key, V value, boolean onlyIfAbsent) {if (key null || value null) throw new NullPointerException(); // 键或值为空抛出异常// 键的hash值经过计算获得hash值这里的 hash 计算多了一步 HASH_BITSHASH_BITS 是 0x7fffffff该步是为了消除最高位上的负符号 hash的负在ConcurrentHashMap中有特殊意义表示在扩容或者是树结点int hash spread(key.hashCode());int binCount 0;for (NodeK,V[] tab table;) { // 无限循环NodeK,V f; int n, i, fh;if (tab null || (n tab.length) 0) // 表为空或者表的长度为0// 初始化表tab initTable();else if ((f tabAt(tab, i (n - 1) hash)) null) { // 表不为空并且表的长度大于0并且该桶不为空if (casTabAt(tab, i, null,new NodeK,V(hash, key, value, null))) // 比较并且交换值如tab的第i项为空则用新生成的node替换break; // no lock when adding to empty bin}else if ((fh f.hash) MOVED) // 该结点的hash值为MOVED// 进行结点的转移在扩容的过程中tab helpTransfer(tab, f);else {V oldVal null;synchronized (f) { // 加锁同步if (tabAt(tab, i) f) { // 找到table表下标为i的结点if (fh 0) { // 该table表中该结点的hash值大于0// binCount赋值为1binCount 1;for (NodeK,V e f;; binCount) { // 无限循环K ek;if (e.hash hash ((ek e.key) key ||(ek ! null key.equals(ek)))) { // 结点的hash值相等并且key也相等// 保存该结点的val值oldVal e.val;if (!onlyIfAbsent) // 进行判断// 将指定的value保存至结点即进行了结点值的更新e.val value;break;}// 保存当前结点NodeK,V pred e;if ((e e.next) null) { // 当前结点的下一个结点为空即为最后一个结点// 新生一个结点并且赋值给next域pred.next new NodeK,V(hash, key,value, null);// 退出循环break;}}}else if (f instanceof TreeBin) { // 结点为红黑树结点类型NodeK,V p;// binCount赋值为2binCount 2;if ((p ((TreeBinK,V)f).putTreeVal(hash, key,value)) ! null) { // 将hash、key、value放入红黑树// 保存结点的valoldVal p.val;if (!onlyIfAbsent) // 判断// 赋值结点value值p.val value;}}}}if (binCount ! 0) { // binCount不为0if (binCount TREEIFY_THRESHOLD) // 如果binCount大于等于转化为红黑树的阈值// 进行转化treeifyBin(tab, i);if (oldVal ! null) // 旧值不为空// 返回旧值return oldVal;break;}}}// 增加binCount的数量addCount(1L, binCount);return null;
}
JDK1.8的CurrentHashMap与 JDK1.7的CurrentHashMap的对比
1抛弃了JDK1.7中的原有的Segment中分段锁。而是采用了CASsynchronized来保证并发性。
2将 JDK 1.7 中存放数据的 HashEntry 改为 Node但作用是相同的。
我们看下对应的put方法思想: 主要是6步法思想:通过cas将新生成node节点插入table若对应的node节点已经存在则将sychronized锁住哈希桶进行更新或者插入尾巴的下一个节点[CAS补充一下思想:CAS 操作包含三个操作数 —— 内存位置V、预期原值A和新值(B)。 如果内存位置的值与预期原值相匹配那么处理器会自动将该位置值更新为新值 。否则处理器不做任何操作。] 1:如果keynull或者value null,那么对应的对应的异常 2:计算此key的hash值,然后就进入自旋自旋确保数据可以插入。首先判断对应的table表为空或者长度为0若为空则初始化table表。 3根据 key 的 hash 值取出 table 表中的结点元素若取出的结点为空该桶为空则使用CAS将对应的key,value,hash放入对应的桶中。就是上面图片中对于table的长度计算对应还有没有空有空的话就生成对应的Node节点。 4若该结点的的 hash 值为 MOVED-1则对该桶中的结点进行转移。节点转移就是扩容的过程中。 5: 对于桶中的第一个节点进行加锁然后进行遍历。根据桶中的hash值和key值 与本次添加key的值和根据key计算的hash 进行逐一比对。若出现相等的情况则 根据对应的value值进行更新。否则就生成一个节点则赋值给最后一个节点的下一个节点。
6若binCount的值 达到一个 转换为红黑树的阈值。则转换为 红黑树。
ConcurrentHashmap 不支持 key 或者 value 为 null 的原因
1ConcurrentHashmap 和 Hashtable 都是支持并发的当通过 get(k) 获取对应的 value 时如果获取到的是 null 时无法判断是 put(k,v) 的时候 value 为 null还是这个 key 从来没有做过映射。 2HashMap 是非并发的可以通过 contains(key) 来做这个判断。 3支持并发的 Map 在调用 m.contains(key) 和 m.get(key) 时m 可能已经发生了更改。 因此 ConcurrentHashmap 和 Hashtable 都不支持 key 或者 value 为 null。
