博客

HashMap是我们在Java程序中常用的数据结构，但是他的具体实现你是否了解，接下来，我们将自己来写一个HashMap类，从中可以看到HashMap的底层实现是什么。

当然我们实现的HashMap与Java自己的相比并不一致，只是一个简单的实现以此来熟悉一下HashMap的实现原理。


在Java中HashMap的实现原理是 数组+链表(当链表中的元素超过8个时候将会变成红黑树)

1.什么是hash

HashMap离不开hash，什么是hash？他是一种算法可以将任意长度的输入转化为固定长度的输出，在HashMap里面hash算法将任意的key转化为数组对应的下标以此来存储

key-value

形式的对象。理想的hash算法可以使得输入均匀分散的遍布整个数组。当然也有几率出现，两个不同的key生成的hashCode一致的情况，这样的情况被称为碰撞。

如何解决碰撞？Java的处理方式是将数组里面的元素变成链表，当发生碰撞的时候将元素插入链表的头部。当查询的时候，若是该数组元素中不止一个，便依次遍历链表直到找到相同的key进行覆盖存储，若是没有则进行链表的新增（当然Java还会在大于8个元素的时候进行红黑树的转换，依次来减小时间的开销）

2.什么是HashMap

HashMap可以这样来形容，他类似于一个有许多抽屉的柜子(容器)，每个抽屉上面都有一个标签来标识这个抽屉里面装的类别(key)，打开对应标签的抽屉以后你可以就可以找到对应的东西(value)，因此可以看到当查找HashMap的时候他理想的时间复杂度为

O(1)


3.简单Hash算法的实现、

public int hash(String key){
     if(key == null){
        return 0;
     }else{
       return key.length();
     }
}

通过以上的程序，我们可以得到一个简单的hash算法，当然这边明显可以看到不足，当key传入

cat

与

dog

两个字符串的时候，他返回的hash值是一样的，但是其实他不一样，所以我们需要进行改进。

public int hash(String key){
     if(key == null){
        return 0;
     }else{
       int code = 0;
       for(int i =0 ; i < key.length();i++){
          code += key.codePointAt(i);
       }
       return code;
     }
}

以上方法便可以解决传入

cat

与

dog

的问题了，但是问题还是要有的

cat

与

act

的问题又出现了。

所以继续改进：

public int hash(String key){
     if(key ==