当前位置 博文首页 > 偶像java练习生的博客：面试被问到HashMap 底层原理?看完这边文
存储：put 方法 put(key,value)
查询 : get 方法 get(key)
java 代码如下
import java.util.HashMap;
import java.util.Map;
public class App {
public static void main(String[] args) {
Map<String,String> map = new HashMap<>();
map.put("刘一","刘一");
map.put("陈二","陈二");
map.put("张三","张三");
map.put("李四","李四");
map.put("王五","王五");
map.put("Money","我是猴哥Money老师");
System.out.println(map.get("Money"));
}
}
//输出结果：我是猴哥Money老师
程序是等于我们的数据结构和算法
HashMap 其实就是做存储的，做存储的就是数据结构
存储是按上面的规则存储的，那查询是怎么查的了
//数组：采用一段连续的存储单元来存储数据的
//数组的特点: 查询时间复杂度:0(1) ,删除,插入,时间负责度0(N),总结：查询块，插入慢
public static void main(String [] args){
//数组的定义：初始化长度为10，数据类型Integer ,
Integer integer[] = new Integer[10];
//指定下标，复制
integer[0]=0;
//指定下标，复制
integer[1]=1;
//指定下标，复制
integer[9]=2;
//指定下标，复制
integer[9]=400;
System.out.println(integer[9]);
}
// 输出结果：400
数组结构如图：
查询： 时间复杂度 0（1）,查询非常快的
删除，插入 ：时间复杂度0（N） 非常慢的，效率没有查询那么快
为什么查询快，插入，删除慢了？
查询快
插入，删除慢
扩充：
大家知道我们java 哪一个类，底层用的就是数组？
在我们的java.util 包下面有一个ArrayList 类，如图
怎么验证了？
我们查看它的add 方法
public boolean add(E var1) {
this.ensureCapacityInternal(this.size + 1);
this.elementData[this.size++] = var1;
return true;
}
如果面试被问到ArrayList 的特性，直接回答 查询快，插入，删除慢
谈谈什么是链表？
在java 中是这么定义的：
package node;
import com.sun.org.apache.bcel.internal.generic.IMPDEP1;
public class Node {
public Node next;
private Object data;
public Node(Object next) {
this.data = next;
}
//链表：链表是一种物理存储单元上非连续，非顺序的存储结构
//特点: 插入，删除时间复杂度0(1) 查找遍历时间复杂度0(N) 总结：插入快,查询慢
public static void main(String[] args){
Node head =new Node("monkey");
head.next =new Node("张三");
head.next.next =new Node("刘一");
System.out.println(head.data);
System.out.println(head.next.data);
System.out.println(head.next.next.data);
}
}
//输出结果:
//monkey
//张三
//刘一
链表：链表是一种物理存储单元上非连续，非顺序的存储结构,如图：
为什么它插入，删除快，查询慢了？
删除 某个节点，只需要上一个节点 head.next =null
插入 某个几点，只需要上一个节点 head.next 指向插入的节点，插入的节点指向下一个节点
查询某个节点：链表查询都要通过头节点，比如我们要查‘刘一’，我们则要先查头monkey,再查张三，再查到刘一，
虽然只有3个节点，但是我们要查到刘一要查三次，把整个链表都遍历了一次，所以查询慢！
扩充
在我们java 中，哪一个util 类采用的链表来实现的?
我们来查看它的add 方法
public boolean add(E var1) {
this.linkLast(var1);
return true;
}
//看上面有一个linkLast,如下:
void linkLast(E var1) {
LinkedList.Node var2 = this.last;
LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
this.last = var3;
if (var2 == null) {
this.first = var3;
} else {
var2.next = var3;
}
++this.size;
++this.modCount;
}
//看上面有一个Node,如下:
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
this.item = var2;
this.next = var3;
this.prev = var1;
}
}
//上面有一个next,有一个prev
//这是一个双向链表
双向链表如图: 类似与分页，上一页，下一页，下面的对象也可以获取上面对象的数据（head.prev）
现在大家都已经了解JDK7 HashMap 数据结构了，开始了解下算法！
那么HashMap 是怎么去存储的了？他是如何将数据放到我们的数组和链表上的？
用的就是哈希算法，你们知道哈希算法的底层是怎么实现的？
哈希表
什么是哈希算法？
哈希算法（也叫散列），就是把任意长度值（key）通过散列算法变换成固定长度的key(地址)， 通过这个地址进行访问的数据结构，
它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。
例如图中的John Smith 通过散列算法变换成固定长度的key:152 （永远是152），然后通过152 变成John Smith 是不可能的，哈希算法是不可逆的。
HashCode: 通过字符串算出它的ascii 码，进行mod(取模)，算出哈希表中的下标
代码如下：
public class AsciiCode {
public static void main(String[] args) {
char c [] ="lies".toCharArray();
for (int i = 0; i < c.length; i++) {
System.out.println((c[i])+":" +(int)c[i]);
}
}
}
//输出结果：
//l:108
//i:105
//e:101
//s:115
如果我们取模会出现什么问题
会出现hash 冲突(碰撞)的一个问题,
什么是hash冲突
Hash冲突怎么解决了
我们用链表来解决这个问题, 链表是有一个指针的，我们可以让这个lies 指向这个foes,我们让foes 去匹配下标为9 的这个节点，如果匹配lies 不相等，则去匹配下一个节点foes,最终就会找到这个foes,这就是我们hash 算法底层的原理及解决冲突。
public class App {
public static void main(String[] args) {
//Map<String,String> map = new HashMap<>();
App map = new App();
map.put("刘一","刘一");
map.put("陈二","陈二");
map.put("张三","张三");
map.put("李四","李四");
map.
