程序笔记
发布时间：2022-07-12 发布网站：大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了HashMap、LinkedHashMap，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
HashMap和LinkedHashMap的区别
java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap.
Map主要用于存储健值对，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复。
Hashmap 是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。 HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用COncurrentHashMap。
Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。
LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。
一般情况下，我们用的最多的是HashMap,在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.
Jdk1.7 数组+链表
Jdk1.8 数组+链表/红黑树（二分查找）
一个桶上链表长度为8时，进行树化。 树化的时候，会判断当前的数组长度是否小于64，如果小于，则不进行树化，而是选择进行一次扩容，因为扩容的时候会使哈希表长度增加，hash值会重新计算，将重新打乱当前的元素排列，分配到新的空间上，这样也避免了链表过长。
初始容量：16
负载因子：0.75
链表：新增删除仅需处理结点间的引用即可，时间复杂度：O
(1)，查找操作需要遍历链表逐一进行比对。复杂度O(n)；二叉树：对平衡有序二叉树，对其进行插入，查找，删除等操作，平均复杂度都是O(logn)。
hash冲突：进行数据存储时，我们通过对关键字hash时得到的地进行址已经存储了数据，这时就
会出现hash冲突。解决方法有很多种，
hashmap采用了链地址法，也就是数组+链表的方式。
hashmap构造器中没有为数组thashmap主干是Entry数组。Entry是hashmap的基本组成单元，每一个entry包含一个key-value键值对。（数组是hashmap的主体，链表为了解决hash冲突而存在的。
table分配内存空间，而是在执行put操作的时候才能真正构建table数组。
当发生hash冲突并且size大于阈
值的时候，需要进行扩容，扩容时新建一个长度为之前数组2倍的新数组，然后将当前entry数组中元素全部传输过去。
Jdk1.7put()方法：
1.判断table数组是否为空，若为空进行初始化table数组。
2.判断key值是否为null，将null是作为key存进去。
3.若key不为空，通过key计算出数组下标，判断table[i]是否为空。
4.若是不为空通过链表循环，判断在链表中是否存在与该key相等，若是存在，直接将value替换成新的value。若是table[i]为空或者链表中不存在与之相同的key，就addEntry(hash, key, value, i)新增一个节点。
Jdk1.8 put()方
1、hash(key)，取key的hashcode进行高位运算，返回hash值
2、如果hash数组为空，直接resize()
3、对hash进行取模运算计算，得到key-value
在数组中的存储位置i
（1）如果table[i] == null，直接插入Node<key,value>
（2）如果table[i]
!= null，判断是否为红黑树p instanceof TreeNode。
（3）如果是红黑树，则判断TreeNode是否已存在，如果存在则直接返回oldnode并更新；不存在则直接插入红黑树，++size，超出threshold容量就扩容
（4）如果是链表，则判断Node是否已存在，如果存在则直接返回oldnode并更新；不存在则直接插入链表尾部，判断链表长度，如果大于8则转为红黑树存储，++size。
hashMap并不是在链表元素个数大于8就一定会转换为红黑树，而是先
考虑扩容，扩容达到默认限制后才转换。
hashMap的红黑树不一定小于6的时候才会转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。（remove()）
Q1:为何HashMap的数组长度一定是2的次幂？
1.为了数据的均匀分布，减少哈希碰撞。因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。(PS:其实若不
考虑效率，求余也可以就不用位运算了也不用长度必需为2的幂次)
2.输入数据若不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字
Q2:hashmap的特性？
1.存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
2.非同步，线程不安全。
3.底层是hash表，不保证有序。
Q3:底层原理？
jdk8后采用数组+链表/红黑树的数据机构。通过put和get存储或获取对象。put方法传递键和值时，先对键计算hashcode值得到
它在桶数组中的位置来存储entry对象。当获取对象时，通过get获取桶的位置，再通过键对象的equals()方法找到正确的键值队，
然后返回值对象。
Q4:当两个对象的hashCode相等时会怎么样？
会产生哈希碰撞，若key值相同则替换旧值，不然链接到链表后面，链表长度超过阙值8就转为红黑树存储。
Q5:如果两个键的hashcode相同，你如何获取值对象？
HashCode相同，通过equals比较内容获取值对象。
Q5：jdk1.8之前hashmap缺点？
以前是数组+链表，即使哈希函数取的再好，也很难达到百分百均匀分布。当Hashmap中有大量元素放在同一个桶，桶下有一条很长的链表，这时hashmap就像单链表，假如单链表有n个元素，遍历时间复杂度就是O(n)，完全失去了优势。
针对这种情况，jdk1.8增加了红黑树(查找时间复杂度O(logn）)。
Q6：HashMap的扩容机制是怎么样的？JDK7与JDK8有什么不同吗？
JDK 1.7的扩容条件是数组长度大于阈值且存在哈希冲突，而JDK 1.8扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时，源码中的体现如下所示：
Q7:聊一聊JDK 7的HashMap中的“死锁”是怎么回事？
首先JDK7采用的头插法，会有链表成环的问题，JDK8采用的尾插法，不会有循环链表的问题。
HashMap是线程不安全的，在HashMap的源码中并未对其操作进行同步执行，所以在并发访问的时候就
会出现线程安全的问题。
JDK 7死锁出现在高并发的时候，此时两个线程都将
对数据进行扩容，每次扩容的时候，会让链表翻转。
Q8:HashMap是线程安全的吗？为什么安全或者不安全？
不是线程安全的，比如会在扩容的时候产生循环链表；在put的时候会覆盖别的线程的值
Q9:HashMap、HashTable、ConcurrentHashMap的区别?
HashMap是线程不安全的，在jdk1.7高并发的时候，可能会在扩容的时候，产生循环链表，所以在高并发的时候，不去使用。
HashTable是一个线程安全的，采用的是synchronize的方式，关键字加在方法上，即对当前HashTable对象加锁，会导致所有的数据加上锁。
ConcurrentHashMap在JDK1.7的时候使用的是Segment分段锁的思想，将数据分成段，每个段都有个可重入锁，则多线程的时候不会影响到其他线程访问其他段的数据。
ConcurrentHashMap在JDK1.8的时候使用的是CAS+synchronized方式，抛弃了Segment分段锁的思想，CAS是一个乐观锁，则在不加锁情况下实现赋值，在当前节点为空的时候，会采用CAS的方式添加节点；而用synchronized而不用是可重入锁的原因
是因为官方对synchronized
做了很多优化。
Q10:谈谈你理解的 HashMap，讲讲其中的 get和put 过程?
put方法：
根据key计算哈希值，找到hash表对应的索引
然后判断是否出现的hash冲突，如果没有则直接插入，查看是否需要扩容
思路与上面一致，只是少了一个扩容和树化的过程
Q11:HashMap中的键值可以为Null吗？能简单说一下原理吗？
JDK两个版本都可以。JDK1.7和1.8本质都是JDK1.7出现hash冲突直接插入链表中即可
JDK1.8出现hash冲突，需要先判断当前是红黑树还是链表，对于链表可能会有一个树化的过程
get方法：去寻找Hash值为0的那个桶，然后如果key为null，则直接替换值
Q12:什么 HashMap 的加载因子是0.75？为什么是超过“8”才用红黑树？
加载因子是0.75主要跟数学上泊松分布有关系，选择的参数平均为0.5的泊松分布，计算出来当前加载因子是0.75，这更是空间与时间的一种选择折中。
而超过8才使用红黑树，源于该泊松分布计算出来的，一个节点哈希冲突8次的概率极为的小，几乎为不可能时间，这也是一次空间与时间的折中。
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
7: 0.00000094
8: 0.00000006
大佬总结
以上是大佬教程为你收集整理的HashMap、LinkedHashMap全部内容，希望文章能够帮你解决HashMap、LinkedHashMap所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
