vr技术对网站建设有哪些影响,创意设计与制作,西安官网seo公司,北京网站设计公司wyhseo1.Map的存储特点 在Map这个结构中#xff0c;数据是以键值对#xff08;key-value#xff09;的形式进行存储的#xff0c;每一个存储进map的数据都是一一对应的。 创建一个Map结构可以使用new HashMap()以及new TreeMap()两种方式#xff0c;两者之间的区别是#xff1a…1.Map的存储特点 在Map这个结构中数据是以键值对key-value的形式进行存储的每一个存储进map的数据都是一一对应的。 创建一个Map结构可以使用new HashMap()以及new TreeMap()两种方式两者之间的区别是TreeMap是支持 排序的。 2.HashMap的底层存储方式 总结: 1. 用hashMap存储数据(key,value)的时候使用put方法 2. put方法会调用putVal方法,把hash(hey)和当前的keyvalue作为参数传进来 3. 判断数组是否为空即判断是否是第一次添加数据,如果是的话会先调用resize方法扩容 4. 之后,根据当前key的hash值找到它在数组中的下标 (怎么算的? index (n - 1) hash)判断当前下标位置是 否已经存在元素 5. 如果不存在直接把key、value包装成Node节点作为链表头存入数组 6. 如果存在分为三种情况 1. 比较一下已有数据和存入数据 如果hash值等于传过来的hash并且他们的key值也相等 最后会把 value的值覆盖处理 2. 上一步不相等就判断一下当前是不是红黑树结构是则调用putTreeVal()把它加入到红黑树 3. 既不相等也不是红黑树结构说明是普通链表结构遍历这个链表将数据存到链表尾部 1. 在遍历过程中如果是最后一个节点则插入新节点 newNode(hash, key, value, null) 2. 如果链表长度超过了8则转化为红黑树 treeifyBin(tab, hash)3. 如果遍历的时候遇到了相同的key 把value的值覆盖处理 7. 如果当前数组中的元素个数超过阈值则扩容 resize(); 8. putVal方法 没修改value就返回NULL 修改了就返回旧值之前的value 3.什么是hash碰撞 Hash Collision 就是我们说的 Hash 碰撞或者 Hash 冲突。 这个其实也非常好理解就是 2 个输入不同的数据经过 Hash 算法后得到的 Hash 值是一样的。 在HashMap的查询和添加过程中绕不过去的是计算元素在数组的位置indexkey的HashCode作为这个计算的 基础。计算后的Hash值存在相同的情况hash与长度取余的结果也有相同的情况这个时候运算结果相同的两个 对象就需要存储到同一个链表中这就是HashMap中的Hash碰撞。 4.如何解决hash碰撞 1.开放地址方法 1线性探测 按顺序决定值时如果某数据的值已经存在则在原来值的基础上往后加一个单位直至不发生哈希冲突。 就是在 此空间不足时直接放入此空间的后一个空的空间 2再平方探测 按顺序决定值时如果某数据的值已经存在则在原来值的基础上先加1的平方个单位若仍然存在则减1的平方个 单位。随之是2的平方3的平方等等。直至不发生哈希冲突。 要注意平方不能超过容量的值 Size16的时候找备 选的单元只能取i1,2,3也就是距离冲突单元1,4,9个单位的位置了。 3伪随机探测 按顺序决定值时如果某数据已经存在通过随机函数随机生成一个数在原来值的基础上加上随机数直至不发 生哈希冲突。 2.链式地址法HashMap的哈希冲突解决方法 对于相同的值使用链表进行连接。使用数组存储每一个链表。 就是hashmap的底层原理 数组链表 就是没有 红黑树 补充在JDK1.8中HashMap通过链式寻址法以其红黑树来解决哈希冲突的其中红黑树是为了优化哈希表的链表 过长 导致遍历时间复杂度增加的问题。当链表长度大于8并且哈希表的容量大于64,再向链表中添加元素,会转化为 红黑树。优点1拉链法处理冲突简单且无堆积现象即非同义词决不会发生冲突因此平均查找长度较2 由于拉链法中各链表上的结点空间是动态申请的故它更适合于造表前无法确定表长的情况 3开放定址法为 减少冲突要求装填因子α较小故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1且结点较大时拉 链法中增加的指针域可忽略不计因此节省空间 4在用拉链法构造的散列表中删除结点的操作易于实现。 只要简单地删去链表上相应的结点即可。 缺点1 指针占用较大空间时会造成空间浪费若空间用于增大散列表规模进而提高开放地址法的效率。 3.建立公共溢出区 建立公共溢出区存储所有哈希冲突的数据 4.再哈希法 对于冲突的哈希值再次进行哈希处理直至没有哈希冲突。 5.如何解决并发 HashMap的线程不安全主要体现在下面两个方面 1.在JDK1.7中当并发执行扩容操作时会造成环形链和数据丢失的情况。 2.在JDK1.8中在并发执行put操作时会 发生数据覆盖的情况。 1、if((p tab[i (n -1) hash])null)// 1、此处线程不安全——用来判定索引位置是否 hash碰撞比如两个线程A、B都在进行put操作并且hash函数计算出的插入下标是相同的当线程A执行完第六 行代码后由于时间片耗尽导致被挂起而线程B得到时间片后在该下标处插入了元素完成了正常的插入然后线 程A获得时间片由于之前已经进行了hash碰撞的判断所有此时不会再进行判断而是直接进行插入这就导致 了线程B插入的数据被线程A覆盖了从而线程不安全。 2、if (size threshold)中的size同样还是线程A、B这两个线程同时进行put操作时假设当前HashMap 的zise大小为10当线程A执行到此行代码时从主内存中获得size的值为10后准备进行1操作但是由于时间片 耗尽只好让出CPU线程B快乐的拿到CPU还是从主内存中拿到size的值10进行1操作完成了put操作并将 size11写回主内存然后线程A再次拿到CPU并继续执行(此时size的值仍为10)当执行完put操作后还是将 size11写回内存此时线程A、B都执行了一次put操作但是size的值只增加了1所有说还是由于数据覆盖又导 致了线程不安全。 解决方法 1.Hashtable HashTable为了实现多线程安全在几乎所有的方法上都加上了synchronized锁锁的是类的实例,也就是整个 map结构当一个线程访 问 Hashtable 的同步方法时其他线程如果也要访问同步方法会被阻塞住。 2.Collections.synchronizedMap(一般不用) 缺点:从锁的角度来看基本上是锁住了尽可能大的代码块.性能会比较 差 3.ConcurrentHashMap常用 JDK 1.7 中采用分段锁的机制实现并发的更新操作底层采用数组链表的 存储结构包括两个核心静态内部类 Segment 和 HashEntry。 ①、Segment 继承 ReentrantLock重入锁 用 来充当锁的角色每个 Segment 对象守护每个散列映射表的若干个桶 ②、HashEntry 用来封装映射表的键-值 对 ③、每个桶是由若干个 HashEntry 对象链接起来的链表 分段锁Segment数组中一个Segment对象就是一 把锁,对应一个HashEntry数组,该数组中的数据同步依赖于同一把锁,不同HashEntry数组的读写互不干扰 JDK 1.8中抛弃了原有的 Segment 分段锁来保证采用Node CAS Synchronized来保证并发安全性。取消类 Segment直接用table 数组存储键值对当 Node对象组成的链表长度超过TREEIFY_THRESHOLD 时链表转换 为红黑树提升性能。底层变更为数组 链表 红黑树。 CAS性能很高但synchronized之前一直都是重量级的 锁jdk1.8 引入了synchronized采用锁升级的方式。
