目录
TreeMap分析
需求分析
哈希表
哈希冲突（Hash Collision）
JDK1.8的哈希冲突解决方案
哈希函数
如何生成key的哈希值
哈希计算的集中情况
TreeMap分析
时间复杂度（平均） 添加、删除、搜索：O(logn) 特点 Key 必须具备可比较性 元素的分布是有顺序的 在实际应用中，很多时候的需求 Map 中存储的元素不需要讲究顺序 Map 中的 Key 不需要具备可比较性 不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1) 那就是采取 哈希表 来实现 Map需求分析
需求： 1.设计一个写字楼通讯录，存放所有公司的通讯信息 2.座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value 3.添加、删除、搜索的时间复杂度要求是 O(1） 最简单的思路数据是如下图所示：
简单的代码思路是这样的：
存在的问题： 空间复杂度非常大 空间使用率极其低，非常浪费内存空间 其实数组 companies 就是一个哈希表，典型的【空间换时间】
哈希表
哈希表也叫做散列表（ hash 有“剁碎”的意思） 如何进行处理数据？？？put( "Jack" , 666); put( "Rose" , 777); put( "Kate" , 888); 添加的过程是如下所示： 添加、搜索、删除的流程都是类似的 1. 利用哈希函数生成 key 对应的 index【 O(1) 】 2. 根据 index 操作定位数组元素【 O(1) 】 解释 哈希表是【空间换时间】的典型应用 哈希函数，也叫做散列函数 哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array哈希冲突（Hash Collision）
哈希冲突也叫做哈希碰撞 2 个不同的 key，经过哈希函数计算出相同的结果 key1 ≠ key2 ，hash(key1) = hash(key2) ，如下所示：解决方式 1. 开放定址法（Open Addressing） 按照一定规则向其他地址探测，直到遇到空桶（这里的含义就是，已经知道03有东西了，然后去探测04之中有没有东西）. 2. 再哈希法（Re-Hashing）设计多个哈希函数（设计两套哈希算法） 3. 链地址法（Separate Chaining）比如通过链表将同一index的元素串起来（共用一个桶，但是通过链表的方式进行连接）JDK1.8的哈希冲突解决方案
说明 默认使用单向链表将元素串起来在添加元素时，可能会由单向链表转为红黑树来存储元素---比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时 当红黑树节点数量少到一定程度时，又会转为单向链表综上所述，JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突，示意图如下所示： 思考：这里为什么使用单链表？ 每次都是从头节点开始遍历 单向链表比双向链表少一个指针，可以节省内存空间哈希函数
哈希表中哈希函数的实现步骤： 先生成key的哈希值（必需是整数）再让key的哈希值跟数组的大小进行相关的运算，生成一个索引值 为了提高相应的效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（ 2 n ）】这里为什么要求是2^n-1,就是相当于是n个并排的1.一个值&全是1的家伙是不发生改变的.
良好的哈希函数 让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能
如何生成key的哈希值
key 的常见种类可能有 整数、浮点数、字符串、自定义对象 不同种类的 key，哈希值的生成方式不一样，但目标是一致的 ✓ 尽量让每个 key 的哈希值是唯一的 ✓ 尽量让 key 的所有信息参与运算 ◼ 在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null 情况一：整数整数值当做哈希值，比如说10的哈希值就是10。
情况二：浮点数 将存储的二进制格式转为整数值。上面的floatToIntBits(value)就是将上面的一段浮点数直接转换成为相应的哈希值. 情况三:Long和Double的哈希值------注意在java之中哈希值必须是int类型的.
计算哈希值最好是让所有的数据进行参与运算,是不可以只是选取其中的一点.
上面的>>>表示无符号右移.^表示的是异或运算.
例如:下面的运算过程就是高32位和低32位进行一个相互转换的过程.全部的64位都是参与运算的.
上面为什么要使用异或呢???如果要是使用别的运算,比如说&运算,运算量是比较小的,可能会出现问题,|运算同理.
情况四:字符串的哈希值
整数5489是如何进行计算的?
字符串是由若干个字符组成的
比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）
因此，jack 的哈希值可以表示为 j ∗ n3 + a ∗ n2 + c ∗ n1 + k ∗ n0，等价于 [ ( j ∗ n + a ) ∗ n + c ] ∗ n + k,上述的计算方式必然可以计算出来一个整数值的.但是这种方式存在大量的重复计算,比如说n的三次方.
在JDK中，乘数 n 为 31，为什么使用 31？
✓ 31是一个奇素数,31 * i = (i << 5 ) - i,这个i无论是换成是谁都是这个样子,所以我们直接是使用31算.
✓ 素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突✓ 最终选择31是经过观测分布结果后的选择
//拿取官方的hashCode值的方式String string = "jack";System.out.printf(string.hashCode());//这里的哈希值是如何进行计算的??//计算过程是这样的:hashCode = (( j * 31 + a ) * 31 + c ) * 31 + k//上面的过程是类似于这样的
//上面我们是使用charAt进行相应的字符的取出过程//在实际的hashCode之中,我们是使用的char val[] = value;//进行相应的字符的取出
哈希函数的计算
import .ProxySelector;import java.sql.SQLOutput;public class Main {public static void main(String[] args) {int a = 110;//这里可以直接使用对象类型,Intergerfloat b = 10.6f;Long c = Long.valueOf(1566389625);Double d = 10.9;String e = "rose";System.out.println(Integer.hashCode(a));System.out.println(Float.floatToIntBits(b));System.out.println(c.hashCode());System.out.println(d.hashCode());//是个负数System.out.println(e.hashCode());}}
结果如下所示:
注意:上面的第四个结果是负数,无论是正负数,只要是整数就可以.
自定义对象类型
这里的自定义对象进行使用的时候,我们是采取使用重写hashCode的方式进行操做,因为声明一个对象之后,hashCode默认的使用方式是直接调用Object的方式进行比较hashCode的值.相应的代码是如下所示(其实是比较容易理解的):
import .ProxySelector;import java.sql.SQLOutput;import java.util.HashMap;import java.util.Map;public class Main {public static void main(String[] args) {Person p1 = new Person(10,1.75f,"Yang");Person p2 = new Person(10,1.75f,"Yang");/*** 在不进行调用重写的方法的时候,下面的两个方法进行调用,得到的结果是不一样的,因为他们的内存地址是不一样的,导致计算出来的hashCode是不一样的*/System.out.println(p1.hashCode());//如果要是不掉用相应的一个重写的hashCode(),会出现相应的调用过程不同//直接调用,则调用的是相应的Object之中的hashCode()方法,跟内存的地址有关系System.out.println(p2.hashCode());/*Map<Object,Object> map = new HashMap<>();map.put(p1,"abc");map.put(p2,"bcd");*/}}
import java.util.Objects;public class Person {private int age;private float height;private String name;public Person(int age, float height, String name) {this.age = age;this.height = height;this.name = name;}/*** 为了规避直接声明出来的对象数组的不同,我们是使用进行调用上面的三个属性进行比较的方式进行*/@Overridepublic int hashCode() {Integer.hashCode(age);Float.hashCode(height);//name.hashCode(); //注意这里可能会出现null指针异常的情况int hashCode = Integer.hashCode(age);hashCode = hashCode * 31 + Float.hashCode(height);hashCode = hashCode * 31 + (name != null ? name.hashCode() : 0);return hashCode;}}
如果要是hashCode值太大,整型溢出怎么处理???------不用做处理,溢出就溢出嘛,目的就是算出一个整数就是可以的,只要最后算出的是一个整数就是可以的.
如果要是不重写的话,就是直接调用内存之中的hashCode方法进行使用.
equals
equals的作用,比如说桶这个地方放入了很多的元素,我们是使用链式存储,一旦是两个key是相同的就是会进行一个覆盖的过程,而equals就是进行比较这里的key是否相等的过程.
equals是比较值大小,但是==是比较内存地址是否相等的过程.我们一般是不使用内存地址是否相等的比较.
注意:不能够使用hashCode的大小作为比较相应的key值是否相等的标准,原因是可能会出现相应的hashCode碰撞的过程. 比如说:int i和float f甚至是String的hashCode的大小是相等的,就是两个不同性质的东西的hashCode值是相等的,为了规避这种现象的出现,采用重写equals.
hashCode值一样,索引必然是一样的,当然hashCode值不一样,索引也是可能会是一样.这里的key的不同不能够使用hashCode进行比较的过程,一定要使用equals进行比较两个对象是否相等.
@Overridepublic boolean equals(Object o) {//内存地址是一样的if(this == o) return true;// if(o == null || o.getClass() != getClass()) return false;if(o == null || !(o instanceof Person)) return false;/*直接进行比较成员变量直接获得相应的key是否相等*/Person person = (Person) o;return person.age == age&& person.height == height&& (person.name == null ? name == null : person.name.equals(name));}
具体过程的演示
哈希计算的集中情况
不实现hashCode_equals 只实现equals,不实现hashCode直接就是p1和p2的索引是不一样的,因为二者的内存地址是不一样的.
只有当二者的索引是一样的时候,才会调用相应的equals方法.
只是实现hashCode
那么就是会出现p2覆盖p1的过程.
构建一个Map接口,接口代码如下所示:
public interface Map<K, V> {int size();boolean isEmpty();void clear();V put(K key, V value);V get(K key);V remove(K key);boolean containsKey(K key);boolean containsValue(V value);void traversal(Visitor<K, V> visitor);public static abstract class Visitor<K, V> {boolean stop;public abstract boolean visit(K key, V value);}}
我们这里的做法是直接将相应的节点放到这个地方，并不是使用放置数组的方式。
HashMap代码
//// Source code recreated from a .class file by IntelliJ IDEA// (powered by Fernflower decompiler)//package com.mj.map;import com.mj.map.Map.Visitor;import com.mj.printer.BinaryTreeInfo;import com.mj.printer.BinaryTrees;import java.util.LinkedList;import java.util.Objects;import java.util.Queue;public class HashMap<K, V> implements Map<K, V> {private static final boolean RED = false;private static final boolean BLACK = true;private int size;private HashMap.Node<K, V>[] table = new HashMap.Node[16];private static final int DEFAULT_CAPACITY = 16;private static final float DEFAULT_LOAD_FACTOR = 0.75F;public HashMap() {}public int size() {return this.size;}public boolean isEmpty() {return this.size == 0;}public void clear() {if (this.size != 0) {this.size = 0;for(int i = 0; i < this.table.length; ++i) {this.table[i] = null;}}}public V put(K key, V value) {this.resize();int index = this.index(key);HashMap.Node<K, V> root = this.table[index];if (root == null) {root = this.createNode(key, value, (HashMap.Node)null);this.table[index] = root;++this.size;this.fixAfterPut(root);return null;} else {HashMap.Node<K, V> node = root;int cmp = 0;K k1 = key;int h1 = this.hash(key);HashMap.Node<K, V> result = null;boolean searched = false;HashMap.Node parent;do {parent = node;K k2 = node.key;int h2 = node.hash;if (h1 > h2) {cmp = 1;} else if (h1 < h2) {cmp = -1;} else if (Objects.equals(k1, k2)) {cmp = 0;} else if (k1 == null || k2 == null || !(k1 instanceof Comparable) || k1.getClass() != k2.getClass() || (cmp = ((Comparable)k1).compareTo(k2)) == 0) {if (searched) {cmp = System.identityHashCode(k1) - System.identityHashCode(k2);} else if ((node.left == null || (result = this.node(node.left, k1)) == null) && (node.right == null || (result = this.node(node.right, k1)) == null)) {searched = true;cmp = System.identityHashCode(k1) - System.identityHashCode(k2);} else {node = result;cmp = 0;}}if (cmp > 0) {node = node.right;} else {if (cmp >= 0) {V oldValue = node.value;node.key = key;node.value = value;node.hash = h1;return oldValue;}node = node.left;}} while(node != null);HashMap.Node<K, V> newNode = this.createNode(key, value, parent);if (cmp > 0) {parent.right = newNode;} else {parent.left = newNode;}++this.size;this.fixAfterPut(newNode);return null;}}public V get(K key) {HashMap.Node<K, V> node = this.node(key);return node != null ? node.value : null;}public V remove(K key) {return this.remove(this.node(key));}public boolean containsKey(K key) {return this.node(key) != null;}public boolean containsValue(V value) {if (this.size == 0) {return false;} else {Queue<HashMap.Node<K, V>> queue = new LinkedList();for(int i = 0; i < this.table.length; ++i) {if (this.table[i] != null) {queue.offer(this.table[i]);while(!queue.isEmpty()) {HashMap.Node<K, V> node = (HashMap.Node)queue.poll();if (Objects.equals(value, node.value)) {return true;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}}return false;}}public void traversal(Visitor<K, V> visitor) {if (this.size != 0 && visitor != null) {Queue<HashMap.Node<K, V>> queue = new LinkedList();for(int i = 0; i < this.table.length; ++i) {if (this.table[i] != null) {queue.offer(this.table[i]);while(!queue.isEmpty()) {HashMap.Node<K, V> node = (HashMap.Node)queue.poll();if (visitor.visit(node.key, node.value)) {return;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}}}}public void print() {if (this.size != 0) {for(int i = 0; i < this.table.length; ++i) {final HashMap.Node<K, V> root = this.table[i];System.out.println("【index = " + i + "】");BinaryTrees.println(new BinaryTreeInfo() {public Object string(Object node) {return node;}public Object root() {return root;}public Object right(Object node) {return ((HashMap.Node)node).right;}public Object left(Object node) {return ((HashMap.Node)node).left;}});System.out.println("---------------------------------------------------");}}}protected HashMap.Node<K, V> createNode(K key, V value, HashMap.Node<K, V> parent) {return new HashMap.Node(key, value, parent);}protected void afterRemove(HashMap.Node<K, V> willNode, HashMap.Node<K, V> removedNode) {}private void resize() {if ((float)(this.size / this.table.length) > 0.75F) {HashMap.Node[] oldTable = this.table;this.table = new HashMap.Node[oldTable.length << 1];Queue<HashMap.Node<K, V>> queue = new LinkedList();for(int i = 0; i < oldTable.length; ++i) {if (oldTable[i] != null) {queue.offer(oldTable[i]);HashMap.Node node;for(; !queue.isEmpty(); this.moveNode(node)) {node = (HashMap.Node)queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}}}}private void moveNode(HashMap.Node<K, V> newNode) {newNode.parent = null;newNode.left = null;newNode.right = null;newNode.color = false;int index = this.index(newNode);HashMap.Node<K, V> root = this.table[index];if (root == null) {this.table[index] = newNode;this.fixAfterPut(newNode);} else {HashMap.Node<K, V> node = root;int cmp = 0;K k1 = newNode.key;int h1 = newNode.hash;HashMap.Node parent;do {parent = node;K k2 = node.key;int h2 = node.hash;if (h1 > h2) {cmp = 1;} else if (h1 < h2) {cmp = -1;} else if (k1 == null || k2 == null || !(k1 instanceof Comparable) || k1.getClass() != k2.getClass() || (cmp = ((Comparable)k1).compareTo(k2)) == 0) {cmp = System.identityHashCode(k1) - System.identityHashCode(k2);}if (cmp > 0) {node = node.right;} else if (cmp < 0) {node = node.left;}} while(node != null);newNode.parent = parent;if (cmp > 0) {parent.right = newNode;} else {parent.left = newNode;}this.fixAfterPut(newNode);}}protected V remove(HashMap.Node<K, V> node) {if (node == null) {return null;} else {HashMap.Node<K, V> willNode = node;--this.size;V oldValue = node.value;HashMap.Node replacement;if (node.hasTwoChildren()) {replacement = this.successor(node);node.key = replacement.key;node.value = replacement.value;node.hash = replacement.hash;node = replacement;}replacement = node.left != null ? node.left : node.right;int index = this.index(node);if (replacement != null) {replacement.parent = node.parent;if (node.parent == null) {this.table[index] = replacement;} else if (node == node.parent.left) {node.parent.left = replacement;} else {node.parent.right = replacement;}this.fixAfterRemove(replacement);} else if (node.parent == null) {this.table[index] = null;} else {if (node == node.parent.left) {node.parent.left = null;} else {node.parent.right = null;}this.fixAfterRemove(node);}this.afterRemove(willNode, node);return oldValue;}}private HashMap.Node<K, V> successor(HashMap.Node<K, V> node) {if (node == null) {return null;} else {HashMap.Node<K, V> p = node.right;if (p != null) {while(p.left != null) {p = p.left;}return p;} else {while(node.parent != null && node == node.parent.right) {node = node.parent;}return node.parent;}}}private HashMap.Node<K, V> node(K key) {HashMap.Node<K, V> root = this.table[this.index(key)];return root == null ? null : this.node(root, key);}private HashMap.Node<K, V> node(HashMap.Node<K, V> node, K k1) {int h1 = this.hash(k1);HashMap.Node<K, V> result = null;boolean var5 = false;while(true) {while(node != null) {K k2 = node.key;int h2 = node.hash;if (h1 > h2) {node = node.right;} else if (h1 < h2) {node = node.left;} else {if (Objects.equals(k1, k2)) {return node;}int cmp;if (k1 != null && k2 != null && k1 instanceof Comparable && k1.getClass() == k2.getClass() && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {node = cmp > 0 ? node.right : node.left;} else {if (node.right != null && (result = this.node(node.right, k1)) != null) {return result;}node = node.left;}}}return null;}}private int index(K key) {return this.hash(key) & this.table.length - 1;}private int hash(K key) {if (key == null) {return 0;} else {int hash = key.hashCode();return hash ^ hash >>> 16;}}private int index(HashMap.Node<K, V> node) {return node.hash & this.table.length - 1;}private void fixAfterRemove(HashMap.Node<K, V> node) {if (this.isRed(node)) {this.black(node);} else {HashMap.Node<K, V> parent = node.parent;if (parent != null) {boolean left = parent.left == null || node.isLeftChild();HashMap.Node<K, V> sibling = left ? parent.right : parent.left;boolean parentBlack;if (left) {if (this.isRed(sibling)) {this.black(sibling);this.red(parent);this.rotateLeft(parent);sibling = parent.right;}if (this.isBlack(sibling.left) && this.isBlack(sibling.right)) {parentBlack = this.isBlack(parent);this.black(parent);this.red(sibling);if (parentBlack) {this.fixAfterRemove(parent);}} else {if (this.isBlack(sibling.right)) {this.rotateRight(sibling);sibling = parent.right;}this.color(sibling, this.colorOf(parent));this.black(sibling.right);this.black(parent);this.rotateLeft(parent);}} else {if (this.isRed(sibling)) {this.black(sibling);this.red(parent);this.rotateRight(parent);sibling = parent.left;}if (this.isBlack(sibling.left) && this.isBlack(sibling.right)) {parentBlack = this.isBlack(parent);this.black(parent);this.red(sibling);if (parentBlack) {this.fixAfterRemove(parent);}} else {if (this.isBlack(sibling.left)) {this.rotateLeft(sibling);sibling = parent.left;}this.color(sibling, this.colorOf(parent));this.black(sibling.left);this.black(parent);this.rotateRight(parent);}}}}}private void fixAfterPut(HashMap.Node<K, V> node) {HashMap.Node<K, V> parent = node.parent;if (parent == null) {this.black(node);} else if (!this.isBlack(parent)) {HashMap.Node<K, V> uncle = parent.sibling();HashMap.Node<K, V> grand = this.red(parent.parent);if (this.isRed(uncle)) {this.black(parent);this.black(uncle);this.fixAfterPut(grand);} else {if (parent.isLeftChild()) {if (node.isLeftChild()) {this.black(parent);} else {this.black(node);this.rotateLeft(parent);}this.rotateRight(grand);} else {if (node.isLeftChild()) {this.black(node);this.rotateRight(parent);} else {this.black(parent);}this.rotateLeft(grand);}}}}private void rotateLeft(HashMap.Node<K, V> grand) {HashMap.Node<K, V> parent = grand.right;HashMap.Node<K, V> child = parent.left;grand.right = child;parent.left = grand;this.afterRotate(grand, parent, child);}private void rotateRight(HashMap.Node<K, V> grand) {HashMap.Node<K, V> parent = grand.left;HashMap.Node<K, V> child = parent.right;grand.left = child;parent.right = grand;this.afterRotate(grand, parent, child);}private void afterRotate(HashMap.Node<K, V> grand, HashMap.Node<K, V> parent, HashMap.Node<K, V> child) {parent.parent = grand.parent;if (grand.isLeftChild()) {grand.parent.left = parent;} else if (grand.isRightChild()) {grand.parent.right = parent;} else {this.table[this.index(grand)] = parent;}if (child != null) {child.parent = grand;}grand.parent = parent;}private HashMap.Node<K, V> color(HashMap.Node<K, V> node, boolean color) {if (node == null) {return node;} else {node.color = color;return node;}}private HashMap.Node<K, V> red(HashMap.Node<K, V> node) {return this.color(node, false);}private HashMap.Node<K, V> black(HashMap.Node<K, V> node) {return this.color(node, true);}private boolean colorOf(HashMap.Node<K, V> node) {return node == null ? true : node.color;}private boolean isBlack(HashMap.Node<K, V> node) {return this.colorOf(node);}private boolean isRed(HashMap.Node<K, V> node) {return !this.colorOf(node);}protected static class Node<K, V> {int hash;K key;V value;boolean color = false;HashMap.Node<K, V> left;HashMap.Node<K, V> right;HashMap.Node<K, V> parent;public Node(K key, V value, HashMap.Node<K, V> parent) {this.key = key;int hash = key == null ? 0 : key.hashCode();this.hash = hash ^ hash >>> 16;this.value = value;this.parent = parent;}public boolean hasTwoChildren() {return this.left != null && this.right != null;}public boolean isLeftChild() {return this.parent != null && this == this.parent.left;}public boolean isRightChild() {return this.parent != null && this == this.parent.right;}public HashMap.Node<K, V> sibling() {if (this.isLeftChild()) {return this.parent.right;} else {return this.isRightChild() ? this.parent.left : null;}}public String toString() {return "Node_" + this.key + "_" + this.value;}}}
LinkedMap代码
//// Source code recreated from a .class file by IntelliJ IDEA// (powered by Fernflower decompiler)//package com.mj.map;import com.mj.map.HashMap.Node;import com.mj.map.Map.Visitor;import java.util.Objects;public class LinkedHashMap<K, V> extends HashMap<K, V> {private LinkedHashMap.LinkedNode<K, V> first;private LinkedHashMap.LinkedNode<K, V> last;public LinkedHashMap() {}public void clear() {super.clear();this.first = null;this.last = null;}public boolean containsValue(V value) {for(LinkedHashMap.LinkedNode node = this.first; node != null; node = node.next) {if (Objects.equals(value, node.value)) {return true;}}return false;}public void traversal(Visitor<K, V> visitor) {if (visitor != null) {for(LinkedHashMap.LinkedNode node = this.first; node != null; node = node.next) {if (visitor.visit(node.key, node.value)) {return;}}}}protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) {LinkedHashMap.LinkedNode<K, V> node1 = (LinkedHashMap.LinkedNode)willNode;LinkedHashMap.LinkedNode<K, V> node2 = (LinkedHashMap.LinkedNode)removedNode;LinkedHashMap.LinkedNode tmp;if (node1 != node2) {tmp = node1.prev;node1.prev = node2.prev;node2.prev = tmp;if (node1.prev == null) {this.first = node1;} else {node1.prev.next = node1;}if (node2.prev == null) {this.first = node2;} else {node2.prev.next = node2;}tmp = node1.next;node1.next = node2.next;node2.next = tmp;if (node1.next == null) {this.last = node1;} else {node1.next.prev = node1;}if (node2.next == null) {this.last = node2;} else {node2.next.prev = node2;}}tmp = node2.prev;LinkedHashMap.LinkedNode<K, V> next = node2.next;if (tmp == null) {this.first = next;} else {tmp.next = next;}if (next == null) {this.last = tmp;} else {next.prev = tmp;}}protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {LinkedHashMap.LinkedNode node = new LinkedHashMap.LinkedNode(key, value, parent);if (this.first == null) {this.first = this.last = node;} else {this.last.next = node;node.prev = this.last;this.last = node;}return node;}private static class LinkedNode<K, V> extends Node<K, V> {LinkedHashMap.LinkedNode<K, V> prev;LinkedHashMap.LinkedNode<K, V> next;public LinkedNode(K key, V value, Node<K, V> parent) {super(key, value, parent);}}}
