这里写目录标题

• • • 一，前言
    • 二，大体框架
    • 1.Map接口创建
    • 2.存储节点的设计
    • 3.大体框架
    • 三，常用方法实现
    • _1.clear方法_
    • _2.put方法_
    • • （1）准备工作1：计算index的方法
      • （2）开始写put方法
    • _3.node查找节点方法，containsKey方法_
    • _4.remove方法_
    • _5.containValue方法_
    • 四.Hashmap的扩容
    • _1.一些概念_
    • _2.方法实现_

一，前言
之前的文章哈希表1，大体介绍了哈希表的结构，和哈希冲突的解决，以及各种数据类型如何生成哈希值。现在来一步一步的实现hashmap。
学习hashmap必须对红黑树有一定的了解，不然学不会的。
二，大体框架
1.Map接口创建
众所周知hashmap 是对接口 map的实现，首先我们创建一个接口，
接口中写一些map的通用方法。

public interface Map { 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 visitor); public static abstract class Visitor{ boolean stop; public abstract boolean visit(K key,V value); } }

2.存储节点的设计
在之前的文章里说过，当哈希表容量 >= 64 且单向链表的节点数大于8 时，我们会把单向链表转化为红黑树存储。这里为了方便一些，我们用红黑树节点存储。为什么不用红黑树？因为红黑树中有我们不需要的东西，比如比较器comparator，size。所以我们仅仅需要红黑树的节点，和他的存储逻辑。

文章图片

我们就是把红黑树的结点拿过来，改成映射（map）的形式就可以使用了。
这里我们添加了K key，和V Value。
添加了 int hash，用来记录这个节点的哈希值。
hash ^(hash >>> 16); 这种运算被称为扰动运算，目的是对哈希值的进一步处理，尽量让所有的Key值信息都参与哈希值的运算。

//节点 private static class Node{ int hash; K key; V value; boolean color = RED; Node left; Node right; Node parent; public Node(K key, V value, Node parent) { this.key = key; this.value = https://www.it610.com/article/value; this.parent = parent; int hash = key == null? 0 : key.hashCode(); this.hash = hash ^(hash>>> 16); } //是否为叶子节点 public boolean isLeaf() { return left == null && right == null; }//是否有两个孩子 public boolean hasTwoChildren() { return left != null && right != null; } //自己是否为左子树 public boolean isLeftChild() { return parent != null && this == parent.left; } //自己是否为右子树 public boolean isRightChild() { return parent != null && this == parent.right; } /* 查找兄弟节点 */ public Node sibling() { if (isLeftChild()) { return parent.right; } if (isRightChild()) { return parent.left; } return null; } }

3.大体框架
Hashmap 实现 Map接口，添加未实现的方法。
size： Hashmap的大小一定要有的。
s private Node[] table; ：哈希表底层由数组实现的。
默认容量：尽量写成2的多少次方，因为JVM可以做出优化（2^3 优化为 1<<4）。
构造函数：给数组（hashmap）一个默认容量。

