手搓 Java hashmap

1. 前言

都知道 hashmap 是哈希表，字典，这里全萌新向，至于为什么萌新向，因为我也不会，算是拷打自己对于一些流程的实现。

我们先把最基础的功能实现了，后面再考虑扰动，红黑冲突树，并发安全，以及渐进式 hash这些高阶功能。

2. 实现过程

2.1. 底层存储结构

这里毫无疑问，就选择数组就行，初始容量我们随便写一个，就写 10 算了。
在这里插入图片描述

java">class BestHashMap{private E[]EArr = new E[10];
}
class E{private Object key;private Object value;
}

2.2. 存入元素（put 函数）

put 函数，可以说是整个 hashmap 的重点

先计算下标

java">        int index = key.hashCode() % EArr.length;

这里没使用位运算，和扰动函数，主打一个便于理解，Java 本身就提供了好用的 hashcode

有下标是不是要存元素了，还不行！

因为这个位置万一有元素呢，这里我们要考虑到冲突问题，最简单的方法就是使用链表，吧 index 一样的元素都存在一个数组下标下面，俗称拉链法

java">public void put(Object key, Object value){int index = Math.abs(key.hashCode() % EArr.length);ListNode listNode = new ListNode(new E(key,value),null);ListNode tempNode = null;int deep = 0;if(EArr[index] != null){tempNode = EArr[index];deep = 1;while (tempNode.next != null){if(tempNode.e.key.equals(key)){tempNode.e.value = value;}tempNode = tempNode.next;deep++;}}if(tempNode != null){tempNode.next = listNode;}else{EArr[index] = listNode;useIndexSum++;}if(deep >= 8 || useIndexSum / (float)EArr.length >= 0.75){grow();}}

2.2. 取出元素（get 函数）

java"> public Object get(Object key){int index = Math.abs(key.hashCode() % EArr.length);ListNode tempNode = null;if(EArr[index] != null){tempNode = EArr[index];while (tempNode != null){if(key == tempNode.e.key){return tempNode.e.value;}tempNode = tempNode.next;}}return null;}

2.3. 扩容

首先，为什么要扩容？想象一下，如果1w 个元素存在十个长度大小的元素中，那么一个下标下起码有 1千元素，效率就会下降非常多，性能就会不如二叉排序树。

所以，我们希望，每个元素都有一个自己的下标，又不浪费过多的内存空间，这里直接公布答案了，就是数组使用超过 75% 进行扩容最合适，每次扩容为原来的二倍。Java 默认实现在链表大于 8 时会转换为红黑树，这里我们同样适用扩容代替

java">private void grow(){useIndexSum = 0;ListNode[] newArr = new ListNode[2 * EArr.length];for(ListNode node : EArr){ArrayList<ListNode>list = new ArrayList<>();while (node != null){list.add(node);node = node.next;}for(ListNode l : list){putToNewArr(l,newArr);}}EArr = newArr;}public void putToNewArr(ListNode listNode,ListNode[] newArr){int index = Math.abs(listNode.e.key.hashCode() % newArr.length);ListNode tempNode = null;if(newArr[index] != null){tempNode = newArr[index];while (tempNode.next != null){if(tempNode.e.value.equals(listNode.e.key)){tempNode.e.value = listNode.e.value;return;}tempNode = tempNode.next;}}if(tempNode != null){tempNode.next = listNode;}else{newArr[index] = listNode;useIndexSum++;}}

这样主体功能就完毕了

2. 优化思路

扰动函数

java">static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这是 jdk8 中的实现，有没有发现有什么不同，总体的思路是把高位的数据影响加到低的16位上，一般来说高16位容易被除数除干净，不太容易对数据起影响，右移之后就容易起影响了。

并发问题
最简单的方法就是对 put 函数增加 synchronized,当然，这只是最简单的实现，可以使用分段锁获取更高的性能。

java">    synchronized public void  put(Object key, Object value)

java">class BestHashMap {private static final int DEFAULT_INITIAL_CAPACITY = 10;private static final float DEFAULT_LOAD_FACTOR = 0.75f;private ListNode[] table;private int size;private  ReentrantLock[] locks;public BestHashMap() {table = new ListNode[DEFAULT_INITIAL_CAPACITY];locks = new ReentrantLock[DEFAULT_INITIAL_CAPACITY];for (int i = 0; i < locks.length; i++) {locks[i] = new ReentrantLock();}}private int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}public void put(Object key, Object value) {int hash = hash(key);int index = (table.length - 1) & hash;ReentrantLock lock = locks[index];lock.lock();try {ListNode listNode = new ListNode(new E(key, value), null);ListNode tempNode = table[index];int deep = 0;while (tempNode != null) {if (tempNode.e.key.equals(key)) {tempNode.e.value = value;return;}tempNode = tempNode.next;deep++;}listNode.next = table[index];table[index] = listNode;size++;if (deep >= 8 || size / (float) table.length >= DEFAULT_LOAD_FACTOR) {grow();}} finally {lock.unlock();}}public Object get(Object key) {int hash = hash(key);int index = (table.length - 1) & hash;ReentrantLock lock = locks[index];lock.lock();try {ListNode tempNode = table[index];while (tempNode != null) {if (key.equals(tempNode.e.key)) {return tempNode.e.value;}tempNode = tempNode.next;}return null;} finally {lock.unlock();}}private void grow() {ListNode[] oldTable = table;ListNode[] newTable = new ListNode[oldTable.length * 2];ReentrantLock[] newLocks = new ReentrantLock[newTable.length];for (int i = 0; i < newLocks.length; i++) {newLocks[i] = new ReentrantLock();}for (ListNode node : oldTable) {while (node != null) {ListNode next = node.next;int hash = hash(node.e.key);int index = (newTable.length - 1) & hash;node.next = newTable[index];newTable[index] = node;node = next;}}table = newTable;locks = newLocks;}
}class E {Object key;Object value;public E(Object key, Object value) {this.key = key;this.value = value;}
}class ListNode {E e;ListNode next;public ListNode(E e, ListNode next) {this.e = e;this.next = next;}
}