linkedhashmap的实现原理,linkedhashmap数据结构
一、摘要
在集合系列的第一章中，我们了解到Map的实现类包括HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。
如何解决写爬虫IP受阻的问题？立即使用。
本文主要从数据结构和算法层面讨论LinkedHashMap的实现。
（推荐学习：Java视频教程）
二、简介
LinkedHashMap继承了HashMap，允许您放入具有空键的元素和插入具有空值的元素。从名字可以看出，这个容器是LinkedList LinkedHashMap的混合体，也就是说，它同时满足HashMap和LinkedList的一些特性，可以看作是一个链表增强的HashMap。
打开LinkedHashMap源代码，可以看到三个主要的核心属性：
公共类LinkedHashMapK，V
扩展散列表
实现MapK，V{
/* *双向链表的头节点*/
瞬态LinkedHashMap。EntryK，V头；
/* *双向链表的尾节点*/
瞬态LinkedHashMap。EntryK，V尾；
/**
* 1.如果accessOrder为true，则被访问的元素将被放置在链表的后面，放置的顺序就是访问的顺序。
* 2.如果accessOrder为false，则按照插入顺序遍历它。
*/
最终布尔访问命令；
}LinkedHashMap在初始化阶段默认按插入顺序遍历。
public LinkedHashMap() {
super()；
accessOrder=false
}LinkedHashMap使用与HashMap相同的哈希算法，但区别在于它重新定义了数组中存储的条目。该条目不仅保存了当前对象的引用，还保存了前一个元素和后一个元素的引用，从而形成了基于哈希表的双向链表。
源代码如下：
静态类EntryK，V扩展HashMap。NodeK，V {
//before指链表的前节点，after指链表的后节点。
EntryK，V在前，V在后；
Entry(int hash，K key，V value，NodeK，V next) {
super(hash，key，value，next)；
}
}
可以直观的看到，插入双向链表头的数据就是链表的入口，迭代器从链表头遍历到链表尾。
这种结构除了保持迭代日历的顺序外，还有一个好处：在迭代LinkedHashMap时，不需要像HashMap一样遍历整个表，只需要直接遍历表头指向的双向链表，也就是说LinkedHashMap的迭代时间只与条目数有关，而与表的大小无关。
三、常用方法介绍
3.1、get方法
get方法根据指定的键值返回相应的值。这个方法的流程与HashMap.get()方法的流程几乎完全相同。默认情况下，它按照插入的顺序被遍历。
public V get(对象键){
NodeK，V e；
if ((e=getNode(hash(key)，key))==null)
返回null
if(辅助指令)
afterNodeAccess(e)；
返回e.value
}如果accessOrder为true，则被访问的元素将被放置在链表的后面，放置的顺序就是访问的顺序。
void afterNodeAccess(NodeK，V e) { //将节点移到最后
LinkedHashMap。EntryK，V last
if (accessOrder (last=tail)！=e) {
LinkedHashMap。EntryK，V p=
(LinkedHashMap。EntryK，V)e，b=p.before，a=p.after
p.after=null
if (b==null)
head=a；
其他
b . after=a；
如果(a！=空)
a . before=b；
其他
last=b；
if (last==null)
head=p；
否则{
p.before=last
last . after=p；
}
尾巴=p；
modCount
}
}测试案例：
公共静态void main(String[] args) {
//accessOrder默认为false
MapString，String accessOrderFalse=new linked hashmap()；
accessOrderFalse.put(1 ， 1 )；
accessOrderFalse.put(2 ， 2 )；
accessOrderFalse.put(3 ， 3 )；
accessOrderFalse.put(4 ， 4 )；
系统。出去。println( acessOrderFalse: accessorderfalse。tostring())；
//accessOrder设置为真实的
MapString，String accessOrderTrue=新链接hashmap(16，0.75f，true)；
accessOrderTrue.put(1 ， 1 )；
accessOrderTrue.put(2 ， 2 )；
accessOrderTrue.put(3 ， 3 )；
accessOrderTrue.put(4 ， 4 )；
accessordertrue。get( 2 )；//获取键2
accessordertrue。get( 3 )；//获取键3
系统。出去。println( accessOrderTrue: accessOrderTrue。tostring())；
}输出结果：
acessOrderFalse:{1=1，2=2，3=3，4=4}
accessOrderTrue:{1=1，4=4，2=2，3=3}3.2、put方法
放(K键，五值)方法是将指定的键，值对添加到地图里。该方法首先会调用模拟的插入方法，同样对地图做一次查找，看是否包含该元素，如果已经包含则直接返回，查找过程类似于获取()方法；如果没有找到，将元素插入集合。
/* *散列表中实现*/
公共V put(K键，五值){
返回putVal(hash(key)，key，value，false，true)；
}
final V putVal(int hash，K key，V value，boolean onlyIfAbsent，
布尔逐出){
NodeK，V[]tab；NodeK，V p；int n，I；
if((tab=table)==null (n=tab。长度)==0)
n=(tab=resize()).长度；
if ((p=tab[i=(n - 1) hash])==null)
tab[i]=newNode(hash，key，value，null)；
否则{
NodeK，V e；负担
if (p.hash==hash
((k=p.key)==key (key！=null key.equals(k))))
e=p；
else if(p TreeNode的实例)
e=((TreeNodeK，V)p).putTreeVal(this，tab，hash，key，value)；
否则{
for(int bin count=0；binCount) {
if ((e=p.next)==null) {
p.next=newNode(hash，key，value，null)；
第一个if(bin count=tree ify _ THRESHOLD-1)//-1
treeifyBin(tab，hash)；
打破；
}
如果（例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
打破；
p=e；
}
}
如果(e！=null) { //键的现有映射
旧值=电子值
如果(!onlyIfAbsent oldValue==null)
e .值=值；
afterNodeAccess(e)；
返回旧值；
}
}
modCount
如果(大小阈值)
resize()；
afterNodeInsertion(驱逐);
返回空
}LinkedHashMap中覆写的方法
//LinkedHashMap中覆写
NodeK，V newNode(int hash，K key，V value，NodeK，V e) {
LinkedHashMap .EntryK，V p=
新LinkedHashMap .EntryK，V(hash，key，value，e)；
//将进入接在双向链表的尾部
linkNodeLast(p)；
返回p；
}
private void linkNodeLast(链接的hashmap .EntryK，副总裁){
LinkedHashMap .EntryK，V last=tail
尾巴=p；
//最后为空，表明链表还未建立
if (last==null)
head=p；
否则{
//将新节点p接在链表尾部
前p=后
最后。after=p；
}
}
3.3、remove方法
移除（对象关键点)的作用是删除键值对应的条目，该方法实现逻辑主要以模拟为主，首先找到键值对应的条目，然后删除该条目（修改链表的相应引用),查找过程跟获取()方法类似，最后会调用LinkedHashMap中覆写的方法，将其删除！
/* *散列表中实现*/
公共V删除(对象键){
NodeK，V e；
return (e=removeNode(hash(key)，key，null，false，true))==null？
null:e . value；
}
最终NodeK，V removeNode(int hash，Object key，Object value
布尔匹配值，布尔可移动){
NodeK，V[]tab；NodeK，V p；int n，索引
if ((tab=table)！=null (n=tab.length) 0
(p=tab[index=(n - 1) hash])！=null) {
NodeK，V node=null，e；K kV v
if (p.hash==hash
((k=p.key)==key (key！=null key.equals(k))))
node=p；
else if ((e=p.next)！=null) {
TreeNode的实例){.}
否则{
//遍历单链表，找到要删除的节点，赋给节点变量
做{
如果(例如，哈希==哈希
((k=e.key)==key
(关键！=null key.equals(k)))) {
node=e；
打破；
}
p=e；
} while ((e=e.next)！=null)；
}
}
如果(节点！=null(！match value (v=node . value)==value
(值！=空值. equals(v)))) {
TreeNode的节点实例){.}
//从单链表中删除要删除的节点
else if (node==p)
tab[index]=node . next；
其他
p . next=node . next；
modCount
-尺寸；
after node removal(node)；//调用删除回调方法进行后续操作
返回节点；
}
}
返回null
afterNodeRemoval方法在}LinkedHashMap中被重写
void afterNodeRemoval(NodeK，V e) { //unlink
LinkedHashMap。EntryK，V p=
(LinkedHashMap。EntryK，V)e，b=p.before，a=p.after
//清空P节点的前置和后续引用。
p . before=p . after=null；
//b为空，表示P为头节点。
if (b==null)
head=a；
其他
b . after=a；
//a为空，表示P为尾节点
if (a==null)
尾巴=b；
其他
a . before=b；
}
四、总结
LinkedHashMap继承自HashMap，大部分功能和特性基本相同。两者唯一的区别是LinkedHashMap在HashMap的基础上以双向链表的形式连接所有条目，从而保证元素的迭代顺序与插入顺序相同。
体的一部分和HashMap完全一样，只是头指向双向链表的头，尾指向双向链表的尾，双向链表默认的迭代顺序是条目的插入顺序。
本文来自我们，java教程专栏，欢迎学习！以上是对LinkedHashMap (graphic)细节的简单分析。请多关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。