正文
自己动手用java写一个hashMap
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
入坑java很多年了，现在总结一下自己学到的东西。
1、首先我们先来聊聊什么是HashMap？
什么是hash？hash用中文的说法就叫做“散列”，通俗的讲就是把任意长度的字符串输入，经过hash计算出固定长度的字符串。而这个字符串就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
2、hash碰撞?
上面已经说到了，不同的输入值可能会计算出相同的输出，这就是碰撞。
3、java中的hashMap是怎么实现的？
java的hashMap底层是用数组加链表实现的。存储对象的时候，我们是将K/V传给put方法，然后这个put方法会调用hashCode方法计算出hash值（也就是数组的下标）从而得到存储的位置，进一步存储。那么问题来了,我们都知道，创建数组的时候是要指定数组的长度的，万一它的初始化的数组不够用怎么办？其实hashMap早都给你想好了，hashMap会根据当前你存储的数据的占用情况自动调整数组的长度。获取对象的时候，我们是把K传给get()方法，它就会调用hashCode计算hash的值从而得到存储位置，并且进一步调用equals方法确定键值对。发生碰撞的时候：HashMap通过链表将产生碰撞冲突的元素组织起来，在Java8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。关于解决hash冲突的方法在这里暂且不说，我直接上代码了。
4、代码
首先我们先定义一个Map接口:
package com.jian.utils;
/**
* Map接口
* @author weijianyi
*
* @param <K>
* @param <V>
*/
public interface Map<K,V> { //向Map中插入值
public V put(K k,V v); //根据key获取hashMap中的值
public V get(K k); //获得Map中元素的个数
public int size(); //获取Map中，键值对的对象
interface Entry<K,V>{
K getKey(); V getValue(); V setValue(V v); }
}
第二步定义我们的MyhashMap类：
package com.jian.utils;
/**
* hashMap的实现 数组+链表
*
* @author weijianyi
*
* @param <K>
* @param <V>
*/
public class HashMap<K, V> implements Map<K, V> {
// 数据存储的结构==>数组+链表
Node<K, V>[] array = null; // 数组/哈希桶的长度,就是数组初始化的长度
private static int defaultLength = 16; /**加载因子/扩容因子,就是给数组界定一个存储阈值,
当数组沾满整个数组的75%的时候,触发扩容操作)**/
private static double factor = 0.75D; // hashMap中的元素个数
private int size; // put元素方法
@SuppressWarnings("unchecked")
@Override
public V put(K k, V v) { // 1.载机制，使用的时候进行分配
if (array == null) {
//初始化一个数组,给的长度是defaultLength
array = new Node[defaultLength];
} // 2.通过hash算法，计算出具体插入的位置,也就是数组的下标
int index = position(k, defaultLength); // 扩容,判断是否需要扩容
// 扩容规则,元素的个数size 大于 桶的尺寸*加载因子
if (size > defaultLength * factor) {
resize();
} // 3.放入要插入的元素(添加到链表)
Node<K, V> node = array[index];
//先判断一下这个链表的index位置是否为空
if (node == null) {
//链表的index这个位置是空的,直接新建该链表并将值放入该位置
array[index] = new Node<K, V>(k, v, null);
//元素的个数加自增1
size++;
} else {
if (k.equals(node.getKey()) || k == node.getKey()) {
return node.setValue(v);
} else {
array[index] = new Node<K, V>(k, v, node);
size++;
}
} return null;
} // 扩容,并且重新排列元素
private void resize() {
// 翻倍扩容
// 1.创建新的array临时变量,相当于defaultlength*2
@SuppressWarnings("unchecked")
Node<K, V>[] temp = new Node[defaultLength << 1]; // 2.重新计算散列值，插入到新的array中去。 code=key % defaultLength ==> code=key %
// defaultLength*2
Node<K, V> node = null;
for (int i = 0; i < array.length; i++) {
node = array[i];
while (node != null) {
// 重新散列
int index = position(node.getKey(), temp.length);
// 插入链表的头部
Node<K, V> next = node.next;
//
node.next = temp[index];
//
temp[index] = node;
//
node = next; }
} // 3.替换掉旧的array
array = temp;
//更新默认的扩容因子的值
defaultLength = temp.length;
temp = null; } // 计算位置
private int position(K k, int length) {
int code = k.hashCode(); // 取模算法
return code % (length - 1); // 求与算法
// return code & (defaultLength-1);
}
/**
* 用K获取hashMap 的K对应的值
*/
@Override
public V get(K k) {
if (array != null) {
int index = position(k, defaultLength);
Node<K, V> node = array[index];
// 遍历链表
while (node != null) {
// 如果key值相同返回value
if (node.getKey() == k) {
return node.getValue();
} else {
// 如果key值不同则调到下一个元素
node = node.next;
}
}
} return null;
}
/**
* 获取hashMap元素个数
*/
@Override
public int size() { return size;
} // 链表节点(链表类)
static class Node<K, V> implements Entry<K, V> {
K key;
V value;
//表示下一个节点
Node<K, V> next; // 构造一个包含当前节点和下一个节点的链表
public Node(K key, V value, Node<K, V> next) {
super();
this.key = key;
this.value = value;
this.next = next;
}
/**
* 链表的get和set方法
*/
@Override
public K getKey() {
return this.key;
} @Override
public V getValue() {
return this.value;
} @Override
public V setValue(V v) {
V oldValue = this.value;
this.value = v;
return oldValue;
} } // 测试方法
public void print() {
System.out.println("===============================");
if (array != null) {
Node<K, V> node = null;
for (int i = 0; i < array.length; i++) {
node = array[i];
System.out.print("下标[" + i + "]");
// 遍历链表
while (node != null) {
System.out.print("[" + node.getKey() + ":" + node.getValue() + "]");
if (node.next != null) {
node = node.next;
} else {
// 到尾部元素
node = null;
}
}
System.out.println();
} }
}
}
到此，自己动手写一个hashMap结束，其实并不难，只要大家认真的去看他每一个步骤和方法流程，我相信大家都能自己写出一个。我这里只是写了一个简易的，如果有什么地方不对或者有什么修改意见，欢迎大家评论探讨，我们一起进步。
