一、概述
在前面的文章中，我们分析了Map的原理，在弄清楚它的原理后，本文中我们来进行实践，手写一个简单的HashMap。
二、手写HashMap
- 手写一个HashMap必然要有插入，和查找的功能，所以我们先定义一个接口，定义插入和查找的方法。额外再加一个获取数量的方法。
public interface Map<K,V> {
V put(K k,V v);
V get(K k);
int size();
}
- 我们都知道，HashMap底层用的是数组+链表，所以我们在Map中再定义一个Node节点的接口，用来存储数据。
public interface Map<K,V> {
V put(K k,V v);
V get(K k);
int size();
interface Node<K,V>{
K getKey();
V getValue();
}
}
- 接口定义好之后 我们来写具体实现HashMap类。
public class HashMap<K,V> implements Map<K,V>{
//创建数组
private Node<K,V> table[];
//数组长度
final int LENGHT = 16;
//元素长度
private int size = 0;
public HashMap() {
table = new Node[LENGHT];
}
/**
* 通过key 算出hash
* 算出index
* 判断node[index]是否为空
* 不为空直接插入
* 不为空赋值给next
* @param k
* @param v
* @return v
*/
@Override
public V put(K k, V v) {
//计算index
int index = (LENGHT - 1) & hash(k);
//拿到node对象
Node<K,V> node = table[index];
//如果node为空，说明数组中还没有，直接存入数组[index]
if (node==null){
table[index] = new Node<>(k,v,hash(k),null);
size++;
}else {
//node不为空，说明数组中已经有了，直接赋值给next，头插
table[index] = new Node<>(k,v,hash(k),node);
size++;
}
return v;
}
/**
* 通过k算出hash
* 算出index
* 找到对应的Node
* 判断Node是否为空
* 不为空 判断是否相等
* 相等：返回
* 不相等：继续查找
* @param k
* @return
*/
@Override
public V get(K k) {
if (size==0) return null;
//计算index
int index = (LENGHT - 1) & hash(k);
//拿到node对象
Node<K,V> node = table[index];
if (node!=null){
//如果第一个node相等，直接返回
if (node.hash==hash(k) && k.equals(node.getKey())){
return node.getValue();
}else {
do{
if (node.next.hash==hash(k) && k==node.getKey()){
return node.next.getValue();
}
}while (node.next!=null);
}
}
return null;
}
@Override
public int size() {
return size;
}
//计算hash值
private int hash(K k){
return k.hashCode() ^ (k.hashCode()>>>16);
}
class Node<K,V> implements Map.Node<K,V>{
K k;
V v;
int hash;
Node<K,V> next;
public Node(K k, V v, int hash, Node<K, V> next) {
this.k = k;
this.v = v;
this.hash = hash;
this.next = next;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
}
代码不是很难理解，这里简单讲一下，首先定义一个hash方法，算出key的hash，再通过key的hash与数组长度进行&运算得到下标。
put：，判断数组中这个位置是否已经存在元素，如果没有元素，则直接赋值给table[index]。如果已经有元素，则将数组中元素直接赋值给当前元素的next，这叫头插法。即插在链表的头部。
get：原理相同，同样是拿到index，然后判断hash和key是否相等，相等则返回，不相等则遍历链表继续查找。
三、测试
手写完毕，我们最后来进行测试，循环插入10条数据，并打印出来：
HashMap<String,String> map = new HashMap<>();
for (int i=0;i<10;i++){
map.put("我是Key"+i,"我是Value"+i);
System.out.println(map.get("我是Key"+i));
}
System.out.println(map.size());
输出：
我是Value0
我是Value1
我是Value2
我是Value3
我是Value4
我是Value5
我是Value6
我是Value7
我是Value8
我是Value9
10
最后可能会有同学问了，为什么没有写remove方法呢？当然是想让你们自己动手写啦，光看是看不会的，还是得动手敲起来，所以remove方法可以自己尝试着去写哦，其实remove和get原理类似，同样是先找到要删除的元素，如果要删除的元素的next不为空，则将next赋值给上一个元素的next，断开要删除元素的链，而达到删除的效果。快行动起来吧。
网友评论