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 {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[] table;class Entry{K k;V v;Entry next;public Entry(K k, V v, Entry 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 current = table[index];// 判断table[index]是否已存在元素// 是if(current != null){// 遍历链表是否有相等key, 有则替换且返回旧值while(current != null){if(current.k == k){V oldValue = http://kandian.youth.cn/index/current.v;current.v = v;return oldValue;}current = current.next;}// 没有则使用头插法table[index] = new Entry(k, v, table[index]);size++;return null;}// table[index]为空 直接赋值table[index] = new Entry(k, v, null);size++;return null;}put方法中 ， 我们通过传入的K-V值构建一个Entry对象 ， 然后判断它应该被放在数组的那个位置 。 回想我们之前的论断：
想要提高HashMap的效率 ， 最重要的就是尽量避免生成链表 ， 或者说尽量减少链表的长度
想要达到这一点 ， 我们需要Entry对象尽可能均匀地散布在数组table中 ， 且index不能超过table的长度 ， 很明显 ， 取模运算很符合我们的需求 int index = k.hashCode() % table.length。 关于这一点 ， HashMap中也使用了一种效率更高的方法——通过Entry 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 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 = http://kandian.youth.cn/index/current.next.v;current.next = current.next.next;size--;return oldValue;}current = current.next;}return null;}