点关注，不迷路！

快速开始

HashMap相信大家在日常的开发中都用过，首先我们快速回忆下。

public class App {
 public static void main(String[] args) {
 //Map map = new HashMap<>();
 App map=new App();
 map.put("刘一", "刘一");
 map.put("陈二", "陈二");
 map.put("张三", "张三");
 map.put("李四", "李四");
 map.put("王五", "王五");
 map.put("springboot", "源码学院-只为培养BAT程序员而生");
 System.out.println(map.get("springboot"));
 }

hashmap在我们日常工作一般用的多的就是其put方法和get方法。

技术本质

现在我们已经对hashmap有一个大致的了解了，接下来我们要去了解其底层的原理，也就是本质。

image.png

很多朋友在面试的时候经常被问到hashmap底层实现原理？都说是数据+链表 ok！估计大家都会被了
但是真正知道底层如何存储的我相信不多，不急 我们来看下数组和链表的定义

数组

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；对于一般的插入删除操作，
涉及到数组元素的移动，其平均复杂度也为O(n)

image.png

Java代码表示

//数组:采用一段连续的存储单元来存储数据。
 //特点:指定下标O(1) 删除插入O（N） 数组：查询快 插入慢 ArrayList
 public static void main(String[] args) {
 Integer[] integers = new Integer[10];
 integers[0]=0;//王五
 integers[1]=1;
 integers[2]=2;
 integers[9]=9;

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，
而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

image.png

public class Node {

 public Node next;
 private Object data;

 public Node(Object data) {
 this.data = data;
 }
 //链表：链表是一种物理存储单元上非连续、非顺序的存储结构
 //特点：插入、删除时间复杂度O（1） 查找遍历时间复杂度0（N） 插入快 查找慢
 public static void main(String[] args) {
 Node node=new Node(15);
 node.next=new Node(1);
 node.next.next=new Node(9);
 }

哈希算法

哈希算法（也叫散列），就是把任意长度值(Key)通过散列算法变换成固定长度的key地址，通过这个地址进行访问的数据结构。
它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

image.png

实现原理刚才我们分析了hashmap由数组+链表构成，介绍了数组+链表的描述，接下来我们就把这两个数据结构整合在一起吧，在整合在一起， 我们写一个伪put代码。

/***
 * 输出 key value hashcode 等 hash算法
 * @param key
 * @param value
 */
 public void put(String key, String value) {
 //hash函数
 System.out.printf("key:%s,hash值:%s,存储位置:%s\r\n", key, key.hashCode(), Math.abs(key.hashCode() % 15));
 }

运行代码如下

key:刘一,hash值:671464,存储位置:4
key:陈二,hash值:1212740,存储位置:5
key:张三,hash值:774889,存储位置:4
key:李四,hash值:842061,存储位置:6
key:王五,hash值:937065,存储位置:0
key:springboot,hash值:1362194047,存储位置:7

对应的图形存储结构就是：

image.png

实现

根据我们图形的演示，你能手写实现吗？

public interface Map<K,V> {
 public V put(K k,V v);
 public V get(K k);
 public int size();
 interface Entry<K,V>{
 public K getKey();
 public V getValue();
 }
}

具体实现：关注我的公众号，输入关键字hashmap即可下载源码。

欢迎关注公众号：Java大型网站架构

image.png