自己动手用java写一个hashMap
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了自己动手用java写一个hashMap，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5139字，纯文字阅读大概需要8分钟。
内容图文
入坑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;
// 3
node.next = temp[index];
// 1
temp[index] = node;
// 2
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结束，其实并不难，只要大家认真的去看他每一个步骤和方法流程，我相信大家都能自己写出一个。我这里只是写了一个简易的，如果有什么地方不对或者有什么修改意见，欢迎大家评论探讨，我们一起进步。
内容总结
以上是互联网集市为您收集整理的自己动手用java写一个hashMap全部内容，希望文章能够帮你解决自己动手用java写一个hashMap所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。