手写一个简单的HashMap
source link: http://www.cnblogs.com/2511zzZ/p/12770864.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
HashMap简介
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方法
@Override
public 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方法
@Override
public 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方法
@Override
public 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的实现，还有几点我们没有解决：
NullPointerException
相信大家自己完成了对HashMap的实现之后，对它的原理一定会有更深刻的认识，本文如果有错误或是不严谨的地方也欢迎大家指出。上述的问题我们接下来再逐步解决，至于红黑树，我也不会（摊手）。
Recommend
-
126
-
134
深度强化学习是学术界研制游戏 AI 的主流算法。这篇文章我们将用深度强化学习早期代表算法 DQN 算法探索棋牌 AI。我们利用非完美信息游戏环境 RoomAI 提供的七鬼五二三游戏上，用 DQN 开发 AI。实验表明，DQN 能够取得一定的效果。
-
27
示例代码请点这里 上一次我们简单了解了一下 redux（文章在这里），今天我们来结合 React，实现自己的 React-redux。 一、创建项目 我们用 create-react-app 创建一个新项目，删除 src 下的冗余部分，添加自己的文件，如下：
-
32
确认过眼神，你还是没有准备秋招的人？时间仓促。自京东6月8号开启管培生的招聘，就意味着秋招的开始。然而你还在等着秋天的到来？今年形势应该更为严峻，随着各大技术(vue,webpack，react，微信小程序)生态越来越成熟，这也意味着我们要更加深入的去了解他们
-
94
MVVM 的前世今生 MVVM 设计模式，是由 MVC（最早来源于后端）、MVP 等设计模式进化而来，M - 数据模型（Model），VM - 视图模型（ViewModel），V - 视图层（View）。 在 MVC 模式中，除了 Model 和 View 层
-
113
最近研究了 DatePicker 的实现原理后做了一个 vue 的 DatePicker 组件，今天带大家一步一步实现 DatePicker 的 vue 组件。 原理 DatePicker 的原理是——计算日历面板中当月或选中月份的总天数及前后月份相近的日子
-
51
前一阵子，收到烨兄的私聊，他突然要解决这样一个任务： 做如下格式的表达式转换： Multi(a, Multi(b, c)) --> a * (b * c) Divide(a, Sub(b, c)) --> a / (b - c) 支持的运算符有：
-
50
前言 HashMap应该算是Java后端工程师面试的必问题，因为其中的知识点太多，很适合用来考察面试者的Java基础。 开场 面试官:你先自我介绍一下吧！ 安琪拉:我是安琪拉，草丛三婊之一，最强中单...
-
17
动手写一个简单的编译器：在JavaScript中使用Swift的尾闭包语法首先跟大家说一下我为什么会有这个想法吧，因为最近在空闲时间学习Swift和SwiftUI的时候会经常使用到这种叫做
-
6
简单实现一个底层数据结构为数组 + 链表的HashMap,不考虑链表长度超过8个时变为红黑树的情况。 1.示例图
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK