写点什么

花 5 分钟手写一个简单的 HashMap,搞定挑剔面试官

用户头像
北游学Java
关注
发布于: 2021 年 05 月 29 日

前言

今天去面试啊,聊得差不多的时候面试官突然问我会手写 HashMap 吗?这我哪能怂啊,好死不死的面试之前我还真手写过一个简单的 HashMap,所以我不过花了 5 分钟便弄出来了,面试官直呼内行。


相信大家关于 HashMap 的面试题刷的也不少了,源码应该也看了很多遍,大部分人可以说是非常熟悉了,但是如果面试官突然给你们整这么一手,我相信很多人还是会表示懵逼的。所以今天给大伙捋一捋,掌握手写 HashMap 之后都给我去手撕面试官。


除了 hashmap 之外我还整理了很多经典面试题,做成了一本 PDF,内容不多,但全是干货,需要的朋友可以点击这里领取>>互联网公司Java面试核心知识



HashMap 是 Java 中一中非常常用的数据结构,也基本是面试中的“必考题”。它实现了基于“K-V”形式的键值对的高效存取。JDK1.7 之前,HashMap 是基于数组+链表实现的,1.8 以后,HashMap 的底层实现中加入了红黑树用于提升查找效率。


HashMap 根据存入的键值对中的 key 计算对应的 index,也就是它在数组中的存储位置。当发生哈希冲突时,即不同的 key 计算出了相同的 index,HashMap 就会在对应位置生成链表。当链表的长度超过 8 时,链表就会转化为红黑树。



手写 HashMap 之前,我们讨论一个小问题:当我们在 HashMap 中根据 key 查找 value 时,在数组、链表、红黑树三种情况下,平均要做多少次比较?


在数组中查找时,我们可以通过 key 的 hashcode 直接计算它在数组中的位置,比较次数为 1

在链表中查找时,根据 next 引用依次比较各个节点的 key,长度为 n 的链表节点平均比较次数为 n/2

在红黑树中查找时,由于红黑树的特性,节点数为 n 的红黑树平均比较次数为 log(n)


前面我们提到,链表长度超过 8 时树化(TREEIFY),正是因为 n=8,就是 log(n) < n/2 的阈值。而 n<6 时,log(n) > n/2,红黑树解除树化(UNTREEIFY)。另外我们可以看到,想要提高 HashMap 的效率,最重要的就是尽量避免生成链表,或者说尽量减少链表的长度,避免哈希冲突,降低 key 的比较次数。

手写 HashMap

定义一个 Map 接口

也可以使用 Java 中的java.util.Map


public interface MyMap<K,V> {
V put(K k, V v);
V get(K k);
int size();
V remove(K k);
boolean isEmpty();
void clear();}
复制代码


然后编写一个 MyHashMap 类,实现这个接口,并实现里面的方法。

成员变量

    final static int DEFAULT_CAPACITY = 16;    final static float DEFAULT_LOAD_FACTOR = 0.75f;
int capacity; float loadFactor; int size = 0;
Entry<K,V>[] table;
复制代码


class Entry<K, V>{    K k;    V v;    Entry<K,V> next;
public Entry(K k, V v, Entry<K, V> next){ this.k = k; this.v = v; this.next = next; }}
复制代码


我们参照 HashMap 设置一个默认的容量 capacity 和默认的加载因子 loadFactor,table 就是底层数组,Entry 类保存了"K-V"数据,next 字段表明它可能会是一个链表节点。

构造方法

public MyHashMap(){    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);}
public MyHashMap(int capacity, float loadFactor){ this.capacity = upperMinPowerOf2(capacity); this.loadFactor = loadFactor; this.table = new Entry[capacity];}
复制代码


这里的upperMinPowerOf2的作用是获取大于 capacity 的最小的 2 次幂。在 HashMap 中,开发者采用了更精妙的位运算的方式完成了这个功能,效率比这种方式要更高。


private static int upperMinPowerOf2(int n){    int power = 1;    while(power <= n){        power *= 2;    }    return power;}
复制代码


为什么 HashMap 的 capacity 一定要是 2 次幂呢?这是为了方便 HashMap 中的数组扩容时已存在元素的重新哈希(rehash)考虑的。

put 方法