public class HashMap implements Map{ private int size; private static final boolean BLACK = true; private static final boolean RED = false; //默认容量 private static final int DEFAULT_CAPACITU = 1<<4; //数组 private Node[] table; //数组的默认容量 public HashMap() { table = new Node[DEFAULT_CAPACITU]; } //节点 private static class Node{ K Key; V Value; boolean color = RED; Node left; Node right; Node parent; public Node(K key, V value, Node parent) { Key = key; Value = https://www.it610.com/article/value; this.parent = parent; } //是否为叶子节点 public boolean isLeaf() { return left == null && right == null; }//是否有两个孩子 public boolean hasTwoChildren() { return left != null && right != null; } //自己是否为左子树 public boolean isLeftChild() { return parent != null && this == parent.left; } //自己是否为右子树 public boolean isRightChild() { return parent != null && this == parent.right; } /* 查找兄弟节点 */ public Node sibling() { if (isLeftChild()) { return parent.right; } if (isRightChild()) { return parent.left; } return null; } } @Override public int size() { // TODO 自动生成的方法存根 return size; } @Override public boolean isEmpty() { // TODO 自动生成的方法存根 return size == 0; } @Override public void clear() { // TODO 自动生成的方法存根 } @Override public V put(K key, V value) { // TODO 自动生成的方法存根 return null; } @Override public V get(K key) { // TODO 自动生成的方法存根 return null; } @Override public V remove(K key) { // TODO 自动生成的方法存根 return null; } @Override public boolean containsKey(K key) { // TODO 自动生成的方法存根 return false; } @Override public boolean containsValue(V value) { // TODO 自动生成的方法存根 return false; } @Override public void traversal(Visitor visitor) { // TODO 自动生成的方法存根 } }

三，常用方法实现
1.clear方法
这里要注意的就是先判断size是否为0，在做清除。我们为了防止这种情况：数组已经扩容很大了，但是数组已经空了，如果我们再去遍历清除，会很浪费性能。

public void clear() { // TODO 自动生成的方法存根 if (size == 0) { return; } size = 0; for(int i = 0; i < table.length; i ++) { table[i] = null; } }

2.put方法
（1）准备工作1：计算index的方法 想要把一数据插入哈希表，首先要根据Key的哈希值计算索引。
两个重载的函数，一个根据给定的key算索引，一个根据给定的node算索引。

/* 通过key算索引 */ private int index(K key) { //key为空 默认放在0位置 if(key == null) return 0; int hashcode = key.hashCode(); //二次运算 return (hashcode ^ (hashcode >>> 16)) & (table.length - 1); } private int index(Node node) { return node.hash & (table.length - 1); }

（2）开始写put方法 之前我们说了哈希表存储节点用的是红黑树的存储逻辑（二叉搜索树的添加逻辑 + 红黑树的平衡逻辑）。
这里还有一点需要提的：根结点如何设置的问题。在红黑树中专门有一个root属性表示结点。修改根结点直接赋值即可。但是在hashmap我们使用的是红黑树结点存储，并没有root这个属性。
解决方法：table[index] 表示的就是数组中 index 那一行中的第一个结点，即那棵树的根结点。
步骤：
1.首先根据Key的哈希值生成索引。
2.看索引对应的那颗红黑树（或链表）是否为空，若为空则把key和value存入根节点中。
3.若不为空就是有哈希冲突了，我们用如下的存储逻辑

存储逻辑： 我们用的是二叉树的存储逻辑，整个步骤大体分两块，第一，比较大小来得出cmp的值（cmp > 0插入节点相比较大，cmp < 0插入节点相比较小），第二，根据cmp值的正负，再和它的左、右子节点比较。一直重复这个过程直到找到插入节点的合适位置。 但是，hashmap存储的节点不需要具有可比较性。那我们通过什么来比较呢？？比较逻辑还是有的，如下：

1.首先通过key的哈希值比较来决定cmp的值（正或负）
2.如果key的哈希值相同，并且两个key不为null、两个key为同一个类、此类具有可比较性，我们就使用comparTo对两个key作比较。
3.若cmpareTo得出的不为0，我们做的操作仅仅是把结果赋值给cmp就行。
若comoareTo得出的值为零，那我们就黔驴技穷了，我们只能通过地址值的比较来得出cmp的值了。（为什么compareTo为0就不能赋值给cmp了？？ 因为compareTo为0，代表key中的某个属性一样，就好像people类中的age属性一样，并不能代表这两个就是同一个人，而我们设定cmp为0则这两个key为同一个，value值直接覆盖）

public V put(K key, V value) { // 根节点为null的情况 int index = index(key); Node root = table[index]; if (root == null) { root = new Node<>(key, value, null); table[index] = root; size ++; afterAdd(root); return null; } //根节点不为空 哈希冲突了 添加新的节点到红黑树上面 Node parent = root; Node node = root; int cmp = 0; K k1 = key; int h1 = hash(k1); //记录比较结果 Node result = null; boolean searched = false; 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.getClass() == k2.getClass() && k1 instanceof Comparable && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {}else if(searched){ cmp = System.identityHashCode(k1) - System.identityHashCode(k2); }else { //覆盖去重 if ((node.left != null && (result = node(node.left,k1)) != null) ||(node.right != null && (result = node(node.right,k1)) != null)) { node = result; cmp = 0; }else { cmp = System.identityHashCode(k1) - System.identityHashCode(k2); } }if (cmp > 0) { node = node.right; }else if (cmp < 0) { node = node.left; }else { //相等覆盖 //防止是引用类型 除了年龄还有别的属性 node.key = key; V oldValue = https://www.it610.com/article/node.value; node.value = value; return oldValue; } }while(node != null) ; //创建新节点 Node newNode = new Node<>(key, value, parent); //插入父节点左右 if (cmp > 0) { parent.right = newNode; }else { parent.left = newNode; }size ++; afterAdd(newNode); return null; }

3.node查找节点方法，containsKey方法
node查找节点方法，基本上和put方法的思路差不多。不同之处是在比较的最后，我们实在找不到对比方式的时候，put方法是用地址值的比较来决定cmp的正负。而node的处理思路是：首先分析一下，我们比较地址值时的条件——哈希值相等，内容不等，不是同一类型。此时参数结点和正在比较的结点已经无法比较了，而且也没有再比较下去的必要了，因为这两个节点一定不相同，我们就把参数结点和正在比较的结点的左右子节点做比较（采用递归调用的方法）一直到找到符合条件的节点，或者最终都没有找到返回null。
为什么node不使用地址值的比较？
比如我们再查找函数node中传入一个新创建引用类型，这个引用类型的地址一定是和我们Hashmap中存储的引用类型不同的。如果运气好可以比较两个引用类型的值，也许可以找到。如果因为某些原因比较一次地址，也许就永远都找不到了（即使树中存在也找不到，地址值永远不相等）。

private Node node(K key){ //取根节点 Node root = table[index(key)]; return root ==null ? null : node(root, key); } private Node node(Node node,K k1) { int h1 = hash(k1); //存储查找的结果 Node result = null; int cmp = 0; 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; }else if (k1 != null && k2 != null && k1.getClass() == k2.getClass() && k1 instanceof Comparable && (cmp = ((Comparable)k1).compareTo(k2)) != 0) { if (cmp > 0) { node = node.right; }else if (cmp < 0) { node = node.left; } }else if (node.right != null && (result = node(node.right,k1)) != null) { return result; }else { node = node.left; } } return null; }

@Override public boolean containsKey(K key) { // TODO 自动生成的方法存根 return node(key) != null; }

4.remove方法
方法的实现逻辑和红黑树的基本一样分几种情况讨论。这个我在之前的二叉搜索树中有记录。二叉搜索树的重构

@Override public V remove(K key) { return remove(node(key)); } private V remove(Node node) { //结点为空 if(node == null) return null; size --; //删除结点是度为2的结点 if (node.hasTwoChildren()) { //找后继结点 Node s = successor(node); //后继节点的值覆盖原来结点 node.key = s.key; node.value = https://www.it610.com/article/s.value; //下面还要删除后继结点 node = s; }//删除node 结点(现在node的度必然为0 或者1) Node replacement = node.left != null ? node.left : node.right; if (replacement != null) {//node 是度为1的结点 //更改parent replacement.parent = node.parent; //若果node为度为1的根节点 if (node.parent == null) { table[index(node)] = replacement; }else if (node == node.parent.left) {//node是左子节点node.parent.left = replacement; }else if(node == node.parent.right){//node是右子节点node.parent.right = replacement; } afterRemove(node,replacement); return node.value; }else if (node.parent == null) {//node是叶子结点并且是根结点table[index(node)] = null; afterRemove(node,null); return node.value; }else {//是叶子结点 且不是根结点 直接删除if (node == node.parent.left) { node.parent.left = null; }else { node.parent.right = null; } afterRemove(node,null); return node.value; } }

5.containValue方法
遍历整棵红黑树，使用层序遍历

/* * 找value就只能遍历整个map来找了 * 红黑树的遍历我们用层序遍历 */ @Override public boolean containsValue(V value) { if(size == 0) return false; Queue> queue = new LinkedList<>(); for(int i = 0; i < table.length; i ++) { if(table[i] == null) continue; queue.offer(table[i]); while(!queue.isEmpty()) { Node node = queue.poll(); if (Objects.equals(node.value, value)) return true; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } return false; }

四.Hashmap的扩容
1.一些概念

• 装填因子： 总结点数量/哈希表桶数组的长度，也叫负载因子
• 在JDK1.8的Hashmap中，如果装填因子超过0.75，就扩容为原来的2倍。

2.方法实现
1.添加装填因子属性

private static final float DEFAULT_LOAD_FACTOR = 0.75f;

2.方法的实现
思路一：扩容之后我们遍历所有的节点，直接使用put方法将他们添加到新的（扩容后的）Hashmap中。这种做法着实不好，因为我们每次添加都要 new Node<>(key, value, parent); 这样也太浪费内存了。
思路二：扩容之后我们遍历所有的节点，将节点移动到新的Hashmap中，这就省去创建新的节点了，节约内存
我们当然是选择第二种思路了。
实现步骤
1.resize方法（）
判断数组是否需要扩容，如果需要的话采用层序遍历，把结点移动到新的数组（扩容后）中。

private void resize() { //装填因子 <= 0.75 if (size / table.length <= DEFAULT_LOAD_FACTOR) return; //扩容实现 Node []oldTable = table; table = new Node[oldTable.length << 1]; //层序遍历 Queue> queue = new LinkedList<>(); for(int i = 0; i < oldTable.length; i ++) { if(oldTable[i] == null) continue; queue.offer(oldTable[i]); while(!queue.isEmpty()) { Node node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } moveNode(node); } } }

方法写完还有一个问题，我们在哪里判断是否需要扩容呢？
在添加方法（put）的最前面判断是否需要扩容
2.结点的转移方法moveNode
节点移动的方法
结点移动到新的数组中，应该放置什么位置？我们采用的还是put方法中的逻辑，不同的是我们不新建结点，而是把旧的结点放进去。

public void moveNode(Node newNode) { //去除曾经的关系 newNode.parent = null; newNode.left = null; newNode.right = null; newNode.color = RED; //移动添加 // 根节点为null的情况 int index = index(newNode); Node root = table[index]; if (root == null) { root = newNode; table[index] = root; afterAdd(root); return ; } //根节点不为空 哈希冲突了 添加新的节点到红黑树上面 Node parent = root; Node node = root; int cmp = 0; K k1 = newNode.key; int h1 = newNode.hash; 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.getClass() == k2.getClass() && k1 instanceof Comparable && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { }else { 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; } afterAdd(newNode); }

【哈希表|哈希表2--Hashmap的实现详解】思路实现中的一些坑：
1.移动时候，是不需要考虑新的数组的size问题，size一定是原来数组的二倍。
2.在移动结点的时候，要把原先的属性去除，比如父节点、左右子树、颜色之类的。父节点，子树结点通通设置为null，结点的颜色通通设置为RED（红黑树结点的初始化颜色为红色）
3.由于我们只是转移结点，也不需要考虑插入结点是否会覆盖同一个index上的其他结点的问题，因为必定没有两个相同的结点。

推荐阅读

• 

  鱼缸加热棒什么牌子口碑好？推荐几款口碑好的鱼缸加热棒
• 

  DNF现阶段如何能快速升级？
• 

  术数纵横怎么没有了 术数纵横
• 

  三围女生标准对照表 腰围怎么量
• 

  APP怎么查看失效的优惠券
• 

  如何在手机维修行业中打造专业的换屏服务？ 手机专业换屏服务器怎么弄
• 

  草莓酱怎么算熬好了
• 

  创维盒子安装第三种桌面方法 电信机顶盒破解版刷机教程
• 

  底特律变人破碎马库斯流程分支图一览 第八章收集攻略
• 

  桔梗的食用方法和药用价值 桔梗的食用方法
• 

  离开的理由我为之离开的理由
• 

  猫咪吹空调会感冒吗?
• 

  拍摄能结合什么，拍摄方式的作用
• 

  文的盲刷LeetCode|文的盲刷LeetCode 24. 两两交换链表中的节点
• 

  给美丽做道加法。
• 

  存储空间降为|存储空间降为 MySQL 的十分之一，TDengine 在货拉拉数据库监控场景的应用
• 

  筏钓怎么绑 筏钓线组怎么绑
• 

  大闸蟹蒸多长时间为最佳
• 

  挽组词语 汉字挽组词语
• 

  比亚迪e3续航里程多远 比亚迪e3真实续航里程

• 数据结构与算法|【Java数据结构】哈希表详解
• Android|Android全面解析之由浅及深Handler消息机制
• 数据库|Redis——作为sql数据库缓存
• Redis|Redis——Redis用作缓存（内存回收/穿透/击穿/雪崩）
• 安卓源码探究|android源码学习-Handler机制及其六个核心点
• 《C语言杂俎》|证明堆排序的时间复杂度
• 指针|【发际线大作战】C++学习记录之用户自定义数据类型
• Java|idea 设置导航栏显示前进和后退返回键
• idea|idea前进和后退按钮如何显示