哈希表|哈希表2--Hashmap的实现详解


这里写目录标题

      • 一,前言
      • 二,大体框架
      • 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。所以我们仅仅需要红黑树的节点,和他的存储逻辑。
哈希表|哈希表2--Hashmap的实现详解
文章图片

我们就是把红黑树的结点拿过来,改成映射(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上的其他结点的问题,因为必定没有两个相同的结点。

    推荐阅读