@Overridepublic V put(K k, V v) {    // 通过hashcode散列    int index = k.hashCode() % table.length;    Entry<K, V> current = table[index];    // 判断table[index]是否已存在元素    // 是    if(current != null){        // 遍历链表是否有相等key, 有则替换且返回旧值        while(current != null){            if(current.k == k){                V oldValue = current.v;                current.v = v;                return oldValue;            }            current = current.next;        }        // 没有则使用头插法        table[index] = new Entry<K, V>(k, v, table[index]);        size++;        return null;    }    // table[index]为空 直接赋值    table[index] = new Entry<K, V>(k, v, null);    size++;    return null;}
复制代码


put 方法中,我们通过传入的 K-V 值构建一个 Entry 对象,然后判断它应该被放在数组的那个位置。回想我们之前的论断:


想要提高 HashMap 的效率,最重要的就是尽量避免生成链表,或者说尽量减少链表的长度


想要达到这一点,我们需要 Entry 对象尽可能均匀地散布在数组 table 中,且 index 不能超过 table 的长度,很明显,取模运算很符合我们的需求int index = k.hashCode() % table.length。关于这一点,HashMap 中也使用了一种效率更高的方法——通过 &运算完成 key 的散列,有兴趣的同学可以查看 HashMap 的源码。


如果 table[index]处已存在元素,说明将要形成链表。我们首先遍历这个链表(长度为 1 也视作链表),如果存在 key 与我们存入的 key 相等,则替换并返回旧值;如果不存在,则将新节点插入链表。插入链表又有两种做法:头插法尾插法。如果使用尾插法,我们需要遍历这个链表,将新节点插入末尾;如果使用头插法,我们只需要将 table[index]的引用指向新节点,然后将新节点的 next 引用指向原来 table[index]位置的节点即可,这也是 HashMap 中的做法。



如果 table[index]处为空,将新的 Entry 对象直接插入即可。

get 方法

@Overridepublic V get(K k) {    int index = k.hashCode() % table.length;    Entry<K, V> current = table[index];    // 遍历链表    while(current != null){        if(current.k == k){            return current.v;        }        current = current.next;    }    return null;}
复制代码


调用 get 方法时,我们根据 key 的 hashcode 计算它对应的 index,然后直接去 table 中的对应位置查找即可,如果有链表就遍历。

remove 方法

@Overridepublic V remove(K k) {    int index = k.hashCode() % table.length;    Entry<K, V> current = table[index];    // 如果直接匹配第一个节点    if(current.k == k){        table[index] = null;        size--;        return current.v;    }    // 在链表中删除节点    while(current.next != null){        if(current.next.k == k){            V oldValue = current.next.v;            current.next = current.next.next;            size--;            return oldValue;        }        current = current.next;    }    return null;}
复制代码


移除某个节点时,如果该 key 对应的 index 处没有形成链表,那么直接置为 null。如果存在链表,我们需要将目标节点的前驱节点的 next 引用指向目标节点的后继节点。由于我们的 Entry 节点没有 previous 引用,因此我们要基于目标节点的前驱节点进行操作,即:


current.next = current.next.next;
复制代码


current 代表我们要删除的节点的前驱节点。


还有一些简单的 size()、isEmpty()等方法都很简单,这里就不再赘述。现在,我们自定义的 MyHashMap 基本可以使用了。

最后

关于 HashMap 的实现,还有几点我们没有解决:


  1. 扩容问题。在 HashMap 中,当存储的元素数量超过阈值(threshold = capacity * loadFactor)时,HashMap 就会发生扩容(resize),然后将内部的所有元素进行 rehash,使 hash 冲突尽可能减少。在我们的 MyHashMap 中,虽然定义了加载因子,但是并没有使用它,capacity 是固定的,虽然由于链表的存在,仍然可以一直存入数据,但是数据量增大时,查询效率将急剧下降。

  2. 树化问题(treeify)。我们之前讲过,链表节点数量超过 8 时,为了更高的查询效率,链表将转化为红黑树。但是我们的代码中并没有实现这个功能。

  3. null 值的判断。HashMap 中是允许存 null 值的 key 的,key 为 null 时,HashMap 中的 hash()方法会固定返回 0,即 key 为 null 的值固定存在 table[0]处。这个实现起来很简单,不实现的情况下 MyHashMap 中如果存入 null 值会直接报NullPointerException异常。

  4. 一些其他问题。


相信大家自己完成了对 HashMap 的实现之后,对它的原理一定会有更深刻的认识,本文如果有错误或是不严谨的地方也欢迎大家指出。上述的问题我们接下来再逐步解决。




往期热文



end

发布于: 2021 年 05 月 29 日阅读数: 50
用户头像

北游学Java

关注

进群1044279583分享学习经验和分享面试心得 2020.11.16 加入

我秃了,也变强了

评论

发布
暂无评论
花5分钟手写一个简单的HashMap,搞定挑剔面试官