前言
网上对于HashMap的实现有很多,也写得很不错。我也读过许多对数据结构有比较深理解的博文,感触也比较深。今天写这篇文章也可以算是一个读后感。或者说是对阅读之后的一个加深理解。其实HashMap的原理其实绝大部分的人都知道,底层是数组加链表结构实现的。但是为什么要这样实现,不知道大家有没有去想过这个问题。
数组
首先说一下数组的特性:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)。数组对于给定下标查询的速度是非常快的,但是对于插入或者删除操作的时候,就稍微显得有点力不从心了。
链表
链表的特性:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)。从上面的时间复杂度可以看出,链表对于新增,删除操作是在非常快,对于查询就出现了它的弊端。
在这样的背景下,于是就有聪明人想到了一个问题。为何不将他们二者之间的优势结合起来,不就完美了吗。这是哈希表结构就应运而生了。
哈希表
相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。
t01a3c20166ce2ee885.jpg
根据上面的图,其实我们大致能看出他的实现思路。通过key的哈希函数获得对应的hash值,以hash值作为下标寻找对应的数组中的位置,如果当前位置没有值则插入,如果已经存在时。这时才是hashmap的精髓之处。这里我们统称 哈希冲突,如何解决这个冲突就产生了几个不同的数据结构方向。开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法(这里介绍一下 散列:散列(Hashing)是计算机科学中一种对资料的处理方法,通过某种特定的函数/算法(称为散列函数/算法)将要检索的项与用来检索的索引(称为散列,或者散列值)关联起来,生成一种便于搜索的数据结构(称为散列表)。二次再散列法是指第一次散列产生哈希地址冲突,为了解决冲突,采用另外的散列函数或者对冲突结果进行处理的方法
),链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。
大致的一个思路是这样的,当然实际过程中肯定还有各种各样的问题,这只有亲身操作了才有体会。这里我也简单的实现了一把,并附上了注释以及说明。当然其中的很多功能并没有全部实现。
1.首先定义接口
package com.example.demo.MyHashMap;
public interface IMyMap<K,V> {
// 实现hashmap时 需要注意的几个地方 1.了解HashMap数据结构组成 数组+单链表
// 2.如何解决key hash后的平均分布,减少碰撞 hash函数实现
// 3.数据阈值的控制以及扩容
public V put(K k,V v);
public V get(K k);
// 定义内部entry接口
interface Entry<K,V>{
public K getKey();
public V getValue();
}
}
2.实现接口
package com.example.demo.MyHashMap;
import java.util.ArrayList;
import java.util.List;
public class MyHashMap<K,V> implements IMyMap<K,V> {
// 定义底层数组的初始化大小
private static final int DEF_INIT_CAP = 1 << 4;
// 定义阈值比例 容量达到这个比例时,就需要进行扩容
private static final float DEF_LOAD_FACTOR = 0.75f;
private int defaultInitSize;
private float defaultLoadFactor;
//map中entry数量
private int entrySize;
//table数组
private Entry<K,V>[] tables = null;
// 定义构造函数 注意这里为什么需要这样定义构造函数 实际上用到的都是第二个构造函数。这里实际上用到了门面的设计模式。
// 这里的主要作用是为:子系统提供一个集中化和简化的沟通管道
public MyHashMap(){
this(DEF_INIT_CAP,DEF_LOAD_FACTOR);
}
// 初始化信息
public MyHashMap(int defaultInitSize,float defaultLoadFactor){
if(defaultInitSize <0) throw new IllegalArgumentException();
if(defaultLoadFactor <=0 || Float.isNaN(defaultLoadFactor)) throw new IllegalArgumentException();
this.defaultInitSize = defaultInitSize;
this.defaultLoadFactor = defaultLoadFactor;
tables = new Entry[defaultInitSize];
}
@Override
public V put(K k, V v) {
//定义以前的值
V oldValue = null;
// 在put之前需要判断 map数量是否需要扩容
if(entrySize >= (defaultInitSize * defaultLoadFactor)){
// 需要进行扩容操作
resize(2*defaultInitSize);
}
// 对key进行哈希处理 得到index位置
int index = hash(k) & (defaultInitSize -1);
// 判断这个位置 数组是否存在值
if(tables[index] == null){
tables[index] = new Entry<K,V>(k,v,null);
++entrySize;
}else{
// 如果存在 则需要遍历这个链表
Entry<K,V> entry = tables[index];
Entry<K,V> e = entry;
// 遍历
while (e != null){
if(k == e.getKey() || "k".equals(e.getKey())){
oldValue = e.value;
e.value = v;
return oldValue;
}
e = e.next;
}
// 重新插入tables中
tables[index] = new Entry<K,V>(k,v,entry);
++entrySize;
}
return oldValue;
}
@Override
public V get(K k) {
int index = hash(k) & (defaultInitSize - 1);
if(tables[index] == null){
return null;
}else{
Entry<K,V> entry1 = tables[index];
do {
if(k == entry1.getKey() || k.equals(entry1.getKey())){
return entry1.getValue();
}
entry1 = entry1.next;
}while (entry1.next != null);
}
return null;
}
// hash函数参考 采用jdk中实现的
private int hash(K k){
int hashCode = k.hashCode();
hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
return hashCode ^ (hashCode >>> 7) ^(hashCode >>>4);
}
// 数组扩容 这里需要注意 初始变量需要改变
public void resize(int i){
Entry[] table = new Entry[i];
defaultInitSize = i;
entrySize = 0;
rehash(table);
}
public void rehash(Entry<K,V>[] newTable){
// 对老的集合进行遍历 并放进新的集合中
List<Entry<K,V>> list = new ArrayList<>();
for(Entry<K,V> entrys : tables){
if(entrys != null){
// 对链表进行遍历
do {
list.add(entrys);
entrys = entrys.next;
}while (entrys != null);
}
}
//将原来的引用覆盖
if(newTable.length > 0){
tables = newTable;
}
// 重新put
for(Entry<K,V> entry1 : list){
put(entry1.getKey(),entry1.getValue());
}
}
class Entry<K,V> implements IMyMap.Entry<K,V>{
private K key;
private V value;
private Entry<K,V> next;
public Entry(){
}
public Entry(K k,V v ,Entry<K,V> next){
this.key = k;
this.value = v;
this.next = next;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
}
}
这里把代码都写在了一起,为了方便就没有单独在抽出来了.... 这只是一个简单的实现,如果有兴趣或者想提高自己对数据结构的理解,还是推荐亲自去实现一把,还是有收获的。如果觉得有收获记得点个赞(__)
网友评论